考虑对操作进行转换。假设 \(a_i\) 为第 \(i\) 个 \(1\) 前面的 \(0\) 的个数。
则操作可以进行如下转换：
转换 1：选择一个长度为 \(k + 1\) 的子区间 \(a_{l ~ l + k}\)。我们先把 \(a_{l + 1 ~ l + k - 1}\) 翻转，然后更改 \(a_l\) 和 \(a_{l + k}\) 使得 \(a_l + a_{l + k}\) 不变。
转换 2：操作是可逆的，所以若我们能把 \(S, T\) 都转换成同一个字符串 \(I\)，那么 \(S \rightarrow T\) 就是可行的。
于是现在的问题是能否把 \(S, T\) 转换成同一个 \(I\)。
现在我们想要把 \(a\) 数组不为 \(0\) 的值尽量往前移，且我们有 \(2\times n\) 的操作次数。
容易发现，当我们翻转了一个 \(a_{l ~ l + k}\) 时，我们可以让 \(\begin{cases}a_l = a_l + a{l + k}\\a_{l + k} = 0\end{cases}\)，这样我们操作了 \(n - k\) 次后，只会有 \(a\) 的前 \(k + 2\) 个位置有值。
然后我们考虑如何把前 \(k + 2\) 个位置移到第 \(1\) 个位置。
若我们每次操作 \(a_{1 ~ k + 1}\) 和 \(a_{2 ~ k + 2}\)，则每次 \(a_{2 ~ k + 1}\) 会先进行长度为 \(2\) 的循环位移，然后把前两个数设为 \(0\)。
经过 \(\lfloor \frac{k}{2} \rfloor \times 2\) 次操作后，\(\forall 2 \leq i \leq k + 1, a_i = 0\)。
然后，分类讨论。
先考虑 \(2 \ |\ k\) 的情况。我们发现，奇数编号的位置不可能转到偶数编号的位置，所以不可能。
再考虑 \(k\) 为奇数的情况。这时候，我们只要 \(a_{2, k + 2}\) 和 \(a_{1, k + 1}\) 轮流操作即可。次数 \(k + 1\)。
时间复杂度 \(\mathcal{O}(n ^ 2)\)，操作次数最大为 \(n + k + 1\)。由于 \(k = n\) 时不可能存在解，所以满足限制。
代码咕了。
标签：CF1530G,转换,题解,位置,操作,我们 From： https://www.cnblogs.com/aemmprty/p/18115537