BZOJ4179 - B

今天模拟赛的第二题,还是大水题,但是由于 SPFA 打错调了好久,还有这个 SB 出题人怎么说都不说一句读入的 $L$ 是 long long 范围的啊,你™咋不上高精

好了,回归正常的题解。本题可以理解为 POI2000 病毒 的加强版(连样例都一样),于是按照惯例,我们只需要建造一棵 AC 自动机。如果能够找到环,那么一定能够产生无限长度的答案串,直接输出 Yes 即可。否则就是一棵 DAG ,跑一下 SPFA (或 BFS)求出最长的答案串,和要求的 $L$ 比较一下就好。

我不会说我写了个 SPFA 还写挂调了两个小时的…

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
// =================================
// author: memset0
// date: 2019.01.07 08:46:27
// website: https://memset0.cn/
// =================================
#include <bits/stdc++.h>
#define ll long long
namespace ringo {
template <class T> inline void read(T &x) {
x = 0; register char c = getchar(); register bool f = 0;
while (!isdigit(c)) f ^= c == '-', c = getchar();
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
if (f) x = -x;
}
template <class T> inline void print(T x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) print(x / 10);
putchar('0' + x % 10);
}
template <class T> inline void print(T x, char c) { print(x), putchar(c); }

const int N = 1e5 + 10, M = 2e6 + 10;
int n, x, tot, q[M], dis[M];
bool inq[M], vis[M], found[M], find_answer;
char a[N];
ll m;

struct node {
int ch[2], fail;
bool tag;
} e[M];

void insert(char *a) {
int len = strlen(a), p = 1;
for (int i = 0, x; i < len; i++) {
x = a[i] == 'A' ? 0 : 1;
if (!e[p].ch[x]) e[p].ch[x] = ++tot;
p = e[p].ch[x];
}
e[p].tag = 1;
}

void build_fail() {
std::queue <int> q; int p, t;
if (e[1].ch[0]) q.push(e[1].ch[0]), e[e[1].ch[0]].fail = 1;
if (e[1].ch[1]) q.push(e[1].ch[1]), e[e[1].ch[1]].fail = 1;
while (q.size()) {
p = q.front(), q.pop();
for (int i = 0; i < 2; i++)
if (e[p].ch[i]) {
q.push(e[p].ch[i]);
t = e[p].fail;
while (t != 1 && !e[t].ch[i]) t = e[t].fail;
if (!e[t].ch[i]) e[e[t].ch[i]].fail = 1;
else e[e[p].ch[i]].fail = e[t].ch[i], e[e[p].ch[i]].tag |= e[e[t].ch[i]].tag;
} else e[p].ch[i] = e[e[p].fail].ch[i];
}
}

void find_circle(int u) {
if (find_answer) return;
vis[u] = 1;
for (int i = 0; i < 2; i++) {
if (!e[u].ch[i]) continue;
if (vis[e[u].ch[i]]) {
find_answer = true; return;
} else if (!e[e[u].ch[i]].tag && !found[e[u].ch[i]]) {
found[e[u].ch[i]] = 1;
find_circle(e[u].ch[i]);
}
}
vis[u] = 0;
}

bool spfa() {
int u, v, l = 0, r = 0, max = 0; q[0] = 1, dis[1] = 0;
while (l <= r) {
u = q[(l++) % tot];
for (int i = 0; i < 2; i++) {
v = e[u].ch[i];
if (dis[u] + 1 > dis[v] && v && !e[v].tag) {
dis[v] = dis[u] + 1;
if (!inq[v]) inq[q[(++r) % tot] = v];
}
}
}
for (int i = 1; i <= tot; i++) max = std::max(dis[i], max);
return max >= m;
}

void main() {
while (scanf("%d%lld", &n, &m) != EOF) {
for (int i = 1; i <= tot; i++) e[i].ch[0] = e[i].ch[1] = e[i].fail = e[i].tag = 0;
find_answer = 0, tot = 1;
for (int i = 1; i <= n; i++) scanf("%s", a), insert(a);
build_fail(), find_circle(1);
if (!find_answer) find_answer = spfa();
puts(find_answer ? "Yes" : "No");
for (int i = 1; i <= tot; i++) vis[i] = found[i] = dis[i] = inq[i] = 0;
}
}

} signed main() { return ringo::main(), 0; }
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×