(以“分类:广度优先搜索分类:搜索与枚举 ==摘要== {{信息题|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|1|100|time=2015-2-15 23:54:21}}
+
{{信息题|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的非子串。

2015年2月16日 (一) 16:06的最后版本

摘要

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

(AC 1237)

题意

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

题解

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

  1. 对于长度为n的字符串,最多只有M_1=n-L+1个长度为L的子串;
  2. 长度为L的串一共有M_2=2^L个;
  3. M_1<M_2n<2^L+L-1的时候,根据抽屉原理,该字符串一定存在长度为L的非子串;

由n≤500000,要保证(3),只要2^L+L-1\geq500000,由单调性知道L≥19。也就是说,L=19时,一定能保证存在要求的解[1]。 容易知道2^{19}=524288,这在可枚举范围内,用类似广搜的方式枚举即可(或者二进制压位直接枚举)。

代码

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;
            }
}


参考资料和拓展阅读

  1. http://wenku.baidu.com/link?url=ErBAJnhqgrHq_mvy2dNmPMvlJNQ5SwsHoILjFv-47Ae24q4aDJTgo8gWSPnY89rxfYaS0Zkl5DByoEQiKoBoImxdAHPZ74iUNewCAyQ9yXa

著作权声明[编辑]

关于[编辑]