C. Sakurada Reset
「Gym 102361C」Sakurada Reset（动态规划）
题目描述
给定数列 $A, B$，将数列中的每个子序列都看作一个 $1000$ 进制数，问有多少对 $(x, y)$ 满足 $x$ 是 $A$ 的某个子序列，$y$ 是 $B$ 的某个子序列，并且 $x > y$。本质相同的子序列只算一次，答案对大素数取模。
数据范围：$n, m \le 5000, 1 \le A_i, B_i \le 100$。
思路分析
令 $p_i$ 表示 $A$ 中满足 $j < i$ 且 $A_j = A_i$ 的最大的 $j$，如果不存在则为 $0$；$q_i$ 在 $B$ 中有类似的定义。首先计算长度不等的对数，发现这时一定是 $x$ 的长度比 $y$ 的大。预处理出每个数列中特定长度的本质不同子序列个数，就可以直接计算答案了。转移方程：$f(i, j) = f(i - 1)(j) + f(i - 1)(j - 1) - f(p_i - 1)(j - 1)$。
之后再考虑 $x, y$ 长度相同时的贡献。$x, y$ 必定有一个 lcp，之后的第一个数一定是 $x$ 中的比 $y$ 中的大，然后就可以随便排了。将这三个阶段写成三个状态：$f, g, h$，$f(i, j)$ 表示选到 $A_i, B_j$ 为止都相同的方案数，$g, h$ 类似。那么 $f$ 要求 $A_i = B_j$，$g$ 要求 $A_i > B_j$，$h$ 没有要求； $f, g$ 可以从 $f$ 转移过来，$h$ 可以从 $g, h$ 转移过来。下面列出 $f$ 的转移方程，$g, h$ 类似：
前缀和优化 dp 即可。时间复杂度 $O(\max(n, m)^2)$，注意常数优化。
代码实现
1 | |
2 | using namespace std; |
3 | |
4 | namespace __main__ { |
5 | const int maxn = 5e3, mod = 998244353; |
6 | int n, m, a[maxn + 3], b[maxn + 3]; |
7 | int f[maxn + 3][maxn + 3], g[maxn + 3][maxn + 3]; |
8 | int last[maxn + 3], p_a[maxn + 3], p_b[maxn + 3]; |
9 | |
10 | void read_arr(int a[], int n) { |
11 | for (int i = 1; i <= n; i++) { |
12 | scanf("%d", &a[i]); |
13 | } |
14 | } |
15 | |
16 | void add(int &x, int y) { |
17 | x += y, x < mod ? 0 : x -= mod; |
18 | } |
19 | |
20 | void sub(int &x, int y) { |
21 | x -= y, x < 0 ? x += mod : 0; |
22 | } |
23 | |
24 | void get_f(int f[maxn + 3][maxn + 3], int p[maxn + 3], int a[maxn + 3], int n) { |
25 | memset(last, 0, sizeof(last)); |
26 | f[0][0] = 1; |
27 | for (int i = 1; i <= n; i++) { |
28 | memcpy(f[i], f[i - 1], sizeof(f[i][0]) * (i + 1)); |
29 | for (int j = 1; j <= i; j++) { |
30 | add(f[i][j], f[i - 1][j - 1]); |
31 | if (last[a[i]]) { |
32 | sub(f[i][j], f[last[a[i]] - 1][j - 1]); |
33 | } |
34 | } |
35 | p[i] = last[a[i]]; |
36 | last[a[i]] = i; |
37 | } |
38 | } |
39 | |
40 | inline int func(int x) { |
41 | return x < mod ? x : x - mod; |
42 | } |
43 | |
44 | int sum(int f[][maxn + 3], int u, int d, int l, int r) { |
45 | u--, l--; |
46 | int x = f[d][r]; |
47 | if (~u) sub(x, f[u][r]); |
48 | if (~l) sub(x, f[d][l]); |
49 | if ((~u) && (~l)) add(x, f[u][l]); |
50 | return x; |
51 | } |
52 | |
53 | int solve() { |
54 | f[0][0] = 1, g[0][0] = 0; |
55 | for (int i = 1; i <= n; i++) { |
56 | f[i][0] = 1, g[i][0] = 0; |
57 | } |
58 | for (int i = 1; i <= m; i++) { |
59 | f[0][i] = 1, g[0][i] = 0; |
60 | } |
61 | for (int i = 1; i <= n; i++) { |
62 | for (int j = 1; j <= m; j++) { |
63 | f[i][j] = 0, g[i][j] = 0; |
64 | if (a[i] == b[j]) f[i][j] = sum(f, p_a[i], i - 1, p_b[j], j - 1); |
65 | if (a[i] > b[j]) g[i][j] = sum(f, p_a[i], i - 1, p_b[j], j - 1); |
66 | add(g[i][j], sum(g, p_a[i], i - 1, p_b[j], j - 1)); |
67 | |
68 | add(f[i][j], func(func(f[i][j - 1] + f[i - 1][j]) - f[i - 1][j - 1] + mod)); |
69 | add(g[i][j], func(func(g[i][j - 1] + g[i - 1][j]) - g[i - 1][j - 1] + mod)); |
70 | } |
71 | } |
72 | return func(g[n][m]); |
73 | } |
74 | |
75 | void main() { |
76 | scanf("%d %d", &n, &m); |
77 | read_arr(a, n), read_arr(b, m); |
78 | get_f(f, p_a, a, n), get_f(g, p_b, b, m); |
79 | int ans = 0; |
80 | for (int i = 1; i <= n; i++) { |
81 | for (int j = 1; j < i && j <= m; j++) { |
82 | ans = (ans + 1ll * f[n][i] * g[m][j]) % mod; |
83 | } |
84 | } |
85 | add(ans, solve()); |
86 | printf("%d\n", ans); |
87 | } |
88 | } |
89 | |
90 | int main() { |
91 | __main__::main(); |
92 | return 0; |
93 | } |
E. Escape
题目描述
给定 $n$ 行 $m$ 列的棋盘，北面某些位置有机器人头朝下，南边有某些位置有出口。棋盘中有一些障碍物，机器人不能通过。你可以在一些没有障碍物的地方放置转弯装置，共有四种（“北 $\leftrightarrow$ 东” 以及其他类似的三种）。问机器人是否能够到达某个出口。
数据范围：$T \le 10, n, m \le 100$。
思路分析
一个重要的观察就是每个转弯装置只能给一个人用。那么考虑网络流，给每个格子拆成两个点：横点和竖点，每排的横点连边，每列的竖点连边，机器人和出口与竖点连边。转弯装置相当于联通横点与竖点，也就是在横点和竖点之间连一条边。这样网络中的所有边都是单位容量边，网络流跑得很快。时间复杂度 $O(T \cdot \text{flow}(n \times m, n \times m))$。
代码实现
1 | |
2 | using namespace std; |
3 | |
4 | namespace __main__ { |
5 | const int maxn = 100, maxv = 3e4, maxe = 2e5, inf = 1e9; |
6 | int T, n, m, a[maxn + 3][maxn + 3], A, B; |
7 | int cnt, src, snk, row[maxn + 3][maxn + 3], col[maxn + 3][maxn + 3]; |
8 | int tot, ter[maxe + 3], wei[maxe + 3], nxt[maxe + 3], lnk[maxv + 3]; |
9 | int dep[maxv + 3], cur[maxv + 3], q[maxv + 3], l, r; |
10 | |
11 | void add_e(int u, int v, int w) { |
12 | ter[++tot] = v, wei[tot] = w; |
13 | nxt[tot] = lnk[u], lnk[u] = tot; |
14 | } |
15 | |
16 | void add(int u, int v) { |
17 | add_e(u, v, 1), add_e(v, u, 0); |
18 | } |
19 | |
20 | void add_b(int u, int v) { |
21 | add(u, v), add(v, u); |
22 | } |
23 | |
24 | bool bfs() { |
25 | memset(dep, -1, sizeof(dep)); |
26 | dep[src] = 0; |
27 | l = r = 0, q[r++] = src; |
28 | while (l < r) { |
29 | int u = q[l++]; |
30 | for (int i = lnk[u], v, w; i; i = nxt[i]) { |
31 | v = ter[i], w = wei[i]; |
32 | if (w && dep[v] == -1) { |
33 | dep[v] = dep[u] + 1; |
34 | q[r++] = v; |
35 | } |
36 | } |
37 | } |
38 | return ~dep[snk]; |
39 | } |
40 | |
41 | inline int adj(int x) { |
42 | return x & 1 ? x + 1 : x - 1; |
43 | } |
44 | |
45 | int dfs(int u, int f) { |
46 | if (u == snk) { |
47 | return f; |
48 | } |
49 | int x = 0; |
50 | for (int &i = cur[u], v, w; i && x < f; i = nxt[i]) { |
51 | v = ter[i], w = wei[i]; |
52 | if (w && dep[v] == dep[u] + 1) { |
53 | int t = dfs(v, min(w, f - x)); |
54 | wei[i] -= t, wei[adj(i)] += t, x += t; |
55 | } |
56 | } |
57 | if (x < f) { |
58 | dep[u] = -1; |
59 | } |
60 | return x; |
61 | } |
62 | |
63 | int dinic() { |
64 | int ans = 0; |
65 | while (bfs()) { |
66 | memcpy(cur, lnk, sizeof(cur)); |
67 | ans += dfs(src, inf); |
68 | } |
69 | return ans; |
70 | } |
71 | |
72 | void main() { |
73 | scanf("%d", &T); |
74 | while (T --> 0) { |
75 | scanf("%d %d %d %d", &n, &m, &A, &B); |
76 | for (int i = 1; i <= n; i++) { |
77 | for (int j = 1; j <= m; j++) { |
78 | scanf("%1d", &a[i][j]); |
79 | } |
80 | } |
81 | tot = 0; |
82 | memset(lnk, 0, sizeof(lnk)); |
83 | cnt = 2, src = 1, snk = 2; |
84 | for (int i = 1; i <= n; i++) { |
85 | for (int j = 1; j <= m; j++) { |
86 | row[i][j] = ++cnt; |
87 | } |
88 | } |
89 | for (int i = 1; i <= n; i++) { |
90 | for (int j = 1; j <= m; j++) { |
91 | col[i][j] = ++cnt; |
92 | } |
93 | } |
94 | for (int i = 1, x; i <= A; i++) { |
95 | scanf("%d", &x); |
96 | add(src, col[1][x]); |
97 | } |
98 | for (int i = 1, x; i <= B; i++) { |
99 | scanf("%d", &x); |
100 | add(col[n][x], snk); |
101 | } |
102 | for (int i = 1; i <= n; i++) { |
103 | for (int j = 1; j <= m; j++) { |
104 | if (a[i][j] == 0) { |
105 | if (i >= 2 && a[i - 1][j] == 0) { |
106 | add_b(col[i - 1][j], col[i][j]); |
107 | } |
108 | if (j >= 2 && a[i][j - 1] == 0) { |
109 | add_b(row[i][j - 1], row[i][j]); |
110 | } |
111 | add_b(row[i][j], col[i][j]); |
112 | } |
113 | } |
114 | } |
115 | if (dinic() == A) { |
116 | puts("Yes"); |
117 | } else { |
118 | puts("No"); |
119 | } |
120 | } |
121 | } |
122 | } |
123 | |
124 | int main() { |
125 | __main__::main(); |
126 | return 0; |
127 | } |
H. Houraisan Kaguya
绝对不鸽。
K. MUV LUV UNLIMITED
「Gym 102361K」MUV LUV UNLIMITED（博弈论）
题目描述
有一棵树，先手和后手轮流操作，每次可以拿掉若干叶子结点（不能不拿），拿到根结点的人获胜。问先手是否必胜。
复杂度要求线性。
思路分析
对于某棵树，考虑在它的某个非叶结点下面加上一个叶子结点，那么：
- 如果原树是必败态，先手第一次只取新叶子后就留下了必败态，那么新树就是必胜态。
- 如果原树是必胜态，先手第一次取下新叶子和原树必胜态中第一步应该取下的叶子，那么新树还是必胜态。
也就是说，如果一个树满足一个叶子结点的父亲度数大于等于 $2$，它就是必胜态。
如果不是怎么办呢？我们对于每个叶子结点找到第一个祖先 $x$ 满足它的父亲度数大于等于 $2$，我们的目标就是让敌人删到 $x$ 成为叶子结点，然后自己就赢了。这样问题转化成了有 $k$ 个 $a_i$ 表示叶子结点和对应的 $x$ 结点的距离，每次可以选择若干个 $a_i$ 减去 $1$，把其中一个减到 $0$ 的人就输了。
发现只要有一个 $a_i$ 是偶数，你就可以在第一步把所有偶数都取掉一个，之后对手干什么你就复读，最后肯定会在对手的回合留下 $k$ 个 $1$，然后他就输了。否则这时 $a_i$ 全是奇数，对手只要复读你他就能赢。也就是说如果 $a_i$ 全是奇数，你会输；否则你会赢。这样问题就解决了，时间复杂度 $O(n)$。
代码实现
1 | |
2 | using namespace std; |
3 | |
4 | const int maxn = 1e6; |
5 | int T, n, fa[maxn + 3], deg[maxn + 3]; |
6 | |
7 | void print(int x) { |
8 | puts(x ? "Takeru" : "Meiya"); |
9 | } |
10 | |
11 | int main() { |
12 | scanf("%d", &T); |
13 | while (T --> 0) { |
14 | scanf("%d", &n); |
15 | for (int i = 1; i <= n; i++) { |
16 | deg[i] = 0; |
17 | } |
18 | for (int i = 2; i <= n; i++) { |
19 | scanf("%d", &fa[i]); |
20 | deg[fa[i]]++; |
21 | } |
22 | bool ch = true; |
23 | for (int i = 1; i <= n; i++) { |
24 | ch &= deg[i] <= 1; |
25 | } |
26 | if (ch) { |
27 | print(n & 1); |
28 | continue; |
29 | } |
30 | bool flag = false; |
31 | for (int i = 1; i <= n; i++) if (deg[i] == 0) { |
32 | if (deg[fa[i]] >= 2) { |
33 | print(1); |
34 | flag = true; |
35 | break; |
36 | } |
37 | } |
38 | if (flag) { |
39 | continue; |
40 | } |
41 | flag = false; |
42 | for (int i = 1; i <= n; i++) if (deg[i] == 0) { |
43 | int x = i, c = 0; |
44 | while (deg[x] < 2) { |
45 | x = fa[x], c++; |
46 | } |
47 | flag |= c & 1; |
48 | } |
49 | print(flag); |
50 | } |
51 | return 0; |
52 | } |
L. MUV LUV ALTERNATIVE
在路上了。