P11190 「KDOI-10」反回文串 题解

前言

upd on 2024.10.16：发现了针对原思路的 hack，修改了不正确的特判部分

场上写了不用动脑子的 40pts 部分分，挂成 4pts。

比较恶心的分类讨论构造题，但个人觉得比 T2 T4 可做，反正都是我做不出来的题（？）

思路

发现这个题的限制似乎不是特别多，非常多的情况下都可以把不一样的字符两两配对，于是应当尽量使最终的解接近这种形式。

这个题的两个特殊性质极为友好，先从特殊性质入手。

先来看性质 A：考虑一张将每个字符出现次数从小到大排序的柱状图，发现如果每次取出其中出现次数最多的两个字符，这张柱状图将越来越平缓，由于保证每个字符出现次数 $\leq \frac{n}{2}$，每个字符最终都能够被配对。于是按照该思路使用大根堆等维护每个字符的出现次数并模拟即可。

将性质 A 的做法推广到串长为奇数的情况：将剩下的最后一个字符随便扔到一个子序列中即可。如果这样不合法，那么所有的 $\lfloor \frac{n}{2} \rfloor$ 个子序列中一定均含有该字符，加上本身后，与“每个字符出现次数 $\leq \lfloor \frac{n}{2} \rfloor$”的限制不符。于是我们解决了串中字符出现次数均 $\leq \lfloor \frac{n}{2} \rfloor$ 的情况。

发现性质 B 也很具有启发性：由于只有两种字符，除了出现次数相等的情况，其余情况出现次数较多的字符的出现次数均 $>\lfloor \frac{n}{2} \rfloor$。

不妨设串中 $\text{a}$ 的出现次数较多。首先特判掉只有一个 $\text{b}$ 居中且长度为奇数的情况，这一定是不合法的。其余情况下，由于不能存在全 $\text{a}$ 串，答案的上界为 $cnt_b$。

先尝试一个朴素的贪心策略：从左到右枚举每个 $\text{a}$，寻找其右边是否还存在 $\text{b}$，若存在则将它们配对。这个过程进行完之后，字符串只会剩下一段 $\text{b}$ 和一段 $a$，且这 $x$ 个 $a$ 一定是原串中最后 $x$ 个。

最后剩下了前缀若干个 $\text{b}$ 的情况是好解决的，由于 $\text{a}$ 出现次数更多，直接把 $\text{a}$ 挂在 $\text{b}$ 后面就做完了。那如果最后剩下的只有 $\text{a}$ 该如何解决呢？

先把后面存在配对过的 $\text{b}$ 的那些 $\text{a}$ 挂在后面的 $\text{b}$ 之前，形成的子序列形如 $\text{aaa...b}$，这样一来就只剩下了原串末尾的若干个 $\text{a}$。考虑将它们挂在 $\text{aaa...b}$ 之后。这时的限制很松，只要有一个子序列前缀 $\text{a}$ 的数量与当前还剩下的个数不同，就可以全部挂在其末尾；否则，挂一个 $\text{a}$ 在第一个子序列中，把剩下的 $\text{a}$ 挂在第二个子序列中即可。似乎做完了？

实际上还存在一种未考虑的 corner case，即后缀 $\text{a}$ 个数为 $1$ 且之前配对的子序列均为 $\text{ab}$ 的情况，进行最后一步操作是不合法的。此时将最后一个 $\text{a}$ 和倒数第二个 $\text{b}$ 配对，然后删除这两个字符，再对剩余的字符串进行原来的解法即可。

于是我们解决了仅有两种字符的问题。其余情况，将出现次数最多的字符当作 $\text{a}$，剩下都当作 $\text{b}$，与原来并无本质区别。

至此所有情况都被考虑周全。代码实现挺复杂的。

代码

link，写的很丑，仅供参考。