赛时
T1
发现公差只有 \(m/n\) 个,可以枚举,对于每个数在一个公差下可以推出首项为几是它才不改变,我开 \(map\) 存了在这个公差,首相下有几个 \(a\) 可以不变。此时快九点。
T2
很快有了 \(O(n^3)\) 的做法,感觉很好写,就没有立即写,想着再想想,把后面的题想了一圈,受挫,回来老实码,码完不过样例,发现有三个相同的数不会立即消除,改改改,过样例时已经十点多。
T3
想贪心确定左脚后,右脚在相同颜色中取最近的,发现不对。还有半个小时时,回来老实码 \(O(n^4)\) 暴力 \(dp\) 。
T4
不会。。。
赛后
估分 100+50+20+0=170
实际 70+40+30+0=140
挂的算少的了。
T1 公差上下边界开错了,应该是 \(1\) 到 \((m-1)/(n-1)\) ,我开的 \(0\) 到 \(m/n\) ,\(Wa\) 了几个点,用 \(map\) 会 \(T\) ,要用桶每次只存首项。
T2 状态转移有点问题。
T3 先迈左脚再迈右脚可以优化到 \(O(n^3)\) ,感觉还挺不好想的,然后斜率优化。
T4 单调队列的 \(20\) 分应该要会的。