🦄️🦄️ Horse Power! ️🦄️🦄️

0%

「CCPC 2019 秦皇岛」部分题解

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

namespace __main__ {
const int maxn = 5e3, mod = 998244353;
int n, m, a[maxn + 3], b[maxn + 3];
int f[maxn + 3][maxn + 3], g[maxn + 3][maxn + 3];
int last[maxn + 3], p_a[maxn + 3], p_b[maxn + 3];

void read_arr(int a[], int n) {
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
}

void add(int &x, int y) {
x += y, x < mod ? 0 : x -= mod;
}

void sub(int &x, int y) {
x -= y, x < 0 ? x += mod : 0;
}

void get_f(int f[maxn + 3][maxn + 3], int p[maxn + 3], int a[maxn + 3], int n) {
memset(last, 0, sizeof(last));
f[0][0] = 1;
for (int i = 1; i <= n; i++) {
memcpy(f[i], f[i - 1], sizeof(f[i][0]) * (i + 1));
for (int j = 1; j <= i; j++) {
add(f[i][j], f[i - 1][j - 1]);
if (last[a[i]]) {
sub(f[i][j], f[last[a[i]] - 1][j - 1]);
}
}
p[i] = last[a[i]];
last[a[i]] = i;
}
}

inline int func(int x) {
return x < mod ? x : x - mod;
}

int sum(int f[][maxn + 3], int u, int d, int l, int r) {
u--, l--;
int x = f[d][r];
if (~u) sub(x, f[u][r]);
if (~l) sub(x, f[d][l]);
if ((~u) && (~l)) add(x, f[u][l]);
return x;
}

int solve() {
f[0][0] = 1, g[0][0] = 0;
for (int i = 1; i <= n; i++) {
f[i][0] = 1, g[i][0] = 0;
}
for (int i = 1; i <= m; i++) {
f[0][i] = 1, g[0][i] = 0;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
f[i][j] = 0, g[i][j] = 0;
if (a[i] == b[j]) f[i][j] = sum(f, p_a[i], i - 1, p_b[j], j - 1);
if (a[i] > b[j]) g[i][j] = sum(f, p_a[i], i - 1, p_b[j], j - 1);
add(g[i][j], sum(g, p_a[i], i - 1, p_b[j], j - 1));

add(f[i][j], func(func(f[i][j - 1] + f[i - 1][j]) - f[i - 1][j - 1] + mod));
add(g[i][j], func(func(g[i][j - 1] + g[i - 1][j]) - g[i - 1][j - 1] + mod));
}
}
return func(g[n][m]);
}

void main() {
scanf("%d %d", &n, &m);
read_arr(a, n), read_arr(b, m);
get_f(f, p_a, a, n), get_f(g, p_b, b, m);
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j < i && j <= m; j++) {
ans = (ans + 1ll * f[n][i] * g[m][j]) % mod;
}
}
add(ans, solve());
printf("%d\n", ans);
}
}

int main() {
__main__::main();
return 0;
}

E. Escape

「Gym 102361E」Escape(最大流)

题目描述

给定 $n$ 行 $m$ 列的棋盘,北面某些位置有机器人头朝下,南边有某些位置有出口。棋盘中有一些障碍物,机器人不能通过。你可以在一些没有障碍物的地方放置转弯装置,共有四种(“北 $\leftrightarrow$ 东” 以及其他类似的三种)。问机器人是否能够到达某个出口。

数据范围:$T \le 10, n, m \le 100$。

思路分析

一个重要的观察就是每个转弯装置只能给一个人用。那么考虑网络流,给每个格子拆成两个点:横点和竖点,每排的横点连边,每列的竖点连边,机器人和出口与竖点连边。转弯装置相当于联通横点与竖点,也就是在横点和竖点之间连一条边。这样网络中的所有边都是单位容量边,网络流跑得很快。时间复杂度 $O(T \cdot \text{flow}(n \times m, n \times m))$。

代码实现

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <bits/stdc++.h>
using namespace std;

namespace __main__ {
const int maxn = 100, maxv = 3e4, maxe = 2e5, inf = 1e9;
int T, n, m, a[maxn + 3][maxn + 3], A, B;
int cnt, src, snk, row[maxn + 3][maxn + 3], col[maxn + 3][maxn + 3];
int tot, ter[maxe + 3], wei[maxe + 3], nxt[maxe + 3], lnk[maxv + 3];
int dep[maxv + 3], cur[maxv + 3], q[maxv + 3], l, r;

void add_e(int u, int v, int w) {
ter[++tot] = v, wei[tot] = w;
nxt[tot] = lnk[u], lnk[u] = tot;
}

void add(int u, int v) {
add_e(u, v, 1), add_e(v, u, 0);
}

void add_b(int u, int v) {
add(u, v), add(v, u);
}

bool bfs() {
memset(dep, -1, sizeof(dep));
dep[src] = 0;
l = r = 0, q[r++] = src;
while (l < r) {
int u = q[l++];
for (int i = lnk[u], v, w; i; i = nxt[i]) {
v = ter[i], w = wei[i];
if (w && dep[v] == -1) {
dep[v] = dep[u] + 1;
q[r++] = v;
}
}
}
return ~dep[snk];
}

inline int adj(int x) {
return x & 1 ? x + 1 : x - 1;
}

int dfs(int u, int f) {
if (u == snk) {
return f;
}
int x = 0;
for (int &i = cur[u], v, w; i && x < f; i = nxt[i]) {
v = ter[i], w = wei[i];
if (w && dep[v] == dep[u] + 1) {
int t = dfs(v, min(w, f - x));
wei[i] -= t, wei[adj(i)] += t, x += t;
}
}
if (x < f) {
dep[u] = -1;
}
return x;
}

int dinic() {
int ans = 0;
while (bfs()) {
memcpy(cur, lnk, sizeof(cur));
ans += dfs(src, inf);
}
return ans;
}

void main() {
scanf("%d", &T);
while (T --> 0) {
scanf("%d %d %d %d", &n, &m, &A, &B);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
scanf("%1d", &a[i][j]);
}
}
tot = 0;
memset(lnk, 0, sizeof(lnk));
cnt = 2, src = 1, snk = 2;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
row[i][j] = ++cnt;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
col[i][j] = ++cnt;
}
}
for (int i = 1, x; i <= A; i++) {
scanf("%d", &x);
add(src, col[1][x]);
}
for (int i = 1, x; i <= B; i++) {
scanf("%d", &x);
add(col[n][x], snk);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a[i][j] == 0) {
if (i >= 2 && a[i - 1][j] == 0) {
add_b(col[i - 1][j], col[i][j]);
}
if (j >= 2 && a[i][j - 1] == 0) {
add_b(row[i][j - 1], row[i][j]);
}
add_b(row[i][j], col[i][j]);
}
}
}
if (dinic() == A) {
puts("Yes");
} else {
puts("No");
}
}
}
}

int main() {
__main__::main();
return 0;
}

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

const int maxn = 1e6;
int T, n, fa[maxn + 3], deg[maxn + 3];

void print(int x) {
puts(x ? "Takeru" : "Meiya");
}

int main() {
scanf("%d", &T);
while (T --> 0) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
deg[i] = 0;
}
for (int i = 2; i <= n; i++) {
scanf("%d", &fa[i]);
deg[fa[i]]++;
}
bool ch = true;
for (int i = 1; i <= n; i++) {
ch &= deg[i] <= 1;
}
if (ch) {
print(n & 1);
continue;
}
bool flag = false;
for (int i = 1; i <= n; i++) if (deg[i] == 0) {
if (deg[fa[i]] >= 2) {
print(1);
flag = true;
break;
}
}
if (flag) {
continue;
}
flag = false;
for (int i = 1; i <= n; i++) if (deg[i] == 0) {
int x = i, c = 0;
while (deg[x] < 2) {
x = fa[x], c++;
}
flag |= c & 1;
}
print(flag);
}
return 0;
}

L. MUV LUV ALTERNATIVE

在路上了。