B4323 [科大国创杯小学组 2025] 改写

· · 题解

不难发现一个性质：任意两个不同颜色的段，无论长度是多少，拼起来一定是一个非回文串。

那么长度不小于 2 的段一定能分成两部分，而长度为 1 的段只能作为一部分。

那么就可以考虑把长度大于 2 的连续段的段长全部设置为 2，剩下长度只有 1,2 的序列（因为同色段是回文的，长度 \ge 2 的连续段能且仅能划分为 2 段）。

这样我们就把整个串压缩到了 \mathcal{O}(n) 的长度了。

贪心地想，如果想让划分数尽可能多，每次只应取两段，也就是说，序列中只有相邻项能划分。

对于一个长度全为 1 的子串，其内部的点肯定只能两两匹配，最后剩下 1 段或 2 段。

对于一个长度全为 2 的子串，如果段数等于 1，那么肯定没法操作，但段数大于 1 时，每相邻两段之间一定能完成匹配，并且最终两端还能决定留不留下一部分与邻段匹配。

可以发现，上面两种处理产生的匹配数一定最优，并且不会对其余部分产生影响。

这启示我们对连续段进行压缩，最后只剩下四种类型的段：

a，ab，aa，aabb。

分别称它们为 A,B,C,D，其中 A,B 和 C,D 必然交替出现。

其实还可以继续简化，令 $B$ 和周围的两个 $C,D$ 产生匹配一定是最优的，因为 $D$ 严格优于 $C$，而令 $B$ 和周围的 $C,D$ 匹配，相当于把这三项合并，进行两次匹配，并产生一个新的 $D$。 如果 $B$ 周围没有段，那么就只有这一段，内部匹配掉即可。 如果 $B$ 在开头或结尾的话，内部匹配一定是最优的，因为即使匹配了一侧，另一端多出的那部分无法匹配，就只能考虑合并，但合并有可能失败，一定不会更优，特别地，删去开头或结尾处的 $B$ 也可以把相邻的 $C$ 设置为 $D$，理由会在后文中解释。 除去所有 $B$ 后，序列中就只剩下 $A,C,D$ 了，并且 $A$ 和 $C,D$ 是交替出现的。 此时想要产生最多的匹配数，一定是尽量多地匹配 $A$，又由于 $C,D$ 的匹配位置是任意的，所以一定能完全匹配 $A$。 但是还有一种 $CACAC\dots AC$ 的情况，这时会有一个 $C$ 失配。 如果我们先前在首尾删去了 $B$，那么我们可以顺带删去一个 $C$，等价于将 $C$ 设置为 $D$。 如果存在一个 $A$ 是由长度大于 $1$ 的全 $1$ 段删除得到的，那么就可以用一端的匹配处理掉一个 $C$。因为 $11X$ 和 $X11$ 一定是非回文串（$X$ 是一个长度不为 $1$ 的段）。 反之，我们就要考虑把其中一个 $C$ 拆成两份，一种拆分方式不合法当且仅当至少有一边产生了回文串，但是即使在 $C$ 的长度最小，也就是 $2$ 的时候，也存在 $(0,2),(1,1),(2,0)$ 三种拆分方式，所以至少有一种合法的拆分方式。 那么只有在 $C1C$ 或 $C$ 或 $A$ 的时候，我们不能用上述方式拆分，进行讨论。 $C$ 显然无解。 $C1C$ 只要判断两端的字符串是不是完全相同即可，相同就无解，否则答案为 $1$。 $A$ 可能稍微困难一些，此时原串的长度和段数均 $L$ （$L$ 为奇数）。采用类似的思路，我们考虑合并掉其中三个段，那么段的位置可能为“奇-偶-奇”或者 “偶-奇-偶”。 如果我们删除的段落为“奇-偶-奇”，则剩下的段落长度均为偶数，可以自行匹配。 如果删除的段落为“偶-奇-偶”，左右都会剩下长为奇的段落，这是性质相同的子问题，如果想要完全划分，要么分出一段“奇-偶-奇”，要么在段中抽出一个合并，前者一定更劣，后者如果只合并一端，则不如把其划分为两个长为 $2$ 的段落，如果合并两端，实质是一个以奇位置开始的划分。 综上，我们一定只会删除位置为“奇-偶-奇”的段落。 完成“奇-偶-奇”的划分，只需相邻两个奇位置字符的不同，此时答案为 $\frac{len-1}{2}$。 如果所有奇位置都相同，那就不存在合适的长度为 $3$ 的划分了，接着考虑有没有长度为 $5$ 的划分，同理，我们一定选择位置为“奇-偶-奇-偶-奇”的段落。 由于奇位置完全相同，所以必须得有相邻且不同的偶位置才可以找到合法划分，如果找到，把这段划分出即可，此时答案为 $\frac{len-3}{2}$。 如果长度为 $5$ 的也找不到呢？继续枚举 $7,9\dots$ 的段长？**并不需要，因为此时我们一定无法找到长度为奇数的非回文串了**，这时直接返回无解即可。 至此，所有情况都讨论完了，可以发现，把无解和答案为 $\frac{len-3}{2}$ 的特殊情况判完后，原串能划分出的最大互不相交的非回文串数就是最后的答案。 然后就可以用贪心求解，由上述推导可知，我们此时一定能构造出一组与贪心所得答案相同的合法方案，且显然不存在更优的方案。