(以“分类:广度优先搜索分类:搜索与枚举 ==摘要== {{信息题|Keyword|http://acm.sgu.ru/problem.php?contest{{=}}0&problem{{=}}142|1|100|time=2015-2-...”为内容创建页面) |
小 (→摘要: 难度) |
||
第1行: | 第1行: | ||
[[分类:广度优先搜索]][[分类:搜索与枚举]] | [[分类:广度优先搜索]][[分类:搜索与枚举]] | ||
==摘要== | ==摘要== | ||
− | {{信息题|Keyword|http://acm.sgu.ru/problem.php?contest{{=}}0&problem{{=}}142| | + | {{信息题|Keyword|http://acm.sgu.ru/problem.php?contest{{=}}0&problem{{=}}142|2|100|time=2015-2-15 23:54:21}} |
(AC 1237) | (AC 1237) | ||
+ | |||
==题意== | ==题意== | ||
已知一个只有a,b的字符串,求最短的只有a,b的非子串。 | 已知一个只有a,b的字符串,求最短的只有a,b的非子串。 |
题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 需要注意 |
---|---|---|---|---|---|
Keyword | ★★☆☆☆ | 答案正确 | 100 | 2015-2-15 23:54:21 | 无 |
(AC 1237)
已知一个只有a,b的字符串,求最短的只有a,b的非子串。
感觉像是枚举,但是直接枚举500W肯定T,所以需要缩小枚举范围。我们容易知道:
由n≤500000,要保证(3),只要,由单调性知道L≥19。也就是说,L=19时,一定能保证存在要求的解[1]。 容易知道,这在可枚举范围内,用类似广搜的方式枚举即可(或者二进制压位直接枚举)。
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; } } |