1469E - A Bit Similar

题意:给定一个长度为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处理。

#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;
}