题解：P9717 [EC Final 2022] Binary String

xiazha · 2026-11-10 14:45:09 · 题解

目前已有的题解对我来说均晦涩难懂，让我来讲讲人话。

首先，当字符串中没有连续 0 或连续 1 出现时，就会进入循环，并且循环次数为最小循环节长度。

如果 0 的个数比 1 多，我们可以将字符串 01 翻转，同时整体反转，这样等价于原问题，这样我们只用考虑最终没有连续 0 的情况。

现在核心问题就是：求出经过多少秒后字符串中没有两个 0 在环上相邻，并且求得此时的字符串形态，然后用 kmp 跑一下最小循环节就做完了。

记所有 0 的位置为 f_1,f_2,\cdots,f_k，记 z_j(t) 表示 t 时刻第 j 个 0 的位置。

我们先断环成链，将两个 s 拼接在一起，令 f_{j+k} = f_j+n。

手模一下发现 z_j(t+1) = \min( z_j(t) + 1 , z_{j+1}(t) - 1 )。

再往后推一项：z_j(t+2) = \min(z_j(t)+2,z_{j+1}(t),z_{j+2}(t)-2)。

归纳得出 z_j(t) = \min_{0\le s\le t} ( f_{j+s} + t - 2s )。

如果我们得到终止时间 t'，那么用单调队列求一下所有 0 的最终位置就可以把字符串求出来了。

下面考虑如何得到终止时间 t'。

目标是 z_{j+1}(t) − z_j(t) \ge 2 对所有 j 成立，转化一下得到 \min_{1\le s \le t+1} (f_{j+s}-2s) \ge \min_{0\le s\le t} (f_{j+s}-2s)。

这个 2s 的贡献卡在这里很烦人，于是再做一步转化，记 p_j=f_{j+1}-f_j-2，pre_j=\sum_{1\le i\le j} p_i，那么等价于对于任意 j，满足 pre_{j + t + 1} \ge \min_{j \le u \le j+t} pre_u。

想要找到这个最小的 t' 只需要求得 prev_q 表示最大的 u < q 且 pre_u \le pre_q，跑个单调栈就行了。

至此本题就做完了，时间复杂度 O(n)。