蓝桥杯-1.-缺失的环节算法赛
目录
蓝桥杯 1. 缺失的环节【算法赛】
水题.
先考虑朴素想法,枚举len从1到n,然后内部循环枚举.设枚举开始时值为x
这个时候发现,
只需要对x去掉最高位(如果为1),然后左移一位,再加上右面新增位就可以获得下一位值
显然有pow(2,len) > n - len + 1时必然有解.那么右边看成n放缩下,差不多就是logn时
时间复杂度O(n * logn)显然可以过.
代码
#include<iostream>
using namespace std;
string s;
int n;
const int N = 1e5+10;
bool vis[N];
int main()
{
scanf("%d",&n);
cin>>s;
s = " " + s;
for(int len = 1; len<=n; len++)
{
int cur =0;
for(int i =1; i<= len; i++)
{
cur = (cur<<1) + s[i] - '0';
}
vis[cur] = true;
for(int i = len + 1; i<= n; i++)
{
if((cur>>(len-1)) & 1)
cur -= 1 << (len-1);
cur<<=1;
cur += s[i] - '0';
vis[cur] = true;
}
if(len == 1 && vis[0] == false)
{
cout<<0<<endl;
return 0;
}
for(int i = 1<<(len-1); i< 1<<len; i++)
{
if(vis[i])
continue;
cout<<i<<endl;
return 0;
}
}
return 0;
}