蓝桥杯 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;
}