自动搬运

查看原文

来自洛谷，原作者为

	JHPOTATO 那也请不要忘记 落泪的眼睛 曾动容的心情

搬运于2025-08-24 21:18:39，当前版本为作者最后更新于2025-04-03 11:55:41，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

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

那么长度不小于 $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$ 必然交替出现。

$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}$ 的特殊情况判完后，原串能划分出的最大互不相交的非回文串数就是最后的答案。

然后就可以用贪心求解，由上述推导可知，我们此时一定能构造出一组与贪心所得答案相同的合法方案，且显然不存在更优的方案。