CF1951ENo_Palindromes_0">题解：CF1951E（No Palindromes）

题目翻译：给定一个长度为 $n$ 的字符串 $s$，询问是否可以将其分成若干份，使得每一份都不是回文串。若可以，输出 YES 并给出任意一组方案；若不可以，则直接输出 NO。其中，数据多测，共 $t$ 组，保证 $\sum n\le 10^6$。

先观察数据范围，1e6 级别，基本上就是 $O(n)$ 的，看来是一道结论题。

为了之后表述方便，我们不妨将字符串分成若干个部分，使得每个部分中的字符都相同且相邻两个部分的字符不相等。记这样的部分数为 $cnt$，记第 $i$ 个部分为 $x_i$。

于是，我们开始分情况讨论：

• 当 $cnt$ 为偶数时，不难证明，整个字符串一定不是一个回文串，因此可以分，整体分成一份即可。当然，我们将它的奇数段和偶数段两两搭配分在一起也是可以的。
• 当 $cnt=1$ 时，显然无论怎么分，每一段内的字母都一定相同，因此不可以分。
• 当 $cnt$ 为奇数（$1$ 除外）时，我们要想能分成，要么将奇数个段（显然 $1$ 除外）分在一起，要么将某一段拆开，还需要继续分类：
• • 当存在 $1\le i\le cnt-2$，使得 $x_i=x_{i+2}$ 时，那一定可以分（就是用第 $id$、$id+1$ 和 $id+2$ 段组成前面所说的“奇数个段”），但是怎么分还要分类（记我们找到的其中任意一个 $i$ 为 $id$）：
• • • 当 $id$ 为偶数时，在第 $id$ 段之前有偶数个段，我们将其奇数段和偶数段两两搭配；对于中间，我们将第 $id$、$id+1$ 和 $id+2$ 段分在一起；对于第 $id+2$ 之后也有偶数个段，我也是时将其奇数段和偶数段两两搭配。
• • • 当 $id$ 为奇数时，在第 $id-1$ 段之前有偶数个段，我们将其奇数段和偶数段两两搭配；对于中间，我们将第 $id-1$、$id$、$id+1$、$id+2$ 和 $id+3$ 段分在一起；对于第 $id+3$ 之后也有偶数个段，我也是时将其奇数段和偶数段两两搭配。
• • 当不存在 $1\le i\le cnt-2$，使得 $x_i=x_{i+2}$ 时，给定字符串一定是由两种段交替组成的，我们需要继续分类（记其中第奇数段的字符数量为 $u$，第偶数段的字符数量为 $v$）：
• • • 当 $u=v=1$ 时，由于总段数 $cnt$ 为奇数，而任何一段都不可能被拆成两半，因此最终的字符串一定被分成两份，分别有奇数个段和偶数个段组成，显然那个由奇数个段组成的一部分一定是回文串，因此不可以分。
• • • 当 $v\ne 1$ 时，第 $2$ 段可以被拆成两半，因此可以分，将其第一个字符与前面的第 $1$ 段分成一部分，第 $2$ 段的剩余的部分与它右侧所有剩余字符分成另一部分。
• • • 当 $v=1$ 且 $u\ne 1$ 时，再分情况：
• • • • 当 $cnt=3$ 时，只有第 $1$ 段和第 $3$ 段可以拆开，此时一定有一部分中所有字符相同，因此不能分。
• • • • 当 $cnt>3$ 时，将第 $3$ 部分拆成两半，就可以分，分法与上面的“当 $v\ne 1$ 时”类似，这里不再赘述。

于是，我们通过一大片子的分类讨论解决了这道题。

还是给个代码吧！

#include<bits/stdc++.h>
#define N 1100000
#define fors(i,b,e) for(int i=b;i<=e;i++)
#define fst first
#define scd second
#define pb push_back
using namespace std;
int t;
char s[N];
int n;
pair<char,int>x[N];
bool operator==(pair<char,int>x,pair<char,int>y);
int main(){scanf("%d",&t);while(t--){scanf("%s",s+1);n=strlen(s+1);int cnt=0;fors(i,1,n){if(i==1||s[i]!=s[i-1])cnt++,x[cnt]={s[i],1};else x[cnt].scd++;}if(cnt%2==0)printf("YES\n1\n%s\n",s+1);else if(cnt==1)printf("NO\n");else{int id=0;fors(i,1,cnt-2)if(x[i]!=x[i+2]){id=i;break;}if(id!=0){if(id%2==1){printf("YES\n%d\n",cnt/2);for(int i=1;i+1<id;i+=2){fors(j,1,x[i+0].scd)printf("%c",x[i+0].fst);fors(j,1,x[i+1].scd)printf("%c",x[i+1].fst);printf(" ");}fors(i,0,2)fors(j,1,x[id+i].scd)printf("%c",x[id+i].fst);printf(" ");for(int i=id+3;i+1<=cnt;i+=2){fors(j,1,x[i+0].scd)printf("%c",x[i+0].fst);fors(j,1,x[i+1].scd)printf("%c",x[i+1].fst);printf(" ");}printf("\n");}else{printf("YES\n%d\n",cnt/2-1);for(int i=1;i+1<id-1;i+=2){fors(j,1,x[i+0].scd)printf("%c",x[i+0].fst);fors(j,1,x[i+1].scd)printf("%c",x[i+1].fst);printf(" ");}fors(i,-1,3)fors(j,1,x[id+i].scd)printf("%c",x[id+i].fst);printf(" ");for(int i=id+4;i+1<=cnt;i+=2){fors(j,1,x[i+0].scd)printf("%c",x[i+0].fst);fors(j,1,x[i+1].scd)printf("%c",x[i+1].fst);printf(" ");}printf("\n");}}else{int u=x[1].scd,v=x[2].scd;if(u==1&&v==1)printf("NO\n");else if(v!=1){printf("YES\n2\n");fors(i,1,u)printf("%c",x[1].fst);printf("%c ",x[2].fst);fors(i,2,v)printf("%c",x[2].fst);fors(i,3,cnt)fors(j,1,x[i].scd)printf("%c",x[i].fst);printf("\n");}else{if(cnt==3)printf("NO\n");else{printf("YES\n2\n");fors(i,1,u)printf("%c",x[1].fst);fors(i,1,v)printf("%c",x[2].fst);printf("%c ",x[3].fst);fors(i,2,u)printf("%c",x[3].fst);fors(i,4,cnt)fors(j,1,x[i].scd)printf("%c",x[i].fst);printf("\n");}}}}}return 0;
}
bool operator==(pair<char,int>x,pair<char,int>y){return x.fst==y.fst&&x.scd==y.scd;
}

注意：
如果你信心满满地写了一个自以为十分正确的代码提交上去却 Wrong answer on test 2，请不要恼火，慢慢核对，看看有没有哪里写错了，相信你能调对！