P9717 [EC Final 2022] Binary String

Elma_ · 2023-12-20 16:22:07 · 题解

咕值要掉没了，水点题解。

很炫酷的题。

以下的 “段” 均指长度大于 1 的 0 或 1 的连续段。手玩一下能够发现一些规律：

• 对于一个 0 段，如果其左边不和某个 1 段相邻，变换后会整体往左移动一位。
• 对于一个 1 段，如果其右边不和某个 0 段相邻，变换后会整体往右移动一位。
• 如果一个 0 段接在一个 1 段后面，那么相当于两个段相撞，变换后长度都会减 1。

这个过程会一直执行直到不存在 0 或 1 的段。每次相撞会使段的长度减 1，并且 0 段和 1 段的运动方向是相反的，所以显然变换是有限次。之后就会变成一个串在环上不断绕圈，求出这个串之后就只需要用 KMP 求一下最小整周期即可。

考虑怎么求出最后这个串。不妨假设 1 段总长度不小于 0 段总长度。

注意到这个过程和括号匹配很像阿，考虑如果不是环而是序列的话，实际上我们可以直接模拟一遍求出每个 0 连续段会在什么时候消失，以及所有 0 连续段消失后的串。而如果是环，考虑当前没有剩下的 1 去和 0 匹配的情况，由于是个环所以这些 0 会跑到末尾的位置，看起来就很烦。

那考虑规避掉这种情况。根据 Raney 引理，我们总是能找到⼀个起点位置，使得每个前缀中 1 段长度和均不小于 0 段长度和。于是直接做就行了，时间复杂度 \mathcal{O}(n)。