原题链接qaq
倒垃圾（bushi）：
阴间题，赛时PP了以为稳极，谁知道第二天一早醒来就收到了被叉的噩耗/fn
会被叉的思路：
我一看，$n$ 不超 $1e6$ ，那么我们大可直接枚举子串（ $1e6$ 级别），从而刷出一些“危险”的串，即与某个长度为 $k$ 的子串 没有任何一位相同 的串。
因为这是一个可爱的01串，所以直接取反串即可（这个反串说的是每位 取反 后的串）。
把这些危险串存起来，显然这些串一共也不超过 $1e6$ 个。也就是说，必然存在一个 $20$ 位的 $01$ 串，和这些危险串互异。（ $2^{20}>1e6$ ）
很舒适，那么直接枚举这个 $01$ 串即可。确保了最后 $20$ 位的 “A bit similar” 之后，其它的位上我们就可以 自由发挥 了。
它让我们取最小字典序，那么我们只需在其他位上都填 $0$ 即可。
这太简单了叭，我也能有一天 $1h$ 不到切E题，蛤蛤蛤蛤蛤……
真的如此吗？
我为什么又又又又被叉了：
考虑我们“自由发挥”的时候，我们把一些位置填上了 $0$ 。
但是当我们把这些位置填上 $0$ 的时候，是否想过，如果在这里填 $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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
| #include <bits/stdc++.h>
using namespace std;
const int MAX = 4e6 + 7;
int N, M;
string s;
int dan[MAX];
int ok[MAX];
void solve(int T)
{
cin >> N >> M >> s;
int st = max(0, M - 20);
string ans = "";
for (int i = 0; i < st; i++)
{
ans += "0";
}
if (st > 0)
{
int j = 0;
for (int i = 0; i < N; i++)
{
if (s[i] == '0')
{
j = max(i - st + 1, j);
while (j <= i)
{
ok[j] = T;
j++;
}
}
}
}
for (int i = 0; i + M <= N; i++)
{
if (ok[i] == T)
continue;
int cur = 0;
for (int j = st; j < M; j++)
{
cur = cur * 2 + s[i + j] - '0';
}
dan[cur] = T;
}
for (int mask = 0; mask < (1 << (M - st)); mask++)
{
if (dan[mask ^ ((1 << (M - st)) - 1)] == T)
continue;
cout << "YES\n";
cout << ans;
for (int i = M - 1; i >= st; i--)
{
if (mask & (1 << (i - st)))
{
cout << 1;
}
else
{
cout << 0;
}
}
cout << "\n";
return;
}
cout << "NO\n";
}
int main()
{
int T = 1;
cin >> T;
for (int i = 1; i <= T; i++)
{
solve(i);
}
return 0;
}
|
这样你就通过了这道题～
花絮：
