自动搬运

查看原文

来自洛谷，原作者为

	Elma_ blog：https://www.cnblogs.com/came11ia

搬运于2025-08-24 22:51:07，当前版本为作者最后更新于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)$。