（以“分类:广度优先搜索分类:搜索与枚举 ==摘要== {{信息题|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;
}
}
|
CloudLunar