Chro's Blog

だから 迷わない 頑張ろう

Those things that hurt, instruct.


「BZOJ 4730」「UOJ 266」「清华集训2016」Alice和Bob又在玩游戏

  1. 1. Description
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. 题解

Description

Alice和Bob在玩游戏。有n个节点,m条边(0<=m<=n-1),构成若干棵有根树,每棵树的根节点是该连通块内编号最小的点。Alice和Bob轮流操作,每回合选择一个没有被删除的节点x,将x及其所有祖先全部删除,不能操作的人输。注:树的形态是在一开始就确定好的,删除节点不会影响剩余节点父亲和儿子的关系。比如:1-3-2 这样一条链,1号点是根节点,删除1号点之后,3号点还是2号点的父节点。问有没有先手必胜策略。n<=10^5。

Sample Input

1
2
3
4
5
6
7
8
9
4
2 1
1 2
3 2
1 2
1 3
2 0
3 1
1 2

Sample Output

1
2
3
4
Alice
Alice
Bob
Alice

题解

首先每个子树之间都是独立的组合游戏这个很显然,所以以下讨论都是针对单个树的情形。

而且本题还有个更强的但是用不上的结论:如果输入的森林只包含一个连通的树,那么除非只有一个节点,先手一定取胜,考虑 Chomp! 游戏。

每个子树,我们在它的根上记录 sg(u) 和 g(u)。以下将叙述它们的含义。

考虑 SG 定理,对于「一个子树」的游戏状态,它的下一步状态,必然是删除从根到某个节点的一条路径,并剩下几个连通块。

第一种情况是删掉了根节点,定义 g(u, u) 为 u 的每个子节点 v 的 sg(v) 的异或和。

用 g(u, i) 表示删掉 u~i 的路径后,以 u 为根的子树的剩余部分的 SG 函数(异或和)。

我们显然不能每次都暴力计算 g(u, i)。注意到一个性质:对于 u 的每个子节点 v,我们总有 g(u, i)=g(v, i)^g(u, u)^sg(v)。

不难理解该公式:当根节点从 v 向上移动到 u 时,删除一条路径「剩下的部分」多出了一些子树,而这些子树的 SG 函数的异或和,就是 g(u, u)^sg(v)。两项都含有 sg(v),抵消了。

所以我们得到了一个算法:自底向上维护 g(u),g(u) 初始时只 g(u, u) 一个元素,其余的都通过子节点的 g(v) 整体异或同一个数,然后再合并。而 g(u) 中最小的没出现过的自然数就是 sg(u) 了。

用 Trie 树存储每个数的二进制表示,并类比线段树进行合并,我们可以在 $O(n\log_2n)$ 的时间内解决本题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
const int maxm = 2500005;
const int full = 1 << 17;
struct edge { int to, next; } e[maxn << 1];
int T, n, m, tot, head[maxn];
int sg[maxn], root[maxn], flag[maxm];
int next[maxm][2], ntot, val[maxm];
bool vis[maxn];
void update(int o) { val[o] = val[next[o][0]] + val[next[o][1]]; }
void pushdown(int o, int k) {
if (!flag[o] || k == 1) {
flag[o] = 0;
return;
}
if (flag[o] & (k >> 1)) swap(next[o][0], next[o][1]);
flag[next[o][0]] ^= flag[o], flag[next[o][1]] ^= flag[o];
flag[o] = 0;
}
void insert(int &o, int v, int k) {
if (!o) o = ++ntot;
pushdown(o, k);
if (k == 1) val[o] = 1;
else {
insert(next[o][bool(v & (k >> 1))], v, k >> 1);
update(o);
}
}
int merge(int x, int y, int k) {
if (!x || !y) return x + y;
if (k == 1) return x;
pushdown(x, k), pushdown(y, k);
next[x][0] = merge(next[x][0], next[y][0], k >> 1);
next[x][1] = merge(next[x][1], next[y][1], k >> 1);
update(x);
return x;
}
int mex(int o, int k) {
if (k == 1) return 0;
if (val[next[o][0]] & (k >> 1)) return mex(next[o][1], k >> 1) | (k >> 1);
else return mex(next[o][0], k >> 1);
}
void dfs(int u, int p) {
int rem = 0;
vis[u] = true;
for (int t = head[u]; t; t = e[t].next) {
int v = e[t].to;
if (v == p) continue;
dfs(v, u);
rem ^= sg[v];
}
insert(root[u], rem, full);
for (int t = head[u]; t; t = e[t].next) {
int v = e[t].to;
if (v == p) continue;
flag[root[v]] ^= rem ^ sg[v];
root[u] = merge(root[u], root[v], full);
}
sg[u] = mex(root[u], full);
}
void arc(int f, int t) {
e[++tot] = (edge){t, head[f]}, head[f] = tot;
e[++tot] = (edge){f, head[t]}, head[t] = tot;
}
int main() {
for (scanf("%d", &T); T--; ) {
scanf("%d%d", &n, &m);
for (int i = 1, x, y; i <= m; ++i) scanf("%d%d", &x, &y), arc(x, y);
int ans = 0;
for (int i = 1; i <= n; ++i) if (!vis[i]) dfs(i, 0), ans ^= sg[i];
puts(ans ? "Alice" : "Bob");
for (int i = 1; i <= n; ++i) vis[i] = (root[i] = head[i] = 0);
for (int i = 1; i <= ntot; ++i) flag[i] = next[i][0] = next[i][1] = 0;
tot = ntot = 0;
}
return 0;
}
最近的文章

「BZOJ 1815」「SHOI2006」color 有色图

Description Input输入三个整数N,M,P 1&lt; = N &lt;= 53 1&lt; = M &lt; = 1000 N&lt; P &lt; = 10^ 9 Output即总数模P后的余数 Sample Input13 2 97 Sample Output14 Solutio…

BZOJ, Polya 定理 继续阅读
更早的文章

「BZOJ 3672」「UOJ 7」「NOI2014」购票

Description今年夏天,NOI在SZ市迎来了她30周岁的生日。来自全国 n 个城市的OIer们都会从各地出发,到SZ市参加这次盛会。 全国的城市构成了一棵以SZ市为根的有根树,每个城市与它的父亲用道路连接。为了方便起见,我们将全国的 n 个城市用 1 到 n 的整数编号。其中SZ市的编号为 …

BZOJ, 动态规划, 斜率优化, 点分治 继续阅读