CF 1469E - A Bit Similar
littlechai
2020-12-30 15:48:03
[1469E - A Bit Similar](http://codeforces.com/contest/1469/problem/E)
题意：给定一个长度为n的01串s，求字典序最小的长度为k的01串，使得与s的所有长度为k的子串至少有一位相同，1 <= k <= n <= 1e6.
思路：考虑该串与s所有子串都不相同的情况，除了这些情况其它都能满足。一个长度为k的01串，可能的情况有2^k种，s的子串有n-k种，所以当2^k > n-k 时必存在满足条件的s，简化一下2^k >= n时答案必存在，因为n <= 1e6,当k >= 20 时，答案必存在，因此我们可以只考虑该串的后20位，对于串的后20位前直接填0，然后暴力枚举后20位看那种情况符合即可，01串可用2进制hash处理。
```cpp
#include<bits/stdc++.h>
#define ri register int
#define ll long long
#define lson rt << 1, l, mid
#define rson rt << 1|1, mid+1, r
using namespace std;
void re(int &x){
x = 0;
int b = 0;
char ch = getchar();
while(ch < '0' || ch > '9'){
if(ch == '-') b = 1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = (x << 1) + (x << 3) + ch - '0';
ch = getchar();
}
if(b == 1)
x *= -1;
}
const int maxn = 1100000;
const int p = 998244353;
int n, t, q, k;
int pw[maxn], has[maxn], a[maxn], num[maxn];
int ban[maxn];
char s[maxn];
int hashup(int l, int r){
return (has[r] - (ll)has[l-1] * pw[r-l+1] % p + p)%p;
}
void solve(){
for(int i = 1;i+k-1 <= n;i ++){
int x = hashup(max(i, i+k-20), i+k-1);
if(k > 20 && num[i+k-20] - num[i-1] > 0) continue;
if(x > 1e6) continue;
ban[x] = 1;
}
int x = -1, r = (1<<min(k, 21)) - 1;
for(int i = 0;i <= r;i ++){
if(!ban[i]){
x = i;
break;
}
}
string ans = "";
if(k >= 20) for(int i = 20;i <= k;i ++) ans += "0";
r = min(19, k);
for(int i = r-1;i >= 0;i --){
if(x&(1<<i)) ans += "1";
else ans += "0";
}
if(x != -1){
puts("YES");
cout << ans << endl;
}
else puts("NO");
}
int main(){
re(t);
pw[0] = 1;
for(int i = 1;i <= 30;i ++)
pw[i] = pw[i-1] * 2%p;
while(t --){
re(n), re(k);
scanf("%s",s+1);
memset(ban, 0, sizeof(ban));
for(int i = 1;i <= n;i ++){
a[i] = (s[i] == '0');
has[i] = (has[i-1]*2%p + a[i]) % p;
num[i] = num[i-1] + a[i];
}
solve();
}
return 0;
}
```