简介
本文包括 IOI 2020 集训队作业 27 ~ 30 题的题解，下面是题单：
- 25.「AGC 028E」High Elements
- 26.「AGC 028F」Reachable Cells
- 27.「AGC 029C」Lexicographic constraints
- 28.「AGC 029E」Wandering TKHS
- 29.「AGC 029F」Construction of a tree
- 30.「AGC 030C」Coloring Torus
Lexicographic constraints
二分答案，暴力模拟，时间复杂度 $O(n \log^2 n)$。
1 | |
2 | using namespace std; |
3 | |
4 | const int maxn = 2e5; |
5 | int n, a[maxn + 3]; |
6 | |
7 | bool check(int k) { |
8 | map<int, int> M; |
9 | for (int i = 1; i <= n; i++) { |
10 | if (a[i] <= a[i - 1]) { |
11 | if (k == 1) { |
12 | return false; |
13 | } |
14 | while (!M.empty() && M.rbegin() -> first > a[i]) { |
15 | map<int, int>::iterator it = M.end(); |
16 | M.erase(--it); |
17 | } |
18 | for (int j = a[i]; j >= 0; j--) { |
19 | if (j == 0) { |
20 | return false; |
21 | } |
22 | if (++M[j] == k) { |
23 | M[j] = 0; |
24 | } else { |
25 | break; |
26 | } |
27 | } |
28 | } |
29 | } |
30 | return true; |
31 | } |
32 | |
33 | int main() { |
34 | scanf("%d", &n); |
35 | for (int i = 1; i <= n; i++) { |
36 | scanf("%d", &a[i]); |
37 | } |
38 | int l = 1, r = n, mid; |
39 | while (l < r) { |
40 | mid = (l + r) >> 1; |
41 | if (check(mid)) { |
42 | r = mid; |
43 | } else { |
44 | l = mid + 1; |
45 | } |
46 | } |
47 | printf("%d\n", l); |
48 | return 0; |
49 | } |
Wandering TKHS
考虑结点 $u$ 比父亲多走到了哪些点。设 $p_u$ 表示 $u$ 的父亲，$m(u)$ 表示路径 $1 - p_u$ 中结点编号的最大值。令 $Q(u, x)$ 表示 $u$ 只经过 $\le x$ 的点能走到多少个后代结点（$u$ 自己不算）。那么对于所有 $u > 1$，我们有：
原因是如果 $u > m(p_u)$，那么以 $p_u$ 为起点时就不会访问到 $u$，我们就要新加入 $u$ 以及它子树中的信息。否则一定会访问到 $u$，但是从 $p_u$ 出发只会经过 $\le m(p_u)$ 的点，而从 $u$ 出发会经过 $\le m(u)$ 的点，所以要进行一定的修改。那么现在我们只要求出 $Q(u, m(u)), Q(u, m(p_u))$ 即可。$Q(u, x)$ 有递归式：
发现直接递归 + 记忆化的复杂度是正确的。因为对于 $Q(u, m(u))$，我们找到所有它后代中第一次 $> m(u)$ 的点并剪掉它这棵子树，之后 $u$ 的子树中点 $v$ 的询问就只剩下 $Q(v, m(u))$ 了。也就是说每个点只会有 $Q(u, m(u))$ 的询问。同理 $Q(u, m(p_u))$ 递归到每个点也只有常数种询问，所以直接暴力即可，时间复杂度 $O(n \log n)$ 或 $O(n)$。
1 | |
2 | using namespace std; |
3 | |
4 | const int maxn = 2e5; |
5 | int n, ans[maxn + 3], m[maxn + 3]; |
6 | vector<int> G[maxn + 3]; |
7 | map<pair<int, int>, int> M; |
8 | |
9 | int Q(int u, int x, int p) { |
10 | if (M.count(make_pair(u, x))) { |
11 | return M[make_pair(u, x)]; |
12 | } |
13 | int &ret = M[make_pair(u, x)] = 0; |
14 | for (int i = 0, v; i < G[u].size(); i++) { |
15 | v = G[u][i]; |
16 | if (v == p || v > x) continue; |
17 | ret += Q(v, x, u) + 1; |
18 | } |
19 | return ret; |
20 | } |
21 | |
22 | void dfs(int u, int p = 0) { |
23 | if (u != 1) { |
24 | ans[u] = ans[p]; |
25 | if (u > m[p]) { |
26 | ans[u] += Q(u, m[u], p) + 1; |
27 | } else { |
28 | ans[u] += Q(u, m[u], p) - Q(u, m[p], p); |
29 | } |
30 | } |
31 | for (int i = 0, v; i < G[u].size(); i++) { |
32 | v = G[u][i]; |
33 | if (v == p) continue; |
34 | m[v] = max(u, m[u]); |
35 | dfs(v, u); |
36 | } |
37 | } |
38 | |
39 | int main() { |
40 | scanf("%d", &n); |
41 | for (int i = 1, u, v; i < n; i++) { |
42 | scanf("%d %d", &u, &v); |
43 | G[u].push_back(v), G[v].push_back(u); |
44 | } |
45 | dfs(1); |
46 | for (int i = 2; i <= n; i++) { |
47 | printf("%d%c", ans[i], " \n"[i == n]); |
48 | } |
49 | return 0; |
50 | } |
Construction on a Tree
首先从每个集合中选一个数 $a_i$，使得选出的数构成 $2, 3, \cdots, n$ 的排列。然后对于每个集合的 $x \neq a_i$，连有向边 $x \to a_i$，最后求出 $1$ 号点为根的一棵生成树即可，如果不能选出排列或生成树就无解。考虑这样的正确性，首先不能选出排列显然是无解的，有生成树显然是有解的，如果没有生成树代表与某个大小为 $x$ 联通块和剩下 $n - x$ 个点没有任何关联，自然是无解的了。集合选数可以用网络流，所以复杂度 $O(n \sqrt n)$。
1 | |
2 | using namespace std; |
3 | |
4 | const int maxn = 1e6, inf = 1e9; |
5 | int n, tot, ter[maxn + 3], wei[maxn + 3], nxt[maxn + 3], lnk[maxn + 3]; |
6 | int cur[maxn + 3], dep[maxn + 3], num[maxn + 3], ans[maxn + 3]; |
7 | bool vis[maxn + 3]; |
8 | vector<int> S[maxn + 3], V[maxn + 3], G[maxn + 3]; |
9 | |
10 | int adj(int x) { |
11 | return x & 1 ? x + 1 : x - 1; |
12 | } |
13 | |
14 | int add(int u, int v, int w) { |
15 | ter[++tot] = v, wei[tot] = w; |
16 | nxt[tot] = lnk[u], lnk[u] = tot; |
17 | return tot; |
18 | } |
19 | |
20 | int add_f(int u, int v) { |
21 | int t = add(u, v, 1); |
22 | return add(v, u, 0), t; |
23 | } |
24 | |
25 | bool bfs() { |
26 | queue<int> Q; |
27 | Q.push(1); |
28 | memset(dep, -1, sizeof(dep)); |
29 | dep[1] = 0; |
30 | while (!Q.empty()) { |
31 | int u = Q.front(); |
32 | Q.pop(); |
33 | for (int i = lnk[u], v, w; i; i = nxt[i]) { |
34 | v = ter[i], w = wei[i]; |
35 | if ((~dep[v]) || !w) continue; |
36 | dep[v] = dep[u] + 1; |
37 | Q.push(v); |
38 | } |
39 | } |
40 | return ~dep[n * 2]; |
41 | } |
42 | |
43 | int dfs(int u, int t, int lft) { |
44 | if (u == t) { |
45 | return lft; |
46 | } |
47 | int ret = 0; |
48 | for (int &i = cur[u], v, w; i && ret < lft; i = nxt[i]) { |
49 | v = ter[i], w = wei[i]; |
50 | if (w && dep[u] + 1 == dep[v]) { |
51 | int x = dfs(v, t, min(lft - ret, w)); |
52 | wei[i] -= x, wei[adj(i)] += x, ret += x; |
53 | } |
54 | } |
55 | if (ret < lft) { |
56 | dep[u] = -1; |
57 | } |
58 | return ret; |
59 | } |
60 | |
61 | int flow() { |
62 | int ret = 0; |
63 | while (bfs()) { |
64 | memcpy(cur, lnk, sizeof(cur)); |
65 | ret += dfs(1, n * 2, inf); |
66 | } |
67 | return ret; |
68 | } |
69 | |
70 | void dfs(int u) { |
71 | vis[u] = true; |
72 | for (int i = 0, v; i < G[u].size(); i++) { |
73 | v = G[u][i]; |
74 | if (vis[v]) continue; |
75 | ans[v] = u; |
76 | dfs(v); |
77 | } |
78 | } |
79 | |
80 | int main() { |
81 | scanf("%d", &n); |
82 | for (int i = 1, m; i <= n - 1; i++) { |
83 | scanf("%d", &m); |
84 | S[i].resize(m), V[i].resize(m); |
85 | for (int j = 0; j < m; j++) { |
86 | scanf("%d", &S[i][j]); |
87 | if (S[i][j] != 1) { |
88 | V[i][j] = add_f(S[i][j], i + n); |
89 | } |
90 | } |
91 | } |
92 | for (int i = 2; i <= n; i++) { |
93 | add_f(1, i); |
94 | } |
95 | for (int i = n + 1; i < n * 2; i++) { |
96 | add_f(i, n * 2); |
97 | } |
98 | if (flow() != n - 1) { |
99 | puts("-1"); |
100 | return 0; |
101 | } |
102 | for (int i = 1; i <= n - 1; i++) { |
103 | int x = 0; |
104 | for (int j = 0; j < S[i].size(); j++) { |
105 | if (S[i][j] != 1 && !wei[V[i][j]]) { |
106 | x = S[i][j]; |
107 | break; |
108 | } |
109 | } |
110 | num[i] = x; |
111 | for (int j = 0; j < S[i].size(); j++) { |
112 | if (S[i][j] != x) { |
113 | G[S[i][j]].push_back(x); |
114 | } |
115 | } |
116 | } |
117 | dfs(1); |
118 | for (int i = 1; i <= n; i++) { |
119 | if (!vis[i]) { |
120 | puts("-1"); |
121 | break; |
122 | } |
123 | } |
124 | for (int i = 1; i <= n - 1; i++) { |
125 | printf("%d %d\n", ans[num[i]], num[i]); |
126 | } |
127 | return 0; |
128 | } |
Coloring Torus
对于 $n$ 为偶数，可以构造网格：
发现把一些 $x + n$ 换成 $x$ 也是对的，那么我们就可以取 $n = 2 \lceil \frac{K}{4} \rceil$，然后暴力搞掉几个 $x + n$ 就行了，注意特判 $K = 1$，时间复杂度 $O(n^2)$。
1 | |
2 | using namespace std; |
3 | |
4 | const int maxn = 1000; |
5 | int n, k, c[maxn + 3], a[maxn + 3][maxn + 3]; |
6 | |
7 | int main() { |
8 | scanf("%d", &k); |
9 | if (k == 1) { |
10 | puts("1\n1"); |
11 | return 0; |
12 | } |
13 | n = (((k - 1) >> 2) + 1) << 1; |
14 | for (int i = 0; i < n * 2; i++) { |
15 | c[i] = i; |
16 | } |
17 | for (int i = n * 2 - 1; i >= k; i--) { |
18 | c[i] -= n; |
19 | } |
20 | for (int i = 0; i < n; i++) { |
21 | for (int j = 0; j < n; j++) { |
22 | if (~i & 1) { |
23 | a[i][j] = c[(i + j) % n]; |
24 | } else { |
25 | a[i][j] = c[(i + j) % n + n]; |
26 | } |
27 | } |
28 | } |
29 | printf("%d\n", n); |
30 | for (int i = 0; i < n; i++) { |
31 | for (int j = 0; j < n; j++) { |
32 | printf("%d%c", a[i][j] + 1, " \n"[j == n - 1]); |
33 | } |
34 | } |
35 | return 0; |
36 | } |