自动搬运

查看原文

来自洛谷，原作者为

	Perta broken tower

搬运于2025-08-24 22:54:14，当前版本为作者最后更新于2024-01-08 20:01:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

官方题解对笔者而言较为抽象，本文仅提炼出了本题的解法而非解题思路。网上除了 pjudge 也找不到其他题解，组题时花了一些功夫。作为题解搬运工，对一些神奇想法的出处一概不知，所以凑合着看吧...

将原串划分为若干极长全 $\tt A$/$\tt B$ 子串，例如 $\tt ABBAAABBBBA$ 划分为 $\tt A,BB,AAA,BBBB,A$，发现只需要考虑两种子串：长度为 $1$ 的 & 长度大于 $1$ 的。

用 $\tt 1$ 表示长度为 $1$ 的子串，$\tt 2$ 表示长度大于 $1$ 的子串。设 $T$ 为 $S$ 的划分，$T$ 可以用 $\tt 1,2$ 表示，例如上述串的划分 $T=\tt 12221$。

显然，两个串的 $T$ 相等就意味着这两串是等价的。考虑一次操作对 $T$ 的影响：

• 删除最左端或最右端的 $\tt2$；
• 删除非最左端或最右端的 $\tt2$，并将相邻的两个元素合并为一个 $\tt2$；e.g. $\tt (122)21\to221$

我们略去的影响是 $\tt2\to2$ 和 $\tt2\to1$，前者是无意义的，后者不会更优，所以略去。

现在，$S$ 能够被删空，等价于 $T$ 可以由以上两种影响变空。

不妨将 $\lvert T\rvert$ 分奇偶讨论。

$\lvert T\rvert =2k+1$

可以通过打表或者惊为天人的灵感获得结论：$T$ 无法被删空，当且仅当 $T_{k+1}=\tt1$ & 至少有连续的 $k$ 个 $\tt1$ 在同一个连续段。

例如，当 $k=4$ 时，以下形式的 $T$ 无法被删空：

X1111XXXX
XX1111XXX
XXX1111XX
XXXX1111X

证明（构造方案）是容易的。

充分性：假设整个 $T$ 中只有这 $k$ 个 $\tt1$，左侧有连续的 $l$ 个 $\tt2$，右侧有连续的 $r$ 个 $2$，则最多删去 $l+r-2\leq k-1$ 个 $\tt1$，不止有 $k$ 个 $\tt1$ 的情况就不用说了。

必要性：当 $T_{k+1}=\tt2$ 时一直删最中间这个 $\tt2$ 即可。若没有连续的 $k$ 个 $\tt1$，则任意两个相邻的 $\tt2$ 下标差 $\leq k$。我们选择与最中间的 $\tt1$ 的连续段相邻的两个 $\tt2$，例如 $\tt xx21112xx$，观察 $T_{\frac{\lvert T\rvert+1}{2}}$ 如何变化：

发现删除任意一边的一个 $\tt2$，$\frac{\lvert T\rvert+1}{2}$ 向另一边偏移一位且中间少一个 $\tt1$。

最坏情况中间连续的是 $k-1$ 个 $\tt1$，左边的 $\tt2$ 在 $L$ 的位置，右边的 $\tt2$ 在 $L+k$ 的位置。只删左边的 $\tt2$，可以删 $L-1$ 次，那么 $\frac{\lvert T\rvert+1}{2}$ 对应到初始序列上的下标范围就是 $[k+1,L+k]$，也就是说右边的 $\tt2$ 某一时刻在 $T$ 中的位置一定会是 $\frac{\lvert T\rvert+1}{2}$，此时再一直删这个 $\tt2$ 即可。

$\lvert T\rvert=2k$

真的要去做的话很复杂，但是...

大胆猜测，若 $T$ 可以被删空，一定存在 $T=PQ$ 使得 $\lvert P\rvert,\lvert Q\rvert$ 均为奇且 $P,Q$ 可以被删空。

假设 $T$ 可以被删空。由于 $\lvert T\rvert\geq2$，经过一系列操作，最后一定有 $T'=\tt22$。此时有 $P'=Q'=\tt2$，则必然能还原出一对满足结论的 $P,Q$。

找划分点是容易的，判断每个前后缀是否合法即可。

实现采用链表，时间复杂度 $O(n)$。

Code