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

0%

「专题选做」博弈论题目选做 1

发表于 更新于

Candy Piles

「AGC 002E」Candy Piles

题目大意

有 $n$ 个数，两人玩游戏，每次可以取最大的变 $0$ 或把所有的非零数减 $1$，把全部的数变 $0$ 的人会输，问是否先手必胜。

数据范围：$n \le 10^5$。

思路分析

首先发现操作方法是对偶的，可以搞出一个二维 dp，打表发现对角线上的数是一样的，所以我们可以找到和 $(n, a[n])$ 同对角线的 $x$ 坐标最小的点算出 dp 值。时间复杂度 $O(n)$。

代码实现

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
const int maxn = 1e5;
5
int n, a[maxn + 3];
6
7
int main() {
8
	scanf("%d", &n);
9
	for (int i = 1; i <= n; i++) {
10
		scanf("%d", &a[i]);
11
	}
12
	sort(a + 1, a + n + 1);
13
	int x = n, y = 1;
14
	while (x > 1 && y + 1 <= a[x - 1]) {
15
		x--, y++;
16
	}
17
	if (y > a[x - 1]) {
18
		puts((a[x] - y) & 1 ? "First" : "Second");
19
	} else {
20
		int p = (a[x] - y - 1) & 1, z = x - 1;
21
		while (z > 1 && a[z - 1] == a[z]) z--;
22
		int q = (x - 1 - z) & 1;
23
		puts(p && q ? "Second" : "First");
24
	}
25
	return 0;
26
}

Paper-strip Game

「PE 306」Paper-strip Game

题目描述

有长度为 $n$ 的纸带，两个人轮流操作，每次选相邻的两个白格染黑，不能操作者输。问对于所有 $n \le 10^6$ 的情况有多少种是先手必胜的。

思路分析

容易想到 $O(n^2)$ 算法，打表发现有循环节，直接计算即可。答案为 $852938$。

代码实现

1
// 打表代码
2
#include <bits/stdc++.h>
3
using namespace std;
4
5
const int maxn = 1e6;
6
int n, sg[maxn + 3], m, a[maxn + 3];
7
8
int main() {
9
	scanf("%d", &n);
10
	sg[0] = 0;
11
	for (int i = 1; i <= n; i++) {
12
		m = 0;
13
		for (int j = 0; j <= i - 2; j++) {
14
			a[m++] = sg[j] ^ sg[i - 2 - j];
15
		}
16
		sort(a , a + m);
17
		m = unique(a, a + m) - a;
18
		a[m] = -1;
19
		for (int j = 0; j <= m; j++) {
20
			if (a[j] != j) {
21
				sg[i] = j;
22
				break;
23
			}
24
		}
25
	}
26
	for (int i = 1; i <= n; i++) {
27
		putchar(sg[i] ^ '0');
28
	}
29
	puts("");
30
	return 0;
31
}

Combat on a Tree

「SPOJ COT3」Combat on a Tree

题目描述

给定一棵 $n$ 个点的树，每个点有黑白两种颜色。两个人玩游戏，每次可以选一个白点并把它和它的祖先全部变黑，不能操作的人输。问先手是否必胜以及先手必胜时第一步可以选哪些点。

数据范围：$n \le 10^5$。

思路分析

选一个点并染黑祖先可以看作把这个点到根的路径删除，分裂出若干个子问题。我们考虑对于每棵子树算出 sg 值，容易得到一个 $O(n^2)$ 的算法。考虑用 01-Trie 维护，我们只要支持单点加入，整体异或以及 Trie 合并，所以时间复杂度 $O(n \log n)$。

代码实现

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
const int maxn = 1e5, maxk = maxn * 2, logn = 16, maxm = maxn * (logn + 2);
5
int n, col[maxn + 3], dp[maxn + 3], f[maxn + 3], g[maxn + 3], rt[maxn + 3];
6
int tot, val[maxm + 3], ch[maxm + 3][logn + 3], tag[maxm + 3];
7
int cnt, ter[maxk + 3], nxt[maxk + 3], lnk[maxn + 3];
8
bool full[maxm + 3];
9
10
void add(int u, int v) {
11
	ter[++cnt] = v, nxt[cnt] = lnk[u], lnk[u] = cnt;
12
}
13
14
#define ls ch[x][0]
15
#define rs ch[x][1]
16
17
void maintain(int x) {
18
	if (val[x] == -1) {
19
		return;
20
	}
21
	full[x] = full[ls] && full[rs];
22
}
23
24
void push_down(int x) {
25
	if (val[x] == -1) {
26
		return;
27
	}
28
	if (tag[x] >> val[x] & 1) {
29
		swap(ls, rs);
30
		tag[x] ^= 1 << val[x];
31
	}
32
	tag[ls] ^= tag[x], tag[rs] ^= tag[x];
33
	tag[x] = 0;
34
}
35
36
void modify(int x, int y) {
37
	if (x) {
38
		tag[x] ^= y;
39
	}
40
}
41
42
int new_node() {
43
	int ret, x = ret = ++tot;
44
	for (int i = logn; ~i; i--) {
45
		val[x] = i;
46
		ls = ++tot;
47
		x = ls;
48
	}
49
	val[x] = -1, full[x] = true;
50
	return ret;
51
}
52
53
int merge(int x, int y) {
54
	if (!x || !y) {
55
		return x + y;
56
	}
57
	push_down(x);
58
	push_down(y);
59
	ls = merge(ch[x][0], ch[y][0]);
60
	rs = merge(ch[x][1], ch[y][1]);
61
	maintain(x);
62
	return x;
63
}
64
65
int mex(int x) {
66
	if (!x || val[x] == -1) {
67
		return 0;
68
	}
69
	if (full[x]) {
70
		return 1 << (val[x] + 1);
71
	}
72
	push_down(x);
73
	if (!full[ls]) {
74
		return mex(ls);
75
	} else {
76
		return mex(rs) | 1 << val[x];
77
	}
78
}
79
80
void dfs(int u, int pa = 0) {
81
	for (int i = lnk[u], v; i; i = nxt[i]) {
82
		v = ter[i];
83
		if (v == pa) continue;
84
		dfs(v, u);
85
		f[v] ^= dp[v];
86
		modify(rt[v], dp[v]);
87
		rt[u] = merge(rt[u], rt[v]);
88
		f[u] ^= dp[v];
89
	}
90
	if (!col[u]) {
91
		rt[u] = merge(rt[u], new_node());
92
	}
93
	modify(rt[u], f[u]);
94
	dp[u] = mex(rt[u]);
95
}
96
97
void solve(int u, int pa = 0) {
98
	g[u] ^= f[u];
99
	for (int i = lnk[u], v; i; i = nxt[i]) {
100
		v = ter[i];
101
		if (v == pa) continue;
102
		g[v] ^= g[u];
103
		solve(v, u);
104
	}
105
}
106
107
int main() {
108
	scanf("%d", &n);
109
	for (int i = 1; i <= n; i++) {
110
		scanf("%d", &col[i]);
111
	}
112
	for (int i = 1, u, v; i < n; i++) {
113
		scanf("%d %d", &u, &v);
114
		add(u, v), add(v, u);
115
	}
116
	dfs(1);
117
	if (!dp[1]) {
118
		puts("-1");
119
	} else {
120
		solve(1);
121
		for (int i = 1; i <= n; i++) {
122
			if (!col[i] && !g[i]) {
123
				printf("%d\n", i);
124
			}
125
		}
126
	}
127
	return 0;
128
}

Fox and Card Game

「Codeforces 388C」Fox and Card Game

题目描述

$n$ 堆卡片，第 $i$ 堆有 $m_i$ 张，每张上有一个数。两人轮流取卡片，先手可以取堆顶，后手可以取堆底，每个人都想最大化自己拿到卡片的和，问先手最后拿到卡片的和。

数据范围：$n, m_i \le 100$。

思路分析

考虑 $m_i = 1$ 的情况，肯定是从大到小排序后先手取奇数位后手取偶数位。接下来考虑所有情况，发现先手可以每一堆取至少前 $\lfloor \frac{m_i}{2} \rfloor$ 个，后手可以通过模仿先手来保证自己取至少后 $\lfloor \frac{m_i}{2} \rfloor$ 个。如果 $m_i$ 是奇数的话还会剩下中间的一个，就转化成了 $m_i = 1$ 的情况。排序即可，时间复杂度 $O(nm)$。

代码实现

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
const int maxn = 100;
5
int n, m, a[maxn + 3], k, b[maxn + 3], sum, num;
6
7
int main() {
8
	scanf("%d", &n);
9
	for (int i = 1; i <= n; i++) {
10
		scanf("%d", &m);
11
		for (int j = 1; j <= m; j++) {
12
			scanf("%d", &a[j]);
13
			sum += a[j];
14
			if (j * 2 <= m) {
15
				num += a[j];
16
			}
17
		}
18
		if (m & 1) {
19
			b[++k] = a[(m + 1) >> 1];
20
		}
21
	}
22
	sort(b + 1, b + k + 1);
23
	reverse(b + 1, b + k + 1);
24
	for (int i = 1; i <= k; i += 2) {
25
		num += b[i];
26
	}
27
	printf("%d %d\n", num, sum - num);
28
	return 0;
29
}

Tree Game

「AGC 010F」Tree Game

题目描述

一个 $n$ 个点的树，第 $i$ 个点上有 $a_i$ 颗石子，一开始 $k$ 号点上有旗子。两人博弈，每次一个人拿掉旗子所在点的一个石子，然后把旗子移到某个邻居，不能操作者输。求出所有先手必胜的 $k$。

数据范围：$n \le 3000$。

思路分析

对于某个 $k$，考虑以它为根后每个子树的子问题。也就是说，$f(u)$ 表示割掉 $u$ 和父亲的边后，旗子一开始在点 $u$ 是否先手必胜。我们断言：

  • 如果存在儿子 $v$ 满足 $a_u > a_v$ 并且 $f(v)$ 是必败态，那么 $f(u)$ 是必胜态。
  • 否则，$f(u)$ 是必败态。

证明留作习题。直接做即可，时间复杂度 $O(n^2)$。

代码实现

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
const int maxn = 3000;
5
int n, a[maxn + 3];
6
vector<int> G[maxn + 3];
7
8
bool dfs(int u, int pa = 0) {
9
	bool flag = false;
10
	for (int i = 0, v; i < G[u].size(); i++) {
11
		v = G[u][i];
12
		if (v == pa) continue;
13
		flag |= a[u] > a[v] && !dfs(v, u);
14
	}
15
	return flag;
16
}
17
18
int main() {
19
	scanf("%d", &n);
20
	for (int i = 1; i <= n; i++) {
21
		scanf("%d", &a[i]);
22
	}
23
	for (int i = 1, u, v; i < n; i++) {
24
		scanf("%d %d", &u, &v);
25
		G[u].push_back(v), G[v].push_back(u);
26
	}
27
	for (int i = 1; i <= n; i++) {
28
		if (dfs(i)) printf("%d ", i);
29
	}
30
	puts("");
31
	return 0;
32
}

Choosing Carrots

「Codeforces 794E」Choosing Carrots

题目描述

有 $n$ 个数 $a_1, a_2, \cdots, a_n$，两人博弈，每次去掉两头的一个数，最后剩下一个数。先手想最大化剩余数，后手想最小化剩余数。问对于每个 $k$，先手一开始随便删掉 $k$ 个数后再开始博弈，最后剩余的数是多少。

数据范围：$n \le 3 \times 10^5$。

思路分析

先不考虑 $k$，$n$ 为偶数时显然答案是 $\max(a_{\frac{n}{2}}, a_{\frac{n}{2} + 1})$，$n$ 为奇数时答案就是：

然后考虑 $k$，分奇偶性讨论，对于每个值考虑它带来的影响。它肯定是对答案数组有一个后缀的更新，所以单点更新完再做前缀最大值即可，时间复杂度 $O(n)$。

代码实现

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
const int maxn = 3e5, inf = 1e9;
5
int n, mx, a[maxn + 3], f[maxn + 3];
6
7
void upd(int &x, int y) {
8
	x = max(x, y);
9
}
10
11
int main() {
12
	scanf("%d", &n);
13
	for (int i = 1; i <= n; i++) {
14
		scanf("%d", &a[i]);
15
		mx = max(mx, a[i]);
16
	}
17
	for (int i = 2; i < n; i++) {
18
		upd(f[min(i - 1, n - i) * 2 + 1], min(a[i], max(a[i - 1], a[i + 1])));
19
	}
20
	for (int i = 1; i < n; i++) {
21
		upd(f[min(i, n - i) * 2], max(a[i], a[i + 1]));
22
	}
23
	for (int i = n - 2; i >= 2; i--) {
24
		upd(f[i], f[i + 2]);
25
	}
26
	for (int i = n; i >= 2; i--) {
27
		printf("%d ", f[i]);
28
	}
29
	printf("%d\n", mx);
30
	return 0;
31
}