本文主要是介绍题解:CF1951E(No Palindromes),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题解:CF1951E(No Palindromes)
题目翻译:给定一个长度为 n n n 的字符串 s s s,询问是否可以将其分成若干份,使得每一份都不是回文串。若可以,输出 YES
并给出任意一组方案;若不可以,则直接输出 NO
。其中,数据多测,共 t t t 组,保证 ∑ n ≤ 1 0 6 \sum n\leq10^6 ∑n≤106。
先观察数据范围,1e6
级别,基本上就是 O ( n ) O(n) O(n) 的,看来是一道结论题。
为了之后表述方便,我们不妨将字符串分成若干个部分,使得每个部分中的字符都相同且相邻两个部分的字符不相等。记这样的部分数为 c n t cnt cnt,记第 i i i 个部分为 x i x_i xi。
于是,我们开始分情况讨论:
- 当 c n t cnt cnt 为偶数时,不难证明,整个字符串一定不是一个回文串,因此可以分,整体分成一份即可。当然,我们将它的奇数段和偶数段两两搭配分在一起也是可以的。
- 当 c n t = 1 cnt=1 cnt=1 时,显然无论怎么分,每一段内的字母都一定相同,因此不可以分。
- 当 c n t cnt cnt 为奇数( 1 1 1 除外)时,我们要想能分成,要么将奇数个段(显然 1 1 1 除外)分在一起,要么将某一段拆开,还需要继续分类:
-
- 当存在 1 ≤ i ≤ c n t − 2 1\leq i\leq cnt-2 1≤i≤cnt−2,使得 x i = x i + 2 x_i=x_{i+2} xi=xi+2 时,那一定可以分(就是用第 i d id id、 i d + 1 id+1 id+1 和 i d + 2 id+2 id+2 段组成前面所说的“奇数个段”),但是怎么分还要分类(记我们找到的其中任意一个 i i i 为 i d id id):
-
-
- 当 i d id id 为偶数时,在第 i d id id 段之前有偶数个段,我们将其奇数段和偶数段两两搭配;对于中间,我们将第 i d id id、 i d + 1 id+1 id+1 和 i d + 2 id+2 id+2 段分在一起;对于第 i d + 2 id+2 id+2 之后也有偶数个段,我也是时将其奇数段和偶数段两两搭配。
-
-
-
- 当 i d id id 为奇数时,在第 i d − 1 id-1 id−1 段之前有偶数个段,我们将其奇数段和偶数段两两搭配;对于中间,我们将第 i d − 1 id-1 id−1、 i d id id、 i d + 1 id+1 id+1、 i d + 2 id+2 id+2 和 i d + 3 id+3 id+3 段分在一起;对于第 i d + 3 id+3 id+3 之后也有偶数个段,我也是时将其奇数段和偶数段两两搭配。
-
-
- 当不存在 1 ≤ i ≤ c n t − 2 1\leq i\leq cnt-2 1≤i≤cnt−2,使得 x i = x i + 2 x_i=x_{i+2} xi=xi+2 时,给定字符串一定是由两种段交替组成的,我们需要继续分类(记其中第奇数段的字符数量为 u u u,第偶数段的字符数量为 v v v):
-
-
- 当 u = v = 1 u=v=1 u=v=1 时,由于总段数 c n t cnt cnt 为奇数,而任何一段都不可能被拆成两半,因此最终的字符串一定被分成两份,分别有奇数个段和偶数个段组成,显然那个由奇数个段组成的一部分一定是回文串,因此不可以分。
-
-
-
- 当 v ≠ 1 v\neq 1 v=1 时,第 2 2 2 段可以被拆成两半,因此可以分,将其第一个字符与前面的第 1 1 1 段分成一部分,第 2 2 2 段的剩余的部分与它右侧所有剩余字符分成另一部分。
-
-
-
- 当 v = 1 v=1 v=1 且 u ≠ 1 u\neq 1 u=1 时,再分情况:
-
-
-
-
- 当 c n t = 3 cnt=3 cnt=3 时,只有第 1 1 1 段和第 3 3 3 段可以拆开,此时一定有一部分中所有字符相同,因此不能分。
-
-
-
-
-
- 当 c n t > 3 cnt>3 cnt>3 时,将第 3 3 3 部分拆成两半,就可以分,分法与上面的“当 v ≠ 1 v\neq 1 v=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
,请不要恼火,慢慢核对,看看有没有哪里写错了,相信你能调对!
这篇关于题解:CF1951E(No Palindromes)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!