题目描述
FST是一名可怜的 OIer，他很强，但是经常 fst，所以 rating 一直低迷。
但是重点在于，他真的很强！他发明了一种奇特的加密方式，这种加密方式只有OIer
才能破解。
这种加密方式是这样的：对于一个 01 串，他会构造另一个 01 串，使得原串是在新串中没有出现过的最短的串。
现在 FST 已经加密好了一个串，但是他的加密方式有些 BUG ，导致没出现过的最短的串不止一个，他感觉非常懊恼，所以他希望计算出没出现过的最短的串的长度。
输入格式
一行，一个 01 串。
输出格式
一行，一个正整数，表示没有出现过的最短串的长度。
样例数据
输入
100010110011101
输出
4
备注
【数据范围】
测试点 1、2、3 的串长度≤
测试点 3、4、5 的串长度≤
测试点 6、7、8、9、10 的串长度≤
分析：我们可以发现，17位的01串已经有
我在考场上采取的是for循环第一层扫整个字符串，第二层枚举1——17位，然后再来找标记。其实，第一层枚举1——17位，第二层扫整个字符串可以把我的两步合成一步，而且可以不用二维数组，更加简洁。
注意：17位字符串最大是11111111111111111，开数组要开到
代码：
我的做法
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<ctime>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<iomanip>
#include<queue>
#include<set>
using namespace std;
int getint()
{
int sum=0,f=1;
char ch;
for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
if(ch=='-')
{
f=-1;
ch=getchar();
}
for(;ch>='0'&&ch<='9';ch=getchar())
sum=(sum<<3)+(sum<<1)+ch-48;
return sum*f;
}
int lens;
bool bj[280000][20],bjwan;//就是bj数组的第一维开小了！
char s[100010];
int main()
{
freopen("fst.in","r",stdin);
freopen("fst.out","w",stdout);
scanf("%s",s+1);
lens=strlen(s+1);
int sum;
for(int i=1;i<=lens;++i)
{
sum=0;
for(int j=0;j<=min(17,lens-i);++j)//枚举17位，把它们转化成十进制打标记，bj[i][j]表示十进制值为i的01串长度为j（因为可能0开头，要记一下长度）
{
sum=(sum<<1)+s[i+j]-'0';
bj[sum][j+1]=1;
}
}
for(int j=1;j<=18;++j)//再扫一遍位数，可以找到没有的最小01串
for(int i=0;i<=((1<<j)-1);++i)
{
if(bj[i][j]==0)
{
cout<<j<<endl;
return 0;
}
}
}把我的两个部分合并的代码（并且加了二分来优化，这样只需要扫描4种长度的01串了）
#include<iostream>
#include<cstring>
#include<string>
#include<cstdlib>
#include<cstdio>
#include<ctime>
#include<queue>
#include<set>
#include<map>
#include<cctype>
#include<iomanip>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1e5+10;
long long num,len,tot,a[maxn],s[20],d,b,ans;
bool check1[maxn];
char ss[maxn];
int ksm(int y)
{
int ret=1;
for(int x=2;y;x*=x,y/=2)
if(y&1) ret*=x;
return ret;
}
int zjz()
{
int mi=1,sum=0;
sum=s[len-1];
for(int i=len-2;i>=0;i--)
{
mi=mi*2;
sum=sum+s[i]*mi;
}
return sum;
}
bool check(int x)
{
num=0;
d=ksm(x);
if(d>tot) return false;
memset(check1,false,sizeof(check1));
for(int i=1;i<=tot-x+1;i++)
{
len=0;
memset(s,0,sizeof(s));
for(int j=i;j<=i+x-1;j++)
s[len++]=a[j];
b=zjz();
if(check1[b]==false)
{
num++;
check1[b]=true;
}
}
if(num<d) return false;
if(num==d) return true;
}
int half()
{
int l=1,r=20,mid;
while(l<=r)
{
mid=(l+r)>>1;
if(check(mid)==true)
l=mid+1;
else
r=mid-1;
}
return l;
}
int main()
{
freopen("fst.in","r",stdin);
freopen("fst.out","w",stdout);
scanf("%s",ss+1);
tot=strlen(ss+1);
for(int i=1;i<=tot;i++)
a[i]=ss[i]-'0';
ans=half();
printf("%I64d",ans);
return 0;
}本题结。