5

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

 3 years ago
source link: https://blunt-axe.github.io/2019/12/06/20191206-IOI2020-Homework-4/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

本文包括 IOI 2020 集训队作业 27 ~ 30 题的题解，下面是题单：

Lexicographic constraints

二分答案，暴力模拟，时间复杂度 O(nlog2n)O(nlog2⁡n)。

#include <bits/stdc++.h>
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++) {
		if (a[i] <= a[i - 1]) {
			if (k == 1) {
				return false;
			}
			while (!M.empty() && M.rbegin() -> first > a[i]) {
				map<int, int>::iterator it = M.end();
				M.erase(--it);
			}
			for (int j = a[i]; j >= 0; j--) {
				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

考虑结点 uu 比父亲多走到了哪些点。设 pupu 表示 uu 的父亲，m(u)m(u) 表示路径 1−pu1−pu 中结点编号的最大值。令 Q(u,x)Q(u,x) 表示 uu 只经过 ≤x≤x 的点能走到多少个后代结点（uu 自己不算）。那么对于所有 u>1u>1，我们有：

ans(u)−ans(pu)={Q(u,m(u))+1Q(u,m(u))−Q(u,m(pu))(u>m(pu))(u<m(pu))ans(u)−ans(pu)={Q(u,m(u))+1(u>m(pu))Q(u,m(u))−Q(u,m(pu))(u<m(pu))

原因是如果 u>m(pu)u>m(pu)，那么以 pupu 为起点时就不会访问到 uu，我们就要新加入 uu 以及它子树中的信息。否则一定会访问到 uu，但是从 pupu 出发只会经过 ≤m(pu)≤m(pu) 的点，而从 uu 出发会经过 ≤m(u)≤m(u) 的点，所以要进行一定的修改。那么现在我们只要求出 Q(u,m(u)),Q(u,m(pu))Q(u,m(u)),Q(u,m(pu)) 即可。Q(u,x)Q(u,x) 有递归式：

Q(u,x)=∑v∈son(u),v≤xQ(v,x)+1Q(u,x)=∑v∈son(u),v≤xQ(v,x)+1

发现直接递归 + 记忆化的复杂度是正确的。因为对于 Q(u,m(u))Q(u,m(u))，我们找到所有它后代中第一次 >m(u)>m(u) 的点并剪掉它这棵子树，之后 uu 的子树中点 vv 的询问就只剩下 Q(v,m(u))Q(v,m(u)) 了。也就是说每个点只会有 Q(u,m(u))Q(u,m(u)) 的询问。同理 Q(u,m(pu))Q(u,m(pu)) 递归到每个点也只有常数种询问，所以直接暴力即可，时间复杂度 O(nlogn)O(nlog⁡n) 或 O(n)O(n)。

#include <bits/stdc++.h>
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) {
	if (M.count(make_pair(u, x))) {
		return M[make_pair(u, x)];
	}
	int &ret = M[make_pair(u, x)] = 0;
	for (int i = 0, v; i < G[u].size(); i++) {
		v = G[u][i];
		if (v == p || v > x) continue;
		ret += Q(v, x, u) + 1;
	}
	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

首先从每个集合中选一个数 aiai，使得选出的数构成 2,3,⋯,n2,3,⋯,n 的排列。然后对于每个集合的 x≠aix≠ai，连有向边 x→aix→ai，最后求出 11 号点为根的一棵生成树即可，如果不能选出排列或生成树就无解。考虑这样的正确性，首先不能选出排列显然是无解的，有生成树显然是有解的，如果没有生成树代表与某个大小为 xx 联通块和剩下 n−xn−x 个点没有任何关联，自然是无解的了。集合选数可以用网络流，所以复杂度 O(nn−−√)O(nn)。

#include <bits/stdc++.h>
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
int adj(int x) {
	return x & 1 ? x + 1 : x - 1;
}
int add(int u, int v, int w) {
	ter[++tot] = v, wei[tot] = w;
	nxt[tot] = lnk[u], lnk[u] = tot;
	return tot;
}
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");
		return 0;
	}
	for (int i = 1; i <= n - 1; i++) {
		int x = 0;
		for (int j = 0; j < S[i].size(); j++) {
			if (S[i][j] != 1 && !wei[V[i][j]]) {
				x = S[i][j];
				break;
			}
		}
		num[i] = x;
		for (int j = 0; j < S[i].size(); j++) {
			if (S[i][j] != x) {
				G[S[i][j]].push_back(x);
			}
		}
	}
	dfs(1);
	for (int i = 1; i <= n; i++) {
		if (!vis[i]) {
			puts("-1");
			break;
		}
	}
	for (int i = 1; i <= n - 1; i++) {
		printf("%d %d\n", ans[num[i]], num[i]);
	}
	return 0;
}

Coloring Torus

对于 nn 为偶数，可以构造网格：

Ai,j={(i+j)modnn+(i+j)modn(i≡0(mod2))(i≡1(mod2))Ai,j={(i+j)modn(i≡0(mod2))n+(i+j)modn(i≡1(mod2))

发现把一些 x+nx+n 换成 xx 也是对的，那么我们就可以取 n=2⌈K4⌉n=2⌈K4⌉，然后暴力搞掉几个 x+nx+n 就行了，注意特判 K=1K=1，时间复杂度 O(n2)O(n2)。

#include <bits/stdc++.h>
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) {
		puts("1\n1");
		return 0;
	}
	n = (((k - 1) >> 2) + 1) << 1;
	for (int i = 0; i < n * 2; i++) {
		c[i] = i;
	}
	for (int i = n * 2 - 1; i >= k; i--) {
		c[i] -= n;
	}
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
}

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK