题解：CF1951E No Palindromes

· · 题解

省流：屎山。

调死了，开心。

注：本文下标均从 1 开始，下文可能不会特地声明。

我们把字符串转化成一个一个由相同字母组成的块，记录块长，存进一个 vector 里，我们把第 i 块的块长称作 x_i。

注意到相邻块代表的字母一定不同，所以把两个块接在一起肯定不是回文串。那么我们可以得出当块数为偶数时一定可解，将两个块接在一起即可。

那么剩下的情况块数均为奇数，我们考虑如何转化为偶数。

我们有如下四条结论可以帮助转化。

结论一：如果存在 x_i \ne x_{i+2} 或者这两者代表的字母不同，那么把 x_i,x_{i+1},x_{i+2} 所代表的块连接起来一定不是回文串。

证明：

设 x_i,x_{i+1},x_{i+2} 所代表的块连接起来是回文串 s，且下标从 1 开始。

同时我们设 x_i,x_{i+1},x_{i+2} 所代表的块分别由若干 a，若干 b，若干 c 所组成，且在 s 中的位置分别是 s_1 到 s_{x_i}，s_{x_i+1} 到 s_{x_i+x_{(i+1)}}，s_{x_i+x_{(i+1)}+1} 到 s_{x_i+x_{(i+1)}+x_{(i+2)}}，且 a\ne b,b\ne c。

显然当 a \ne c 时结论成立。

接下来处理 a=c 的情况。这些情况满足 x_i\ne x_{i+2}。

依据上面我们有 |s|=x_i+x_{i+1}+x_{i+2}。

当 x_i<x_{i+2} 时：

那么 s_{x_i+1} = s_{|s|-x_i} = s_{x_{(i+1)}+x_{(i+2)}}。

因为 x_i<x_{i+2}。

所以 s_{x_{(i+1)}+x_{(i+2)}}=c。

因为 s_{x_i+1}=b,b\ne c。

所以 s_{x_i+1}\ne s_{x_{(i+1)}+x_{(i+2)}}。

自相矛盾，所以 s 不是回文串。

当 x_i>x_{i+2} 时：

因为 s 是回文串，所以设 c 是反转后的 s。

此时有 c=s。

那么对于 c 满足 x_i<x_{i+2}。

所以 c 不是回文串。

由此可知 s 也不是回文串。

综上，结论成立。

怎么这段这么长……

结论二：如果存在 x_i \ne x_{i+2} 或者这两者代表的字母不同，那么把 x_{i-1},x_i,x_{i+1},x_{i+2},x_{i+3} 所代表的块连接起来的 s 一定不是回文串。

证明：

设 s 是回文串，五个块的成分分别是若干个 a，若干个 b，若干个 c，若干个 d，若干个 e。

如果 b \ne d 结论显然成立。

那么设 a=e。

首先由结论一可以知道，s_{x_{(i-1)}+1} 到 s_{x_{(i-1)}+x_i+x_{(i+1)}+x_{(i+2)}} 不是回文串。

因为 e \ne d,a\ne b。

所以 e\ne b,a\ne d。

那么显然没法补齐中间不是回文串的部分。

所以 s 不是回文串。

综上，结论成立。

对于一个不存在 x_i \ne x_{i+2} 或者这两者代表的字母不同的字符串 s，也就是说这个字符串形如 AB...A，其中 A,B 各代表一类块。

结论三：在满足上述条件且 B>1 时，我们可以把第二个 B 的中间作为分割，这样割出来的两个串均不回文。

结论四：在满足上述条件且 A>1，块数大于 1 时，我们可以把第三个 A 的中间作为分割，这样割出来的两个串均不回文。

证明：

结论三的割法使两个串头尾字符不一，显然不回文。

结论四的割法使两个串头尾长度不一，根据结论一的证明，同理可得结论四也是正确的。

那我们应该怎么构造呢？

首先找出一个满足 x_i \ne x_{i+2} 或者这两者代表的字母不同的 i。

如果不存在这么一个 i，检查是否满足结论三结论四的条件，满足的照做即可。不满足的显然不可做，返回无解。

剩下的情况把 i 按照情况一来做，其余部分是偶数，按照初始情况两两一组即可。

但是这不对。废话那我要情况二干嘛？

当 i 是偶数时，你会发现左右都是奇数，假了。

所以此时按照结论二做即可，因为是五合一，所以刚刚好。

然后你就可以开始调屎山了。

调试之你可能会犯的错误：

越界，如忘记判队列 ans.empty()。这是 UB 的重要原因，CF 不会返回 RE 返回 WA on #2 就很神奇。

多测注意清空，不然见祖宗。

变量不重名。不过这好像没什么关系。

还有就是虽然本文下标从 1 开始但是注意 string 下标从 0 开始！！！！

上述问题不要问我怎么知道的，问就是第一张图。

AC 代码。

拜谢 @tanglb 帮我调题！