2

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

 2 years ago
source link: https://blunt-axe.github.io/2019/12/04/20191204-Game-Theory-2/
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

Sharti

「Codeforces 494E」Sharti

的网格，给定 个矩形，它们的并是白色的，剩下的格子是黑色的。两人博弈，每次可以选择一个边长不超过 的正方形满足它的右下角是白色，然后反转这个正方形的颜色。不能操作者输，问先手是否必胜。

数据范围：。

介绍一个翻硬币的模型：给定一排硬币，每次选择一个右端点正面朝上的区间反转，不能操作者输。那么整个局面的 sg 值等于所有正面朝上的硬币单独存在时 sg 值的异或和。证明是考虑另一个问题：本来正面朝上的硬币处有棋子，每次选择一个右端点有棋子的区间然后拿掉右端点的一个棋子，并给其他点加上一个棋子。这两个问题是等价的，因为一个点有两个棋子时它们 sg 值为 ，就可以拿掉它们。

这个模型放到这个题里照样成立，所以我们考虑每个白格单独存在时的 sg 值。考虑打表：

2
3
4
5
6
7
8

发现 时 sg 值都是左边的表， 时 sg 值都是右边的表。所以可以猜测表和不超过 的最大 的幂次有关。记 表示满足 的最大 ，那么有：

考虑对于每个 分别计算。发现我们最后只要求矩形的面积并，考虑线段树维护两个值：。每次区间 时，我们找出区间对应的 个结点把它们的 。然后对于每个点，都有：

直接更新即可。时间复杂度 ，具体细节见代码。

#include <bits/stdc++.h>
2
#define mid ((l + r) >> 1)
3
#define ls (x << 1)
4
#define rs (ls | 1)
5
using namespace std;
6
7
typedef long long ll;
8
const int maxn = 1e5, maxm = 1 << 18;
9
int n, m, k, bit, a[maxn + 3], b[maxn + 3], c[maxn + 3], d[maxn + 3];
int cnt, pos[maxn + 3], tot, cov[maxm + 3], len[maxm + 3], ans[50];
struct event {
	int x, l, r, y;
	friend bool operator < (const event &a, const event &b) {
		return a.x == b.x ? a.y > b.y : a.x < b.x;
	}
} eve[maxn + 3];
void maintain(int x, int l, int r) {
20
	if (cov[x]) {
21
		len[x] = pos[r + 1] - pos[l];
22
	} else if (l == r) {
23
		len[x] = 0;
24
	} else {
25
		len[x] = len[ls] + len[rs];
26
	}
27
}
28
29
void build(int x, int l, int r) {
30
	cov[x] = len[x] = 0;
31
	if (l == r) {
32
		return;
33
	}
34
	build(ls, l, mid);
35
	build(rs, mid + 1, r);
36
}
37
38
void modify(int x, int l, int r, int lx, int rx, int y) {
39
	if (l >= lx && r <= rx) {
40
		cov[x] += y;
41
		maintain(x, l, r);
42
		return;
43
	}
44
	if (lx <= mid) {
45
		modify(ls, l, mid, lx, rx, y);
46
	}
47
	if (rx > mid) {
48
		modify(rs, mid + 1, r, lx, rx, y);
49
	}
50
	maintain(x, l, r);
51
}
52
53
ll solve() {
54
	cnt = tot = 0;
55
	for (int i = 1; i <= m; i++) if (b[i] < d[i]) {
56
		pos[++cnt] = b[i], pos[++cnt] = d[i];
57
	}
58
	if (!cnt) {
59
		return 0;
60
	}
61
	sort(pos + 1, pos + cnt + 1);
62
	cnt = unique(pos + 1, pos + cnt + 1) - (pos + 1);
63
	for (int i = 1; i <= m; i++) if (b[i] < d[i]) {
64
		int l = lower_bound(pos + 1, pos + cnt + 1, b[i]) - pos;
65
		int r = lower_bound(pos + 1, pos + cnt + 1, d[i]) - (pos + 1);
66
		eve[++tot].x = a[i], eve[tot].l = l, eve[tot].r = r, eve[tot].y = 1;
67
		eve[++tot].x = c[i], eve[tot].l = l, eve[tot].r = r, eve[tot].y = -1;
68
	}
69
	sort(eve + 1, eve + tot + 1);
70
	cnt--;
71
	build(1, 1, cnt);
72
	ll sum = 0;
73
	for (int i = 1; i <= tot; i++) {
74
		sum += 1ll * (eve[i].x - eve[i - 1].x) * len[1];
75
		modify(1, 1, cnt, eve[i].l, eve[i].r, eve[i].y);
76
	}
77
	return sum;
78
}
79
80
int main() {
81
	scanf("%d %d %d", &n, &m, &k);
82
	for (int i = 1; i <= m; i++) {
83
		scanf("%d %d %d %d", &a[i], &b[i], &c[i], &d[i]);
84
		a[i]--, b[i]--;
85
	}
86
	for (bit = 0; 1 << bit <= k; bit++);
87
	for (int i = 0; i < bit; i++) {
88
		ans[i] = solve() & 1;
89
		for (int j = 1; j <= m; j++) {
90
			a[j] >>= 1, b[j] >>= 1, c[j] >>= 1, d[j] >>= 1;
91
		}
92
	}
93
	int sg = 0;
94
	for (int i = 0; i < bit; i++) {
95
		if (ans[i] ^ ans[i + 1]) {
96
			sg ^= 1 << i;
97
		}
98
	}
99
	if (sg) {
		puts("Hamed");
	} else {
		puts("Malek");
	}
	return 0;
}

「ZROI 967」银

把游戏左右翻转，变成翻硬币模型，。设 表示 的高位到低位的前缀异或和（例子：），那么我们有 ，以及 。

设当前整个局面的 sg 值为 ，题目中合法的 要满足：。稍加转化得到 ，也就是 。发现对于一个 存在对应的 当且仅当 的最高位在 的二进制下为 ，所以问题转化成了每次加一个数，删一个数，或查询某一位为 的数的数量。维护 ，直接模拟即可，时间复杂度 。

#include <bits/stdc++.h>
2
using namespace std;
3
4
const int maxn = 5e5;
5
int n, m, a[maxn + 3], cur, cnt[maxn + 3];
6
char s[maxn + 3];
7
8
void add(int x, int y) {
9
	for (int i = 20; ~i; i--) {
		if (x >> i & 1) {
			cnt[i] += y;
		}
	}
}
int lb(int x) {
	return x & -x;
}
20
int hb(int x) {
21
	for (int i = 20; ~i; i--) {
22
		if (x >> i & 1) {
23
			return i;
24
		}
25
	}
26
	return -1;
27
}
28
29
int f(int x) {
30
	int t = 0, s = 0;
31
	for (int i = 20; ~i; i--) {
32
		t ^= x >> i & 1;
33
		s |= t << i;
34
	}
35
	return s;
36
}
37
38
int main() {
39
	scanf("%d %s %d", &n, s + 1, &m);
40
	for (int i = 1; i <= n; i++) {
41
		a[i] = s[n - i + 1] ^ '0';
42
	}
43
	for (int i = 1; i <= n; i++) if (a[i]) {
44
		cur ^= f(lb(i)), add(i, 1);
45
	}
46
	for (int x; m --> 0; ) {
47
		scanf("%d", &x), x = n - x + 1;
48
		cur ^= f(lb(x)), add(x, -a[x]);
49
		a[x] ^= 1, add(x, a[x]);
50
		if (!cur) {
51
			puts("0");
52
		} else {
53
			printf("%d\n", cnt[hb(cur)]);
54
		}
55
	}
56
	return 0;
57
}

Tree-Tac-Toe

「Codeforces 1110G」Tree-Tac-Toe

一棵 个点的树，一开始一些点是白色。先手是白色，后手是黑色，每次一个人可以把一个没有颜色的点涂成自己的颜色。出现三个连续的同种颜色时持有该颜色的人就赢了，问最后是谁赢，或平局。

数据范围：。

首先我们可以去掉所有白点。考虑下图中的白点：

我们把它变成：

考虑这样的正确性。注意到 BDEF 这棵子树中谁都不可能赢，所以我们的最优策略是把 B 点变成自己的颜色。假设先手把 B 变成白色，那么如果后手不把 E 变成黑色，那么先手在下一步就能把 B 变成白色，然后他就赢了。也就是说第二步后手一定会把 E 变成黑色。那么剩下的两个点就和原图没有关系了，如果后手选了其中一个点先手把另一个点选掉即可。

接下来考虑没有白点的图。考虑下面两种情况：

如果一个点度数为 ，或者它度数为 且有至少两个非叶儿子，那么一定先手必胜。

考虑排出这些情况的图，图中每个点的度数都不超过 ，并且度数为 的点最多只有 个。考虑下面这种情况：

即两个度数为 的点中间夹着奇数个点，其实它等价于下面的图：

即两个白点之间夹着奇数个点。考虑这样的策略：每次选择左边白点向右的第二个点，这样黑点必须填在左边两个白点之间，然后问题就转化成了 的子问题。可以证明除了这种情况一定是平局，直接模拟，时间复杂度 。

#include <bits/stdc++.h>
2
using namespace std;
3
4
const int maxn = 2e6;
5
int T, n, deg[maxn + 3];
6
vector<int> G[maxn + 3];
7
char s[maxn + 3];
8
9
void clear(int i) {
	vector<int>().swap(G[i]);
	deg[i] = 0;
}
void add(int u, int v) {
	G[u].push_back(v), G[v].push_back(u);
	deg[u]++, deg[v]++;
}
int main() {
20
	scanf("%d", &T);
21
	while (T --> 0) {
22
		scanf("%d", &n);
23
		for (int i = 1; i <= n; i++) {
24
			clear(i);
25
		}
26
		for (int i = 1, u, v; i < n; i++) {
27
			scanf("%d %d", &u, &v), add(u, v);
28
		}
29
		scanf("%s", s + 1);
30
		for (int i = 1; i <= n; i++) {
31
			if (s[i] == 'W') {
32
				clear(++n), add(i, n);
33
				clear(++n), add(n - 1, n);
34
				clear(++n), add(n - 2, n);
35
			}
36
		}
37
		bool flag = false;
38
		for (int i = 1; i <= n; i++) {
39
			if (deg[i] >= 4) {
40
				puts("White");
41
				flag = true;
42
				break;
43
			}
44
			if (deg[i] == 3) {
45
				int cnt = 0;
46
				for (int j = 0; j < 3; j++) {
47
					cnt += deg[G[i][j]] != 1;
48
				}
49
				if (cnt >= 2) {
50
					puts("White");
51
					flag = true;
52
					break;
53
				}
54
			}
55
		}
56
		if (!flag) {
57
			int x = 0, y = 0;
58
			for (int i = 1; i <= n; i++) {
59
				if (deg[i] == 3) {
60
					if (!x) {
61
						x = i;
62
					} else if (!y) {
63
						y = i;
64
					} else {
65
						exit(1);
66
					}
67
				}
68
			}
69
			if (x && y && ((n - 4) & 1)) {
70
				puts("White");
71
			} else {
72
				puts("Draw");
73
			}
74
		}
75
	}
76
	return 0;
77
}

Chip Game

「Codeforces 1033G」Chip Game

有 堆石子，第 堆有 个。两人玩游戏，A 每轮从一堆中拿 个石子，B 每轮从一堆中拿 个石子，不能拿的人输。对于一种 ，共有四种情况：

  • 不管谁先手都是 A 赢。（A 赢）
  • 不管谁先手都是 B 赢。（B 赢）
  • A 先手 A 赢，B 先手 B 赢。（先手赢）
  • A 先手 B 赢，B 先手 A 赢。（后手赢）

问对于所有 ，四种情况各有多少种。

数据范围：。

考虑特定 的情况。首先把所有 都对 取模，容易证明这样是对的。不妨设 ，对于每一个 讨论：

  1. ，那么 就谁都不能选。
  2. ，那么只有 A 能选一次，B 不能选。
  3. ，那么 A, B 都只能选一次。
  4. ，那么 A 选完后 B 不能选，B 选完后谁都不能选。

那么我们扔掉 1，然后分类讨论：

  • 若存在 2，那么 A 赢。
  • 若不存在 2 且存在至少两个 4，那么 A 肯定可以抢到一个 4 把它变成 2，也就是 A 赢。
  • 若不存在 2, 4，那么相当于先手后手抢 3，奇数个 3 先手赢，偶数个 3 后手赢。
  • 若不存在 2 且只有一个 4，那么如果 A 先手他可以抢到 4，如果 B 先手他必须抢 4，然后变成全是 3 的情况。所以如果奇数个 3，那么 A 赢，否则先手赢。

这样就得到了一个 的算法，不够快。考虑只计算先手、后手赢的情况数，其他两种情况可以用总数减去这些数来推出。枚举 ，首先不能有 2，也就是要满足 。其次 4 只有 个，也就是 的 只有不超过一个。同时我们也要记录 3 的个数，也就是 的个数。我们记录关键的端点，排完序扫一遍即可，时间复杂度 。

#include <bits/stdc++.h>
2
using namespace std;
3
4
typedef long long ll;
5
const int maxn = 100, maxm = 1e5;
6
int n, m, t[maxn + 3], tot, cur[5];
7
ll v[maxn + 3];
8
9
struct event {
	int x, t, v;
	friend bool operator < (const event &a, const event &b) {
		return a.x < b.x;
	}
} ev[maxn * 3 + 3];
void add(int a, int b, int c) {
	ev[++tot].x = a, ev[tot].t = b, ev[tot].v = c;
}
20
int main() {
21
	scanf("%d %d", &n, &m);
22
	for (int i = 1; i <= n; i++) {
23
		scanf("%lld", &v[i]);
24
	}
25
	ll A = 0, B = 0;
26
	for (int s = 2; s <= m * 2; s++) {
27
		for (int i = 1; i <= n; i++) {
28
			t[i] = v[i] % s;
29
		}
30
		int l = max(1, s - m), r = (s - 1) / 2;
31
		for (int i = 1; i <= n; i++) {
32
			l = max(l, min(t[i] + 1, s - t[i]));
33
		}
34
		if (l > r) continue;
35
		tot = 0;
36
		add(l, 0, 0), add(r + 1, 0, 0);
37
		for (int i = 1; i <= n; i++) {
38
			int L = max(l, s - t[i]), R = min(r, t[i] / 2);
39
			if (L <= R) add(L, 1, 1), add(R + 1, 1, -1);
40
		}
41
		for (int i = 1; i <= n; i++) {
42
			int x = max(l, max(s - t[i], t[i] / 2 + 1));
43
			if (x <= r) add(x, 2, 1);
44
		}
45
		sort(ev + 1, ev + tot + 1);
46
		memset(cur, 0, sizeof(cur));
47
		ev[0].x = l;
48
		for (int i = 1; i <= tot; i++) {
49
			int cnt = cur[1], sum = cur[2];
50
			int len = ev[i].x - ev[i - 1].x;	
51
			if (cnt == 0 && (sum & 1)) A += len;
52
			if (cnt == 0 && (~sum & 1)) B += len;
53
			if (cnt == 1 && (~sum & 1)) A += len;
54
			cur[ev[i].t] += ev[i].v;
55
		}
56
	}
57
	A <<= 1, B <<= 1;
58
	for (int i = 1; i <= m; i++) {
59
		int x = 0;
60
		for (int j = 1; j <= n; j++) {
61
			x ^= (v[j] / i) & 1;
62
		}
63
		if (x) A++;
64
		else B++;
65
	}
66
	ll C = (1ll * m * m - (A + B)) / 2;
67
	printf("%lld %lld %lld %lld\n", C, C, A, B);
68
	return 0;
69
}

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK