Sgu/142 2015年2月16日 (一) 16:06云璟月（讨论 | 贡献）的版本 (差异) ←上一版本 | 最后版本 (差异) | 下一版本→ (差异)

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	需要注意
Keyword	★★☆☆☆	答案正确	100	2015-2-15 23:54:21	无

（AC 1237）

题意

已知一个只有a,b的字符串，求最短的只有a,b的非子串。

题解

感觉像是枚举，但是直接枚举500W肯定T，所以需要缩小枚举范围。我们容易知道：

1. 对于长度为n的字符串，最多只有个长度为L的子串；
2. 长度为L的串一共有个；
3. 当即的时候，根据抽屉原理，该字符串一定存在长度为L的非子串；

由n≤500000，要保证(3)，只要，由单调性知道L≥19。也就是说，L=19时，一定能保证存在要求的解。 容易知道，这在可枚举范围内，用类似广搜的方式枚举即可（或者二进制压位直接枚举）。

代码

142.cpp代码已折叠 展开折叠内容

#include<cstdio> #include<string> #include<iostream> bool b[500001]={},a[20][(1<<19)+1]={}; int main() { int n; scanf("%d\n",&n); char c; for(int i=1;i<=n;++i) b[i]=(getchar()=='b'); for(int i=1;i<=n;++i) { int t=0; for(int j=1;j<=19&&i+j-1<=n;++j) { t<<=1; t|=b[i+j-1]; a[j][t]=1; } } for(int w=1;w<=19;++w) for(int i=0;i<(1<<w);++i) if(!a[w][i]) { std::string c=""; for(int t=1;t<=w;++t) { if(i&1) c='b'+c; else c='a'+c; i>>=1; } std::cout<<w<<std::endl<<c; return 0; } }