查看Sgu/142的源代码 ←Sgu/142

[[分类:广度优先搜索]][[分类:搜索与枚举]]
==摘要==
{{信息题|Keyword|http://acm.sgu.ru/problem.php?contest{{=}}0&problem{{=}}142|2|100|time=2015-2-15 23:54:21}}
（AC 1237）

==题意==
已知一个只有a,b的字符串，求最短的只有a,b的非子串。
==题解==
感觉像是枚举，但是直接枚举500W肯定T，所以需要缩小枚举范围。我们容易知道：
#对于长度为n的字符串，最多只有<m>M_1=n-L+1</m>个长度为L的子串；
#长度为L的串一共有<m>M_2=2^L</m>个；
#当<m>M_1<M_2</m>即<m>n<2^L+L-1</m>的时候，根据抽屉原理，该字符串一定存在长度为L的非子串；
由n≤500000，要保证(3)，只要<m>2^L+L-1\geq500000</m>，由单调性知道L≥19。也就是说，L=19时，一定能保证存在要求的解<ref>http://wenku.baidu.com/link?url=ErBAJnhqgrHq_mvy2dNmPMvlJNQ5SwsHoILjFv-47Ae24q4aDJTgo8gWSPnY89rxfYaS0Zkl5DByoEQiKoBoImxdAHPZ74iUNewCAyQ9yXa</ref>。
容易知道<m>2^{19}=524288</m>，这在可枚举范围内，用类似广搜的方式枚举即可（或者二进制压位直接枚举）。
==代码==
{{折叠|142.cpp代码已折叠
|<pre>
#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;
            }
}
</pre>
|sgu142}}

==参考资料和拓展阅读==
<references/>