Luogu 5597 - 【XR-4】复读

一道小清新的构造题。

循环节可以看作是一次对于起点的位移,不难证明如果复读次数在两次以上,位移后的点一定仍在给定的子树上。

所以我们枚举位移方式,计算出对于所有复读的起点。

令起点为 $u$ ,经过一次复读后所能到达的点是 $v$ ,那么对于 $u$ 的子树中,除了 $v$ 的子树的部分,都必须遍历一次。由于复读的次数不止一次,此时 $v$ 又变成起点,于是计算 $v$ 的子树除其复读后到达的点 $w$ 的部分。

这样,每一个起点都会有一个必须遍历的连通块,给他们求一个并集,计算出他们的大小,答案就是:

$o$ 为命令长度,枚举所有的位移方式就可以计算出所有的答案,复杂度 $O(n^2)$ 。

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
#include <bits/stdc++.h>

#define MAXN 2005
#define INF 0x3f3f3f3f

using namespace std;

int n, total, root, ans = INF;
int ch[MAXN][2], size[MAXN], g[MAXN][2];

void build(int u) {
int s;
scanf("%1d", &s);
if (!s)
return ;
else if (s == 1)
build(ch[u][0] = ++n);
else if (s == 2)
build(ch[u][1] = ++n);
else if (s == 3) {
build(ch[u][0] = ++n);
build(ch[u][1] = ++n);
}
}

void merge(int& u, int v, int limit) {
if (v == limit)
return ;
if (!u) {
size[u = ++total] = 1;
g[u][0] = g[u][1] = 0;
}
if (ch[v][0])
merge(g[u][0], ch[v][0], limit);
if (ch[v][1])
merge(g[u][1], ch[v][1], limit);
size[u] = size[g[u][0]] + size[g[u][1]] + 1;
}

int calc(string order) {
int u = 1;
root = total = 0;
while (u) {
int origin = u;
for (int i = 0; i < order.size(); ++i)
u = ch[u][order[i] == 'R'];
merge(root, origin, u);
}
return size[root];
}

void solve(int u, string order) {
if (ch[u][0])
solve(ch[u][0], order + "L");
if (ch[u][1])
solve(ch[u][1], order + "R");
if (u != 1) {
int size = calc(order);
ans = min(2 * size - (int)order.size(), ans);
}
}

int main() {
build(++n);
solve(1, "");
printf("%d\n", ans);
}