1 条题解
-
0
已知字符串 ,其中 为 去除所有
a后的结果。由于 去除a后与 相同,可以从前往后找出第一个位置,使得该位置前非a字符的个数与该位置后的总字符数相等,然后判断该位置前的子串与后缀去除a后是否一致即可,时间复杂度 。也可以通过哈希判断每个可能的分界点后缀是否匹配,时间复杂度 或 。
#include<cstdio> #include<cstring> using namespace std; const int N=1000005; char buf[N],tmp[N],res[N]; int main(){ int T; scanf("%d",&T); while(T--){ scanf("%s",buf+1); int len=strlen(buf+1),p=0; for(int i=1;i<=len;++i) if(buf[i]!='a')tmp[++p]=buf[i]; if(p==0){ puts(buf+1); continue; } if(p&1){ puts("No solution!"); continue; } bool ok=1; for(int i=1,j=p/2+1;j<=p;++i,++j) if(tmp[i]!=tmp[j]){ puts("No solution!"); ok=0; break; } if(ok){ int cnt=0,q=0,r=0; for(int i=1;i<=len;++i){ if(buf[i]!='a')++cnt; if(cnt==p/2+1){ for(int j=i;j<=len;++j) if(buf[j]=='a'){ ok=0; break; } break; } res[++q]=buf[i]; } if(ok){ for(int i=1;i<=q;++i)putchar(res[i]); putchar('\n'); } else puts("No solution!"); } } }
信息
- ID
- 222
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 3
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者