Educational Codeforces Round 101 (Rated for Div. 2) E

题目传送门
很巧妙的一道题。对于一个 (n)位的 (01)字符串，一共有 (2^n)种不同字符排列，对于任意一个固定排列，在 (2^n)种排列中只有一种排列与该固定排列处处不等，而题干中的串长不超过 (1e6)，小于 (2^{20})，也就是说所有长度为 (20)的子串不超过 (1e6)个，那我们只用让答案串的后 (20)位取一个与所有长度为 (20)的子串都“相交”的排列，前面都取 (0)，这样字典序最小。
记录下每个长度为 (20)的子串它的排斥串，然后枚举 ([1,1<<20))找到最小的非排斥串作为答案串后 (20)位。注意只有遇见超过 (k-20)个连续 (1)时才记录排斥串，然后可能 (k)小于 (20)所以要取 (min(k,20))。

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 1e6 + 5;

int T, n, k;
char s[N];
bool vis[N];

void solve(){
    scanf("%d%d%s", &n, &k, s + 1);
    int kk = min(k, 20);
    vector<bool> rej(1 << kk, 0);
    
    for(int i = 1, num = 0; i <= n - kk + 1; ++i){
        if(num >= k - kk){
            int sta = 0;
            for(int t = 0; t < kk; ++t){
                sta = sta * 2 + (s[i + t] != '1');
            }
            rej[sta] = 1;
        }
        num = (s[i] == '1' ? num + 1 : 0);
    }

    for(int i = 0; i < (1 << kk); ++i){
        if(!rej[i]){
            puts("YES");
            for(int t = 1; t <= k - kk; ++t)  putchar('0');
            for(int t = kk - 1; ~t; --t)  putchar((i & (1 << t)) ? '1' : '0');
            puts("");
            return ;
        }
    }
    puts("NO");
}

int main(){
    scanf("%d", &T);
    while(T--)  solve();
    return 0;
}