只要你跑的够快，锅就追不上你

0%

「集训队作业」IOI 2020 集训队作业小结 2

发表于 更新于

简介

本文包括 IOI 2020 集训队作业 13 ~ 18 题的题解。下面是题单：

Simple Subsequence Problem

考虑算出每个串是多少串的子序列。设状态 $f(S | T)$ 表示母串还剩 $S$，当前子序列为 $T$ 的方案数，转移时取 $S$ 中第一个 0/1 加到 $T$ 后面并删掉 $S$ 中该字符前面的东西即可。时间复杂度 $O(2^n n)$。

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
const int maxn = 21, maxm = 1 << maxn;
5
int n, k, dp[maxn + 3][maxm + 3];
6
char s[maxm + 3];
7
8
int main() {
9
	scanf("%d %d", &n, &k);
10
	for (int i = 0; i <= n; i++) {
11
		scanf("%s", s);
12
		for (int j = 0; j < 1 << i; j++) {
13
			dp[i][1 << i | j] = s[j] ^ '0';
14
		}
15
	}
16
	for (int i = n; i; i--) {
17
		for (int j = i; j <= n; j++) {
18
			int b = 1 << j;
19
			for (int k = 0; k < b; k++) {
20
				int x = dp[i][k | b], p = -1, q = -1;
21
				for (int t = i; t; t--) {
22
					if (~k >> (t - 1) & 1) {
23
						p = t;
24
						break;
25
					}
26
				}
27
				for (int t = i; t; t--) {
28
					if (k >> (t - 1) & 1) {
29
						q = t;
30
						break;
31
					}
32
				}
33
				dp[0][(k | b) >> i] += x;
34
				if (p != -1) {
35
					dp[p - 1][(k & ((1 << (p - 1)) - 1)) | (((k >> i) << 1 | 0) << (p - 1)) | (b >> (i - p))] += x;
36
				}
37
				if (q != -1) {
38
					dp[q - 1][(k & ((1 << (q - 1)) - 1)) | (((k >> i) << 1 | 1) << (q - 1)) | (b >> (i - q))] += x;
39
				}
40
			}
41
		}
42
	}
43
	for (int i = n; i >= 0; i--) {
44
		for (int j = 1 << i; j < 1 << (i + 1); j++) {
45
			if (dp[0][j] >= k) {
46
				for (int t = i - 1; t >= 0; t--) {
47
					printf("%d", j >> t & 1);
48
				}
49
				puts("");
50
				return 0;
51
			}
52
		}
53
	}
54
	return 0;
55
}

Choosing Points

相当于给两个图，求一个点集是两个图的独立集。考虑只有一个图的情况：如果 $D$ 是奇数，那么黑白染色可发现图是二分图；如果 $D$ 是偶数，我们黑白染色后发现黑色和白色之间没有边，对于一种颜色，我们把坐标轴旋转 45 度后缩放 $\sqrt 2$ 倍就转化成了一个 $D’ = \frac{D}{2}$ 的子问题，归纳可证图是二分图。这样，对于每个二分图分别染色，每个格子就会有一个颜色的 pair，根据抽屉原理肯定有解。朴素实现时间复杂度为 $O(n^3)$。

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
const int maxn = 600, maxm = maxn * maxn;
5
int n, tot, id[maxn + 3][maxn + 3], row[maxm + 3], col[maxm + 3];
6
int x, y, num[maxm + 3], res[maxm + 3], cnt[5];
7
bool vis[maxm + 3];
8
vector<int> G[maxm + 3];
9
10
void add(int u, int v) {
11
	G[u].push_back(v);
12
}
13
14
void dfs(int u) {
15
	vis[u] = true;
16
	for (int i = 0, v; i < G[u].size(); i++) {
17
		v = G[u][i];
18
		if (vis[v]) continue;
19
		num[v] = num[u] ^ 1;
20
		dfs(v);
21
	}
22
}
23
24
void solve(int x, int y) {
25
	for (int i = 1; i <= tot; i++) {
26
		vis[i] = false;
27
		vector<int>().swap(G[i]);
28
	}
29
	for (int a = 0; a < n * 2; a++) {
30
		for (int b = 0; b < n * 2; b++) {
31
			if (a * a + b * b == x) {
32
				for (int i = 0; i < n * 2 - a; i++) {
33
					for (int j = 0; j < n * 2 - b; j++) {
34
						add(id[i][j], id[i + a][j + b]);
35
						add(id[i + a][j + b], id[i][j]);
36
						add(id[i][j + b], id[i + a][j]);
37
						add(id[i + a][j], id[i][j + b]);
38
					}
39
				}
40
			}
41
		}
42
	}
43
	num[1] = 0;
44
	for (int i = 1; i <= tot; i++) {
45
		if (!vis[i]) dfs(i);
46
	}
47
	for (int i = 1; i <= tot; i++) {
48
		res[i] |= num[i] << y;
49
	}
50
}
51
52
int main() {
53
	scanf("%d %d %d", &n, &x, &y);
54
	for (int i = 0; i < n * 2; i++) {
55
		for (int j = 0; j < n * 2; j++) {
56
			id[i][j] = ++tot;
57
			row[tot] = i, col[tot] = j;
58
		}
59
	}
60
	solve(x, 0), solve(y, 1);
61
	for (int i = 1; i <= tot; i++) {
62
		cnt[res[i]]++;
63
	}
64
	int pnt = 0;
65
	for (int i = 0; i < 4; i++) {
66
		if (cnt[i] >= n * n) {
67
			pnt = i;
68
			break;
69
		}
70
	}
71
	int all = 0;
72
	for (int i = 1; i <= tot; i++) {
73
		if (res[i] == pnt) {
74
			printf("%d %d\n", row[i], col[i]);
75
			if (++all == n * n) break;
76
		}
77
	}
78
	return 0;
79
}

Walking on a Tree

首先发现答案可以取上界，考虑构造。考虑一个子树中向外连的边，如果数量不超过 $1$，那么直接把答案加上数量；否则把答案加上 $2$，然后在这样的边中选两条加一个限制。考虑选哪些边，发现如果某个子树已经有两条链了，那么就继承上来；否则随便选两条链肯定在两个子树中，不会冲突。时间复杂度 $O(nm)$。

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
const int maxn = 2000;
5
int n, m, fa[maxn + 3], dep[maxn + 3], u[maxn + 3], v[maxn + 3], w[maxn + 3], ans;
6
int b[maxn + 3][maxn + 3], g[maxn + 3][2], tot, lft[maxn + 3], rht[maxn + 3], wei[maxn + 3];
7
bool vis[maxn + 3], res[maxn + 3];
8
vector<int> G[maxn + 3], D[maxn + 3], V[maxn + 3];
9
vector<pair<int, int> > S[maxn + 3];
10
11
void add(int u, int v) {
12
	G[u].push_back(v);
13
}
14
15
void dfs(int u, int pa = 0) {
16
	for (int i = 0, v; i < G[u].size(); i++) {
17
		v = G[u][i];
18
		if (v == pa) continue;
19
		dep[v] = dep[u] + 1;
20
		fa[v] = u;
21
		dfs(v, u);
22
	}
23
}
24
25
void add_lim(int u, int v, int w) {
26
	lft[++tot] = u, rht[tot] = v, wei[tot] = w;
27
}
28
29
void solve(int u, int pa = 0) {
30
	g[u][0] = g[u][1] = -1;
31
	for (int i = 1; i <= m; i++) {
32
		b[u][i] = -1;
33
	}
34
	for (int i = 0, v; i < G[u].size(); i++) {
35
		v = G[u][i];
36
		if (v == pa) continue;
37
		solve(v, u);
38
		for (int j = 1; j <= m; j++) {
39
			if (b[u][j] == -1) {
40
				b[u][j] = b[v][j];
41
			}
42
		}
43
	}
44
	for (int i = 0; i < S[u].size(); i++) {
45
		pair<int, int> x = S[u][i];
46
		b[u][x.first] = x.second;
47
	}
48
	int cnt = 0;
49
	for (int i = 1; i <= m; i++) {
50
		cnt += b[u][i] != -1;
51
	}
52
	if (cnt < 2) {
53
		ans += cnt;
54
	} else {
55
		ans += 2;
56
		int p = 0;
57
		for (int i = 0, v; i < G[u].size(); i++) {
58
			v = G[u][i];
59
			if (v == pa) continue;
60
			if (g[v][0] == -1) continue;
61
			if (~b[u][g[v][0]] && ~b[u][g[v][1]]) {
62
				p = v;
63
				break;
64
			}
65
		}
66
		if (p) {
67
			g[u][0] = g[p][0];
68
			g[u][1] = g[p][1];
69
		} else {
70
			int x = 0, y = 0;
71
			for (int i = 1; i <= m; i++) {
72
				if (b[u][i] == -1) continue;
73
				if (!x) {
74
					x = i;
75
				} else if (x && !y) {
76
					y = i;
77
				}
78
			}
79
			g[u][0] = x, g[u][1] = y;
80
			add_lim(x, y, b[u][x] ^ b[u][y] ^ 1);
81
		}
82
	}
83
}
84
85
void color(int u) {
86
	vis[u] = true;
87
	for (int i = 0, v; i < D[u].size(); i++) {
88
		v = D[u][i];
89
		if (vis[v]) continue;
90
		res[v] = res[u] ^ V[u][i];
91
		color(v);
92
	}
93
}
94
95
int main() {
96
	scanf("%d %d", &n, &m);
97
	for (int i = 1, u, v; i < n; i++) {
98
		scanf("%d %d", &u, &v);
99
		add(u, v), add(v, u);
100
	}
101
	dfs(1);
102
	for (int i = 1; i <= m; i++) {
103
		scanf("%d %d", &u[i], &v[i]);
104
		int x = u[i], y = v[i];
105
		while (x != y) {
106
			if (dep[x] < dep[y]) swap(x, y);
107
			x = fa[x];
108
		}
109
		w[i] = x;
110
		if (u[i] != w[i]) {
111
			S[u[i]].push_back(make_pair(i, 0));
112
		}
113
		if (v[i] != w[i]) {
114
			S[v[i]].push_back(make_pair(i, 1));
115
		}
116
		S[w[i]].push_back(make_pair(i, -1));
117
	}
118
	solve(1);
119
	printf("%d\n", ans);
120
	for (int i = 1; i <= tot; i++) {
121
		D[lft[i]].push_back(rht[i]), V[lft[i]].push_back(wei[i]);
122
		D[rht[i]].push_back(lft[i]), V[rht[i]].push_back(wei[i]);
123
	}
124
	for (int i = 1; i <= m; i++) {
125
		if (!vis[i]) color(i);
126
	}
127
	for (int i = 1; i <= m; i++) {
128
		if (!res[i]) {
129
			printf("%d %d\n", u[i], v[i]);
130
		} else {
131
			printf("%d %d\n", v[i], u[i]);
132
		}
133
	}
134
	return 0;
135
}

Addition and Andition

从高位往低位考虑，每次循环到 $(1, 1)$ 的位时把这位做 $k$ 次。维护一个栈存储非全 $0$ 的所有位的 pair，栈顶是最低的位。考虑三种进位 $[1, 1], [1, 0], [0, 1]$。假设进位是 $[1, 1]$：我们每次都是用掉一次操作，然后考虑下一位，直到考虑到一个非全 $0$ 的位时为止。这时我们可以直接判断能否跳到栈顶，如果可以就将剩余操作次数减去进的位数，然后考虑栈顶的那位。如果是 $(1, 0)$，就把它替换成 $(0, 1)$，并转化成对下一位的 $[1, 0]$ 的进位；是 $(0, 1)$ 同理。假设进位是 $[1, 0]$：如果当前一位是 $(1, 0)$，就把它变为 $(0, 0)$，进位还是 $[1, 0]$ 不变；否则当前一位是 $(0, 1)$，那么就转化成进位为 $[1, 1]$ 的情况。发现每进位两次栈的大小会减少 $1$，所以时间复杂度 $O(n + k)$。

1
#include <bits/stdc++.h>
2
using namespace std;
3
 
4
const int maxn = 2e6;
5
int n, m, K, a[maxn + 3], b[maxn + 3], top, A[maxn + 3], B[maxn + 3];
6
char s[maxn + 3], t[maxn + 3];
7
 
8
struct node {
9
	int k, v;
10
	node(int a = 0, int b = 0) {
11
		k = a, v = b;
12
	}
13
} st[maxn + 3], tmp[maxn + 3];
14
 
15
int main() {
16
	scanf("%d %d %d %s %s", &n, &m, &K, s + 1, t + 1);
17
	reverse(s + 1, s + n + 1);
18
	reverse(t + 1, t + m + 1);
19
	for (int i = 1; i <= n; i++) {
20
		a[i] = s[i] ^ '0';
21
	}
22
	for (int i = 1; i <= m; i++) {
23
		b[i] = t[i] ^ '0';
24
	}
25
	for (int i = max(n, m); i; i--) {
26
		if (a[i] && b[i]) {
27
			int pos = i, lft = K, cur = 3, cnt = 0;
28
			while (top) {
29
				if (cur == 3) {
30
					if (lft >= st[top].k - pos) {
31
						lft -= st[top].k - pos, pos = st[top].k;
32
						tmp[++cnt] = st[top], tmp[cnt].v ^= 3;
33
						cur &= st[top].v;
34
					} else {
35
						break;
36
					}
37
				} else if (cur) {
38
					if (st[top].k == pos + 1) {
39
						pos++;
40
						if (st[top].v != cur) {
41
							cur = 3;
42
						}
43
					} else {
44
						break;
45
					}
46
				} else {
47
					break;
48
				}
49
				top--;
50
			}
51
			if (cur == 3) {
52
				A[pos + lft] = 1, B[pos + lft] = 1;
53
			} else if (cur) {
54
				st[++top] = node(pos + 1, cur);
55
			}
56
			for (int i = cnt; i; i--) {
57
				st[++top] = tmp[i];
58
			}
59
		} else if (a[i] || b[i]) {
60
			st[++top] = node(i, a[i] << 1 | b[i]);
61
		}
62
	}
63
	for (int i = 1; i <= top; i++) {
64
		A[st[i].k] = st[i].v >> 1;
65
		B[st[i].k] = st[i].v & 1;
66
	}
67
	int N = max(n, m) + K, M = N;
68
	while (N && !A[N]) N--;
69
	while (M && !B[M]) M--;
70
	reverse(A + 1, A + N + 1);
71
	reverse(B + 1, B + M + 1);
72
	for (int i = 1; i <= N; i++) {
73
		putchar(A[i] ^ '0');
74
	}
75
	puts("");
76
	for (int i = 1; i <= M; i++) {
77
		putchar(B[i] ^ '0');
78
	}
79
	puts("");
80
	return 0;
81
}

Histogram Coloring

考虑最下面一层，它上面的每个格子一定和自己不同，唯一的特例是如果最下面一层交错染色的话，上面一层可以将下面一层的颜色取反。对于一段区间记两个 dp 值：$f$ 表示强制最后一行交错染色的方案数，$g$ 表示不强制的方案数。设区间最小高度为 $x$，最小高度的个数为 $y$，分出来的段分别为 $[l_1, r_1], [l_2, r_2], \cdots, [l_k, r_k]$，那么有：

直接计算即可。时间复杂度 $O(n^2)$ 或 $O(n \log h)$。

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
const int maxn = 100, mod = 1e9 + 7;
5
int n, a[maxn + 3];
6
7
int qpow(int a, int b) {
8
	int c = 1;
9
	for (; b; b >>= 1, a = 1ll * a * a % mod) {
10
		if (b & 1) c = 1ll * a * c % mod;
11
	}
12
	return c;
13
}
14
15
pair<int, int> solve(int l, int r, int h) {
16
	if (l == r) {
17
		int x = qpow(2, a[l] - h);
18
		return make_pair(x, x);
19
	}
20
	int mn = a[l];
21
	for (int i = l; i <= r; i++) {
22
		mn = min(mn, a[i]);
23
	}
24
	int c = 1, t = qpow(2, mn - h);
25
	for (int i = l; i <= r; i++) {
26
		if (a[i] == mn) c = 2ll * c % mod;
27
	}
28
	int x = 1, y = 1;
29
	for (int i = l, j = l; i <= r; i = j + 1, j = i) {
30
		if (a[i] == mn) continue;
31
		while (j < r && a[j + 1] != mn) j++;
32
		pair<int, int> t = solve(i, j, mn);
33
		x = 1ll * x * (t.first + t.second) % mod;
34
		y = 1ll * y * t.first % mod;
35
	}
36
	int p = 1ll * t * y % mod;
37
	int q = (1ll * c * x + 1ll * (t + mod - 2) * y) % mod;
38
	return make_pair(p, q);
39
}
40
41
int main() {
42
	scanf("%d", &n);
43
	for (int i = 1; i <= n; i++) {
44
		scanf("%d", &a[i]);
45
	}
46
	printf("%d\n", solve(1, n, 0).second);
47
	return 0;
48
}

Synchronized Subsequence

按照前缀 a 个数等于 b 个数的点分段。某一段如果 a 开头那么最优串肯定形如 ababab；如果 b 开头，记第 $i$ 个 ch 为 $\text{ch}_i$，那么我们肯定选择一个 $i$ 的后缀的 $a_i, b_i$，因为考虑选了 $i$ 却没选 $i + 1$，选了 $i + 1$ 一定更优（$b_i < b_{i + 1} < a_i < a_{i + 1}$）。我们得出每一段的答案后，发现每一段在最终答案中要么全选要么不选（a 开头的段是选完 b 开头的段之后的工具段，b 开头的段满足任意一个不是最优串的串都不是最优串的前缀），然后只要 dp 一下即可。时间复杂度 $O(n^2)$。 

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
const int maxn = 6000;
5
int n, sum[maxn + 3], tot, m[maxn + 3], k, l, a[maxn + 3], b[maxn + 3], p[maxn + 3], sz[maxn + 3];
6
char str[maxn + 3], s[maxn + 3][maxn + 3], res[maxn + 3][maxn + 3], tmp[maxn + 3];
7
bool vis[maxn + 3];
8
9
bool check(char s[], int n, char t[], int m) {
10
	for (int i = 1; i <= min(n, m); i++) {
11
		if (s[i] > t[i]) return true;
12
		if (s[i] < t[i]) return false;
13
	}
14
	return n > m;
15
}
16
17
void solve(char s[], char ret[], int n, int &m) {
18
	k = l = m = 0;
19
	for (int i = 1; i <= n; i++) {
20
		vis[i] = false;
21
		if (s[i] == 'a') {
22
			a[++k] = i, p[i] = k;
23
		} else {
24
			b[++l] = i, p[i] = l;
25
		}
26
	}
27
	if (s[1] == 'a') {
28
		for (int i = 1; i <= n; i++) {
29
			if (vis[i]) continue;
30
			for (int j = a[p[i]]; j < b[p[i]]; j++) {
31
				vis[b[p[j]]] = true;
32
			}
33
			ret[++m] = 'a';
34
			ret[++m] = 'b';
35
			i = b[p[i]];
36
		}
37
	} else {
38
		for (int i = 1; i <= k; i++) {
39
			int c = 0;
40
			for (int j = 1; j <= n; j++) {
41
				if (p[j] >= i) tmp[++c] = s[j];
42
			}
43
			if (check(tmp, c, ret, m)) {
44
				m = c;
45
				for (int j = 1; j <= c; j++) {
46
					ret[j] = tmp[j];
47
				}
48
			}
49
		}
50
	}
51
}
52
53
int main() {
54
	scanf("%d %s", &n, str + 1);
55
	for (int i = 1; i <= n * 2; i++) {
56
		sum[i] = sum[i - 1] + (str[i] == 'a' ? 1 : -1);
57
	}
58
	int lst = 1;
59
	for (int i = 1; i <= n * 2; i++) {
60
		if (sum[i] == 0) {
61
			++tot;
62
			for (int j = lst; j <= i; j++) {
63
				s[tot][++m[tot]] = str[j];
64
			}
65
			lst = i + 1;
66
		}
67
	}
68
	for (int i = 1; i <= tot; i++) {
69
		solve(s[i], res[i], m[i], sz[i]);
70
	}
71
	string s = "";
72
	for (int i = tot; i; i--) {
73
		string t = "";
74
		for (int j = 1; j <= sz[i]; j++) {
75
			t += res[i][j];
76
		}
77
		t += s;
78
		if (t > s) {
79
			s = t;
80
		}
81
	}
82
	cout << s << endl;
83
	return 0;
84
}