2

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

 2 years ago
source link: https://blunt-axe.github.io/2019/12/10/20191210-IOI2020-Homework-5/
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 集训队作业 31 ~ 35 题的题解，下面是题单：

Inversion Sum

f(i,j)f(i,j) 表示 ai>ajai>aj 的概率，直接转移即可，时间复杂度 O(n(n+q))O(n(n+q))。

#include <bits/stdc++.h>
2
using namespace std;
3
4
const int maxn = 3000, mod = 1e9 + 7, inv2 = (mod + 1) >> 1;
5
int n, q, a[maxn + 3], f[maxn + 3][maxn + 3], g[maxn + 3][maxn + 3];
6
7
int main() {
8
	scanf("%d %d", &n, &q);
9
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	for (int i = 1; i < n; i++) {
		for (int j = i + 1; j <= n; j++) {
			f[i][j] = a[i] > a[j];
			f[j][i] = a[j] > a[i];
		}
	}
	int tot = 1;
	for (int x, y; q --> 0; ) {
20
		tot = 2ll * tot % mod;
21
		scanf("%d %d", &x, &y);
22
		for (int i = 1; i <= n; i++) {
23
			if (i != x) g[i][x] = f[i][x], g[x][i] = f[x][i];
24
			if (i != y) g[i][y] = f[i][y], g[y][i] = f[y][i];
25
		}
26
		f[x][y] = 1ll * (g[x][y] + g[y][x]) * inv2 % mod;
27
		f[y][x] = 1ll * (g[x][y] + g[y][x]) * inv2 % mod;
28
		for (int i = 1; i <= n; i++) if (i != x && i != y) {
29
			f[i][x] = 1ll * (g[i][x] + g[i][y]) * inv2 % mod;
30
			f[i][y] = 1ll * (g[i][x] + g[i][y]) * inv2 % mod;
31
			f[x][i] = 1ll * (g[x][i] + g[y][i]) * inv2 % mod;
32
			f[y][i] = 1ll * (g[x][i] + g[y][i]) * inv2 % mod;
33
		}
34
	}
35
	int sum = 0;
36
	for (int i = 1; i < n; i++) {
37
		for (int j = i + 1; j <= n; j++) {
38
			sum = (sum + f[i][j]) % mod;
39
		}
40
	}
41
	printf("%lld\n", 1ll * sum * tot % mod);
42
	return 0;
43
}

Less than 3

在每个相邻的 01 之间插红色隔板，10 之间插蓝色隔板，左右两边补上无限个隔板。这样给一个数取反相当于将一个隔板移动一格，那么我们枚举隔板的一个匹配，显然移动步数的下界是隔板距离之和。发现下界可以取到，所以直接计算取最小值即可，时间复杂度 O(n2)O(n2)。

#include <bits/stdc++.h>
2
using namespace std;
3
4
const int maxn = 1e4, inf = 1e9;
5
int n, k, l, a[maxn + 3], b[maxn + 3];
6
char s[maxn + 3], t[maxn + 3];
7
8
int _abs(int x) {
9
	return x < 0 ? -x : x;
}
int solve(int p, int q) {
	int ret = 0;
	for (int i = 0; i + p <= k || i + q <= l; i++) {
		int x = i + p <= k ? a[i + p] : n;
		int y = i + q <= l ? b[i + q] : n;
		ret += _abs(x - y);
	}
	for (int i = 1; p - i >= 1 || q - i >= 1; i++) {
20
		int x = p - i >= 1 ? a[p - i] : 0;
21
		int y = q - i >= 1 ? b[q - i] : 0;
22
		ret += _abs(x - y);
23
	}
24
	return ret;
25
}
26
27
int main() {
28
	scanf("%d %s %s", &n, s + 1, t + 1);
29
	for (int i = 1; i < n; i++) {
30
		if (s[i] != s[i + 1]) {
31
			a[++k] = i;
32
		}
33
	}
34
	for (int i = 0; i < 3; i++) {
35
		a[++k] = 0, a[++k] = n;
36
	}
37
	for (int i = 1; i < n; i++) {
38
		if (t[i] != t[i + 1]) {
39
			b[++l] = i;
40
		}
41
	}
42
	for (int i = 0; i < 3; i++) {
43
		b[++l] = 0, b[++l] = n;
44
	}
45
	if (t[1] != s[1]) {
46
		b[++l] = 0;
47
	}
48
	sort(a + 1, a + k + 1);
49
	sort(b + 1, b + l + 1);
50
	int ans = inf;
51
	for (int i = 1; i <= k; i += 2) {
52
		ans = min(ans, solve(i, 1));
53
	}
54
	for (int i = 1; i <= l; i += 2) {
55
		ans = min(ans, solve(1, i));
56
	}
57
	printf("%d\n", ans);
58
	return 0;
59
}

Permutation and Minimum

首先我们将每个不是 −1−1 的 pipi 变成 2n−pi+12n−pi+1 方便处理。(p2i−1,p2i)(p2i−1,p2i) 可以分成三种情况：(x,y),(x,−1),(−1,−1)(x,y),(x,−1),(−1,−1)。(x,y)(x,y) 可以直接扔掉，我们先考虑不存在 (x,−1)(x,−1) 的情况。可以看作是有 2n2n 个点，将它们两两配对后右端点取值形成的集合的个数。考虑前 ii 个数，ii 可以匹配之前的某一个没选过的端点，或者自己暂时不选。发现方案数就是卡特兰数。当然对于一种匹配的方案，有 nn 对点，我们要把它分配到 nn 个位置，答案要额外地乘上 n!n!。

接下来考虑 (x,−1)(x,−1)，一个 (x,−1)(x,−1) 就表示 xx 号点要匹配一个空的点，我们称 xx 为特殊点。记 f(i,j,k)f(i,j,k) 表示考虑前 ii 个位置，有 jj 个未匹配的普通点，有 kk 个未匹配的特殊点。那么如果第 ii 个位置是特殊点，它要么暂时不选，要么匹配普通点。如果第 ii 个位置是普通点，它要么暂时不选，要么匹配普通点，要么匹配特殊点。注意匹配不同的特殊点时在原序列中的位置是不同的，所以方案数要乘上特殊点个数。那么最后的方案数就是 f(n,0,0)×c!f(n,0,0)×c!，cc 表示 (−1,−1)(−1,−1) 的对数。直接 dp，时间复杂度 O(n3)O(n3)。

#include <bits/stdc++.h>
2
using namespace std;
3
4
const int maxn = 300, maxm = maxn * 2, mod = 1e9 + 7;
5
int n, m, a[maxm + 3], cnt[maxm + 3], f[maxm + 3][maxn + 3][maxn + 3];
6
bool tag[maxm + 3];
7
8
void upd(int &x, int y) {
9
	x += y, x < mod ? 0 : x -= mod;
}
int main() {
	scanf("%d", &n);
	m = n * 2;
	for (int i = 1; i <= m; i++) {
		scanf("%d", &a[i]);
		if (a[i] != -1) {
			a[i] = m - a[i] + 1;
		}
20
		cnt[i] = 1;
21
	}
22
	for (int i = 1; i <= m; i += 2) {
23
		if (a[i] != -1 && a[i + 1] != -1) {
24
			cnt[a[i]] = 0, cnt[a[i + 1]] = 0;
25
		}
26
	}
27
	for (int i = 2; i <= m; i++) {
28
		cnt[i] += cnt[i - 1];
29
	}
30
	int num = 1, cur = 0;
31
	for (int i = 1; i <= m; i += 2) {
32
		if (a[i] == -1 && a[i + 1] == -1) {
33
			num = 1ll * num * ++cur % mod;
34
		} else if (a[i] == -1 || a[i + 1] == -1) {
35
			tag[cnt[a[i] + a[i + 1] + 1]] = true;
36
		}
37
	}
38
	m = cnt[m], n = m / 2;
39
	f[0][0][0] = 1;
40
	for (int i = 1; i <= m; i++) {
41
		for (int j = 0; j <= n; j++) {
42
			for (int k = 0; k <= n; k++) {
43
				if (tag[i]) {
44
					upd(f[i][j][k], f[i - 1][j + 1][k]);
45
					if (k > 0) {
46
						upd(f[i][j][k], f[i - 1][j][k - 1]);
47
					}
48
				} else {
49
					upd(f[i][j][k], f[i - 1][j + 1][k]);
50
					upd(f[i][j][k], 1ll * f[i - 1][j][k + 1] * (k + 1) % mod);
51
					if (j > 0) {
52
						upd(f[i][j][k], f[i - 1][j - 1][k]);
53
					}
54
				}
55
			}
56
		}
57
	}
58
	printf("%lld\n", 1ll * f[m][0][0] * num % mod);
59
	return 0;
60
}

A Sequence of Permutations

对于排列 p,qp,q，定义 pqpq 表示第 ii 位为 pqipqi 的排列，p−1p−1 表示第 pipi 位为 ii 的排列，那么我们有 (pq)−1=q−1p−1(pq)−1=q−1p−1，pmpn=pm+npmpn=pm+n，(pq)r=p(qr)(pq)r=p(qr)，并且题目里的 f(p,q)=qp−1f(p,q)=qp−1。记 g(p,q)=pqp−1g(p,q)=pqp−1，那么有：

a1a2a3a4a5a6a7a8a9=p=q=qp−1=qp−1q−1=qp−1q−1pq−1=qp−1q−1p2q−1=qp−1q−1pqpq−1=g(qp−1q−1,p) =qp−1q−1pqp−1qpq−1=qp−1q−1pqp−2qpq−1=g(ε,p)=g(ε,q)=g(ε,qp−1)=g(q,p−1)=g(qp−1,q−1)=g(qp−1,q−1p)=g(qp−1q−1p,p)=g(qp−1q−1p,q)=g(qp−1q−1p,qp−1)a1=p=g(ε,p)a2=q=g(ε,q)a3=qp−1=g(ε,qp−1)a4=qp−1q−1=g(q,p−1)a5=qp−1q−1pq−1=g(qp−1,q−1)a6=qp−1q−1p2q−1=g(qp−1,q−1p)a7=qp−1q−1pqpq−1=g(qp−1q−1,p)=g(qp−1q−1p,p)a8=qp−1q−1pqp−1qpq−1=g(qp−1q−1p,q)a9=qp−1q−1pqp−2qpq−1=g(qp−1q−1p,qp−1)

也就是 g(r,p)g(r,p) 和 g(r,q)g(r,q) 在 66 次之后会变成 g(rqp−1q−1p,p)g(rqp−1q−1p,p) 和 g(rqp−1q−1p,q)g(rqp−1q−1p,q)，所以只要求出 (qp−1q−1p)⌊k−16⌋(qp−1q−1p)⌊k−16⌋ 即可，时间复杂度 O(nlogk)O(nlog⁡k) 或 O(n)O(n)。

#include <bits/stdc++.h>
2
using namespace std;
3
4
const int maxn = 1e5;
5
int n, k;
6
7
struct perm {
8
	int n, a[maxn + 3];
9
	perm(int m) {
		n = m;
		for (int i = 1; i <= n; i++) {
			a[i] = i;
		}
	}
	friend perm operator * (perm p, perm q) {
		perm r(p.n);
		for (int i = 1; i <= p.n; i++) {
20
			r.a[i] = p.a[q.a[i]];
21
		}
22
		return r;
23
	}
24
25
	perm inv() {
26
		perm r(n);
27
		for (int i = 1; i <= n; i++) {
28
			r.a[a[i]] = i;
29
		}
30
		return r;
31
	}
32
33
	void print() {
34
		for (int i = 1; i <= n; i++) {
35
			printf("%d%c", a[i], " \n"[i == n]);
36
		}
37
	}
38
};
39
40
perm g(perm p, perm q) {
41
	return p * q * p.inv();
42
}
43
44
perm qpow(perm p, int k) {
45
	perm q(n);
46
	for (; k; k >>= 1, p = p * p) {
47
		if (k & 1) q = p * q;
48
	}
49
	return q;
50
}
51
52
int main() {
53
	scanf("%d %d", &n, &k);
54
	perm p(n), q(n), r(n);
55
	for (int i = 1; i <= n; i++) {
56
		scanf("%d", &p.a[i]);
57
	}
58
	for (int i = 1; i <= n; i++) {
59
		scanf("%d", &q.a[i]);
60
	}
61
	int x = (k - 1) / 6;
62
	r = q * p.inv() * q.inv() * p;
63
	r = qpow(r, x);
64
	k -= x * 6;
65
	if (k == 1) {
66
		g(r, p).print();
67
	} else if (k == 2) {
68
		g(r, q).print();
69
	} else if (k == 3) {
70
		g(r, q * p.inv()).print();
71
	} else if (k == 4) {
72
		g(r, q * p.inv() * q.inv()).print();
73
	} else if (k == 5) {
74
		g(r, q * p.inv() * q.inv() * p * q.inv()).print();
75
	} else {
76
		g(r, q * p.inv() * q.inv() * p * p * q.inv()).print();
77
	}
78
	return 0;
79
}

Snuke the Phantom Thief

首先枚举选的总个数 TT，对于一种选的方案记 x 坐标从小到大为 x1,x2,⋯,xTx1,x2,⋯,xT。那么 L ai,biai,bi 的限制相当于强制 xbi+1≥ai+1xbi+1≥ai+1，R ai,biai,bi 的限制相当于强制 xT−bi≤ai−1xT−bi≤ai−1。我们可以给每个 xixi 加一个限制 li≤xi≤rili≤xi≤ri，并满足 li≤li+1,ri≤ri+1li≤li+1,ri≤ri+1。D, U 的限制同理，我们搞出 di≤yi≤uidi≤yi≤ui。然后我们建图：

  • 每个珠宝拆成 A 和 B，A 向 B 连边，容量为 11，费用为 −vi−vi。
  • 源点连向每个 x 限制，容量为 11，费用为 00。
  • 每个 x 限制向可行的珠宝 A 连边，容量为 11，费用为 00。
  • 每个珠宝 B 向可行的 y 限制连边，容量为 11，费用为 00。
  • 每个 y 限制连向汇点，容量为 11，费用为 00。

思考一下发现这样是对的，因为如果第 ii 个 x 限制选择的 x 坐标大于第 i+1i+1 个 x 限制选择的 x 坐标的话一定是不优的。于是我们枚举 TT，给每个费用预先加上 10151015，跑最小费用最大流，最后将答案减去 1015T1015T 并取最小值即可。因为最大流的大小是 O(n)O(n) 的，图的规模是 O(n)−O(n2)O(n)−O(n2) 的，我们还要跑 nn 遍这样的算法，所以时间复杂度为 O(n4)O(n4)。

#include <bits/stdc++.h>
2
using namespace std;
3
4
typedef long long ll;
5
const int maxn = 320, maxm = 1e5;
6
const ll lim = 1e15, inf = 1e18;
7
int n, x[maxn + 3], y[maxn + 3], m, a[maxn + 3], b[maxn + 3];
8
int l[maxn + 3], r[maxn + 3], u[maxn + 3], d[maxn + 3];
9
int tot, wei[maxm + 3], ter[maxm + 3], nxt[maxm + 3], lnk[maxn + 3];
int src, snk, pre[maxn + 3];
bool in[maxn + 3];
ll v[maxn + 3], len[maxm + 3], dist[maxm + 3];
char s[maxn + 3];
int func(int x) {
	return x & 1 ? x + 1 : x - 1;
}
void add(int u, int v, int w, ll l) {
20
	ter[++tot] = v, wei[tot] = w, len[tot] = l;
21
	nxt[tot] = lnk[u], lnk[u] = tot;
22
}
23
24
void add_f(int u, int v, int w, ll l) {
25
	add(u, v, w, l);
26
	add(v, u, 0, -l);
27
}
28
29
bool spfa() {
30
	queue<int> Q;
31
	Q.push(src), in[src] = true;
32
	fill(dist + 1, dist + snk + 1, inf);
33
	dist[src] = 0;
34
	while (!Q.empty()) {
35
		int u = Q.front();
36
		Q.pop();
37
		in[u] = false;
38
		ll l = 0;
39
		for (int i = lnk[u], v; i; i = nxt[i]) {
40
			v = ter[i], l = len[i];
41
			if (wei[i] && dist[u] + l < dist[v]) {
42
				dist[v] = dist[u] + l;
43
				pre[v] = i;
44
				if (!in[v]) {
45
					in[v] = true;
46
					Q.push(v);
47
				}
48
			}
49
		}
50
	}
51
	return dist[snk] != inf;
52
}
53
54
void flow(int &res, ll &ans) {
55
	while (spfa()) {
56
		int x = snk;
57
		while (x != src) {
58
			wei[pre[x]]--, wei[func(pre[x])]++;
59
			x = ter[func(pre[x])];
60
		}
61
		res++;
62
		ans += dist[snk];
63
	}
64
}
65
66
int main() {
67
	scanf("%d", &n);
68
	for (int i = 1; i <= n; i++) {
69
		scanf("%d %d %lld", &x[i], &y[i], &v[i]);
70
	}
71
	scanf("%d", &m);
72
	for (int i = 1; i <= m; i++) {
73
		char t[5];
74
		scanf("%s %d %d", t + 1, &a[i], &b[i]);
75
		s[i] = t[1];
76
		if (s[i] == 'U') {
77
			s[i] = 'D';
78
		} else if (s[i] == 'D') {
79
			s[i] = 'U';
80
		}
81
	}
82
	ll ans = 0;
83
	for (int T = 1; T <= n; T++) {
84
		fill(l + 1, l + T + 1, 1);
85
		fill(r + 1, r + T + 1, 100);
86
		fill(u + 1, u + T + 1, 1);
87
		fill(d + 1, d + T + 1, 100);
88
		for (int i = 1; i <= m; i++) {
89
			if (b[i] + 1 > T) {
90
				continue;
91
			}
92
			if (s[i] == 'L') {
93
				l[b[i] + 1] = max(l[b[i] + 1], a[i] + 1);
94
			} else if (s[i] == 'R') {
95
				r[T - b[i]] = min(r[T - b[i]], a[i] - 1);
96
			} else if (s[i] == 'U') {
97
				u[b[i] + 1] = max(u[b[i] + 1], a[i] + 1);
98
			} else if (s[i] == 'D') {
99
				d[T - b[i]] = min(d[T - b[i]], a[i] - 1);
			}
		}
		for (int i = 2; i <= T; i++) {
			l[i] = max(l[i], l[i - 1]);
			u[i] = max(u[i], u[i - 1]);
		}
		for (int i = T - 1; i; i--) {
			r[i] = min(r[i], r[i + 1]);
			d[i] = min(d[i], d[i + 1]);
		}
		src = n * 4 + 1, snk = src + 1;
		tot = 0;
		fill(lnk + 1, lnk + snk + 1, 0);
		for (int i = 1; i <= T; i++) {
			add_f(src, i, 1, 0);
			for (int j = 1; j <= n; j++) {
				if (x[j] >= l[i] && x[j] <= r[i]) {
					add_f(i, j + n, 1, 0);
				}
			}
		}
		for (int i = 1; i <= n; i++) {
			add_f(i + n, i + n * 2, 1, lim - v[i]);
		}
		for (int i = 1; i <= T; i++) {
			add_f(i + n * 3, snk, 1, 0);
			for (int j = 1; j <= n; j++) {
				if (y[j] >= u[i] && y[j] <= d[i]) {
					add_f(j + n * 2, i + n * 3, 1, 0);
				}
			}
		}
		int fl = 0;
		ll mx = 0;
		flow(fl, mx);
		if (fl == T && T * lim - mx > ans) {
			ans = T * lim - mx;
		}
	}
	printf("%lld\n", ans);
	return 0;
}

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK