DDOSvoid's Blog

CF 1469E A Bit Similar

发表于 分类于
本文字数： 1.3k 阅读时长 ≈ 1 分钟

题目描述

https://codeforces.com/contest/1469/problem/E

Solution

我们注意到至少有一位相同，实际上就某一个串 $01reverse$ 之后，两个串不同

那么问题就转换成了给你 $n-k+1$ 个串，找一个字典序最小的串与这 $n-k+1$ 个串不同

注意到 $n$ 很小，所以我们只需要考虑后 $20$ 个位置即可，因为 $n\le 2^{20}$

所以我们直接暴力枚举后 $20$ 位是什么，前面填 $0$ 即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define maxn 1000010
using namespace std;

int n, m;

char s[maxn];

int pre[maxn];

bool ban[maxn];

void work() {
    cin >> n >> m >> s + 1;
    vector<int> a; int v = 0, len = min(20, m), M = (1 << len) - 1;
    for (int i = 1; i <= n; ++i) pre[i] = pre[i - 1] + (s[i] == '1'); 
    for (int i = 1; i < len; ++i) v = v * 2 + '1' - s[i];
    for (int i = len; i <= n; ++i) {
        v = v << 1 & M; v += '1' - s[i]; 
        if (i >= m && pre[i - len] - pre[i - m] == m - len) a.push_back(v), ban[v] = 1; 
    }
    bool ok = 0; vector<int> ans;
    for (int i = 1; i <= m - len; ++i) ans.push_back(0); 
    for (int i = 0; i <= M; ++i)
        if (!ban[i]) {
            for (int o = len - 1; ~o; --o) ans.push_back(i >> o & 1);
            ok = 1; break; 
        }
    for (auto u : a) ban[u] = 0; 
    if (!ok) cout << "NO\n";
    else {
        cout << "YES\n"; 
        for (auto u : ans) cout << u;
        cout << "\n"; 
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T;
    while (T--) work(); 
    return 0;
}