题目链接
题目大意
给你一个长度为n的01串s,要你构造一个长度为k的串t
使得串t和s中所有长度为k的子串至少有一个字符相同
并且t的字典序最小
nk 1e6
题目思路
这个算是一个思维题
其实要把这个题目转化一下
转换为找到一个字典序最小的01串且不能是这n个串的长度为k的子串的反串
还有就是20位就能决定答案,因为\(2^{20}\)>1e6
那么只要确定最后\(20\)位即可
还要注意前导的数字也要特判下
代码
#include<bits/stdc++.h>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int maxn=1e6+5,inf=0x3f3f3f3f,mod=1e9+7;
const double eps=1e-6;
int n,k,len;
bool flag;
int pre[maxn];
string s,t;
map<string,int> mp;
void dfs(int x){
if(flag){
return ;
}
if(x==len+1){
if(mp[t]==0){
cout<<"YES"<<'\n';
int rest=k-len;
while(rest--){
cout<<'0';
}
cout<<t<<'\n';
flag=1;
}
return ;
}
t.push_back('0');
dfs(x+1);
t.pop_back();
t.push_back('1');
dfs(x+1);
t.pop_back();
}
bool check(int l,int r){
if(l==0){
return pre[r]!=r-l+1;
}else{
return pre[r]-pre[l-1]!=r-l+1;
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int _;cin>>_;
while(_--){
mp.clear();
flag=0;
cin>>n>>k>>s;
flag=0;
len=min(k,20);
pre[0]=s[0]-'0';
for(int i=1;i<s.size();i++){
pre[i]=pre[i-1]+s[i]-'0';
}
for(int i=k-len;i+len-1<(int)s.size();i++){
string temp=s.substr(i,len);
for(int j=0;j<temp.size();j++){
temp[j]=(!(temp[j]-'0'))+'0';
}
if(k>len&&check(i-1-(k-len)+1,i-1)){
}else{
mp[temp]=1;
}
}
dfs(1);
if(!flag){
cout<<"NO"<<'\n';
}
}
return 0;
}