acm-(思維、反面、01串)Educational Codeforces Round 101 (Rated for Div. 2) E. A Bit Similar

傳送門

考慮反面，要求構造一個串使得它和每個串有至少一位相同等價于構造一個串使得與所有長度為 k k k的串取反後不同，其實隻需要考慮這些串的最後20位即可，因為 2 20 > 1 e 6 2^{20}>1e6 220>1e6，也就是說當 k ≥ 20 k\ge 20 k≥20的時候總是存在一個長度為 20 20 20的串使得它跟所有的串反面不同，這也是我們需要找的串。

由于要求串最小，那麼除了最後 20 20 20位外我們可以讓其它的位全是 0 0 0，最後 20 20 20位直接從小到大暴力枚舉看是否存在一個長度為 k k k的串的末尾 20 20 20位的取反與它相等，如果沒有的話當期那就是合法的解，輸出即可。不過需要注意的是，當這個長度為 k k k的串的除了最後 20 20 20位以外的部分假如存在一個 0 0 0那麼就可以被忽略。

#include <bits/stdc++.h>
using namespace std;


const int maxn = 2e6+5;
const int MAX = 20;
char s[maxn];
bool vis[1<<MAX];
int cnt[maxn];
vector<int>rec;
void work(int l,int r){
	int ans=0;
	for(int i=l;i<=r;++i){
		ans=ans*2+!(s[i]-'0');
	}
	if(!vis[ans])rec.push_back(ans);
	vis[ans]=true;
}
vector<int>as;
bool flag=false;
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int n,k;
		scanf("%d%d%s",&n,&k,s+1);
		for(int i=1;i<=n;++i){
			cnt[i]=cnt[i-1]+(s[i]=='0');
		}
		for(int i=1;i<=n-k+1;++i){
			if(k>MAX && cnt[i+k-MAX-1]-cnt[i-1]>=1){
				continue;
			}
			work(max(i+k-MAX,i),i+k-1);
		}
		for(int i=0;i<(1<<min(MAX,k));++i){
			if(!vis[i]){
				for(int j=1;j<=k-min(MAX,k);++j){
					as.push_back(0);
				}
				for(int j=min(MAX-1,k-1);j>=0;--j){
					if((1<<j)&i){
						as.push_back(1);
					}else as.push_back(0);
				}
				break;
			}
		}
		for(int i=0;i<rec.size();++i){
			vis[rec[i]]=false;
		}
		rec.clear();
		if(as.empty())printf("NO\n");
		else{
			printf("YES\n");
			for(int i=0;i<as.size();++i)printf("%d",as[i]);puts("");
			as.clear();
		}
	}
}