省选-思维题 · Zhl2010 第二博客

感觉关键就是和出题人脑电波对上，这里展示几个常见的技巧。

这道题的关键思想是将问题转化成可以从上一个状态转移过来的动态规划问题。

其实是先用平均思想吧问题化简，然后在进行进一步的完成。

其实可以手动模拟一下样例，然后就会发现问题。我们进行各种分类讨论就可以得到结论了，然后递归。

这道题就是不一定会投自己家方向的，如果 $p_1\ge p_n$ ， $n$ 和 $1$ 站在同一边。

把“不连续出现”问题转化成隔板与匹配的问题。

常见构造思路，利用斜着的循环：

C++

1 2 3 4 5 6 
2 3 4 5 6 1
3 4 5 6 1 2
4 5 6 1 2 3
5 6 1 2 3 4
6 1 2 3 4 5

然后发现可以每一个颜色的位置可以再加上一个颜色和原来的颜色交替。

遇到这种题就自求多福吧。

从最简单的 $1$ 考试考虑，最后找到一般的情况，一点点转移。

关键是需要发现这个循环不变。

关于二进制运算的我们需要尝试将每一位拆分。我们可以写出模拟程序模拟这些步骤。

然后不难发现，高位的 $1$ 对不会影响低位，所以我们可以先处理高位，然后低位再处理。遇到进位我们可以计算是否超过 $k$ 轮然后向高位进行转移。

这样不会卡，但是正解还需要用栈维护，也就是直接跳过一定需要走的 $0$ 对。