P10059 [CCO2022] Good Game 题解

Perta · 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