TopCoder SRM 561 CirclesGame 题解
作者：钟知闲
关键字：数学 博弈论
题目简述
Alice 和 Bob 在玩一个游戏。平面上有 $n$ 个圆，第 $i$（$0\le i<n$）个圆的圆心为 $(x[i],y[i])$，半径为 $r[i]$，任意两圆的边界无公共点。两人轮流操作，Alice 先手，每个人操作时需要：
选择一个圆，要求不存在红点在圆内部（不包含边界）；
在该圆的内部（不包含边界）画一个红点。
不能操作者输。给定 $n$ 和长度为 $n$ 的数组 $x$，$y$，$r$，问双方都采取最优策略时谁能赢。
$1\le n\le 50$，$-10,000\le x[i]\le 10,000$，$-10,000\le y[i]\le 10,000$，$1\le r[i]\le 10,000$。
题解
由于这些圆只有内含和外离关系，不难发现，这些圆构成了一个树形结构。我们可以这样进行图论建模：对于每个圆 $i$（$0\le i<n$）建立一个点 $v_i$，定义 $v_i$ 的父节点为 $v_j$ 当且仅当圆 $j$ 是包含圆 $i$ 的最小的圆（如果没有圆包含圆 $i$，则 $v_i$ 为根节点），得到一个有根树森林 $T$。
以下证明一些性质：
性质1 在 $T$ 中，若 $v_j$ 是 $v_i$ 的祖先，则圆 $j$ 包含圆 $i$。
证明 记 $f(v)$ 为 $v$ 在 $T$ 中的父节点，由于 $v$ 对应的圆被 $f(v)$ 对应的圆包含，$f(v)$ 对应的圆被 $f(f(v))$ 对应的圆包含……所以 $v$ 对应的圆被所有 $v$ 的祖先对应的圆包含，从而圆 $j$ 包含圆 $i$。
性质2 对于平面上任意点 $P$，若 $P$ 被至少一个圆包含，则包含 $P$ 的圆的集合对应于 $T$ 中某个点到根的路径上所有点。
证明 设圆 $c$ 为包含点 $P$ 的最小的圆，考虑 $T$ 中四类顶点：
1、$v_i$ 是 $v_c$ 的祖先：由性质1，圆 $i$ 包含圆 $c$，而 $P$ 被圆 $c$ 包含，所以圆 $i$ 包含 $P$。
2、$v_c$ 是 $v_i$ 的祖先：由性质1，圆 $c$ 包含圆 $i$，于是圆 $i$ 比圆 $c$ 大，而圆 $c$ 是包含 $P$ 的最小的圆，所以圆 $i$ 不包含 $P$。
3、$v_i$ 和 $v_c$ 连通但无祖先关系：取 $v_i$ 和 $v_c$ 的最近公共祖先 $v_a$，则 $v_a\ne v_i$，$v_a\ne v_c$，记 $v_a$ 到 $v_i$ 的路径上离 $v_a$ 最近的为 $u_i$，$v_a$ 到 $v_c$ 的路径上离 $v_a$ 最近的为 $u_c$，则 $u_i$ 和 $u_c$ 对应的圆外离。
这是因为，假如 $u_i$ 对应的圆包含了 $u_c$ 对应的圆，由于 $u_i$ 对应的圆比 $a$ 小，所以 $a$ 不可能是包含 $u_c$ 对应的圆的最小的圆，矛盾。反之亦然。
而圆 $i$ 和 $c$ 分别包含于 $u_i$ 和 $u_c$ 对应的圆，从而圆 $i$ 和圆 $c$ 外离，圆 $i$ 不包含 $P$。
4、$v_i$ 和 $v_c$ 不连通：设 $v_i$ 和 $v_c$ 所在树的根分别为 $r_i$ 和 $r_c$，则 $r_i\ne r_c$，若 $r_i$ 和 $r_c$ 对应的圆有包含关系，则至少有一个不是根（因为有父节点），从而 $r_i$ 和 $r_c$ 对应的圆外离，圆 $i$ 和圆 $c$ 外离，圆 $i$ 不包含 $P$。
于是该性质得证。
我们记 $S$ 为不包含任何红点的圆在 $T$ 中对应的点集，则初始时 $S$ 为全集，当 $S=\varnothing$ 时输。那么有以下性质：
性质3 一个人的一次操作等效于选择一个 $v\in S$，然后将 $T$ 中 $v$ 及其到根的路径上所有属于 $S$ 的点从 $S$ 中删去。
证明 首先证明对于任意一个合法的操作，都存在一个 $v\in S$ 使得该操作将 $T$ 中 $v$ 及其到根的路径上所有属于 $S$ 的点从 $S$ 中删去。
设选择的圆为 $c$，画的红点为 $P$，包含 $P$ 的最小的圆为 $c'$，则画 $P$ 之前，由于 $c$ 和 $c'$ 有公共点，且 $c$ 不比 $c'$ 小（由假设），所以 $c=c'$ 或 $c$ 包含 $c'$。而加入 $P$ 前 $c$ 中无红点，故 $c'$ 中无红点，即 $v_{c'}\in S$。
由性质2，这相当于把 $v_{c'}$ 及其到根的路径上所有不属于 $S$ 的点从 $S$ 中删去。
接着证明对任意 $v\in S$，都存在一种合法的操作将 $v$ 及其到根的路径上所有属于 $S$ 的点从 $S$ 中删去。
找出 $v$ 对应的圆 $c$，然后任取一个严格位于 $c$ 内但不严格位于包含在 $c$ 内的任何一个圆内部的点 $P$（因为任意两圆无公共点，所以这样的点必然存在），在平面上画红点 $P$，这样 $c$ 是包含 $P$ 的最小的圆，该操作等效于将 $v$ 及其到根的路径上所有属于 $S$ 的点从 $S$ 中删去。
这样就证明完毕了。
现在游戏转化为：给一个有根树森林 $T$，初始时令 $S$ 为 $T$ 的点集，玩家轮流选择一个 $v\in S$ 并将 $v$ 到根的路径上所有不属于 $S$ 的点从 $S$ 中删去，$S=\varnothing$ 时输。
注意到有根树森林中，每个连通块是独立的，即每个连通块是该游戏的一个子游戏，这类问题可以用 SG 定理 解决。形式化地，对于一个游戏局面 $T$，定义
这里 $T\rightarrow T'$ 表示 $T'$ 是 $T$ 的一个后继状态，$\mathrm{mex}\ A$ 表示不属于集合 $A$ 的最小自然数。显然，如果 $T$ 是先手必胜状态，那么 $\mathrm{SG}(T)\ne 0$，如果 $T$ 是先手必败状态，那么 $\mathrm{SG}(T)=0$。
SG 定理：如果 $T$ 由 $k$ 个子游戏 $T_1,T_2,...,T_k$ 组成（轮到一方操作时，该方需选择一个 $i$，然后在 $T_i$ 中进行一步合法操作，所有 $T_i$ 都不能操作时才算输），那么有 \begin{equation} \mathrm{SG}(T)=\mathrm{SG}(T_1)\oplus\mathrm{SG}(T_2)\oplus...\oplus\mathrm{SG}(T_k) \label{SG} \end{equation}
其中 $\oplus$ 表示二进制按位异或运算。要判断当前是先手必胜还是必败，只需计算 $\mathrm{SG}(T)$，根据此定理，只需计算每个连通块 $T_i$ 的 $\mathrm{SG}(T_i)$ 即可。
现在假设 $T$ 是连通的。考虑到本题数据范围不大，可以使用暴力法计算 $\mathrm{SG}(T)$，即枚举所有合法的操作，然后递归算出该操作转移到的局面 $T'$ 的 $\mathrm{SG}(T')$。假如选择了点 $v$，然后把 $v$ 到 $T$ 的根的路径上所有点删去，那么删去后 $T$ 被分成了多个连通块，而每个连通块都是 $T$ 中以某个节点为根的子树。
注意到这一点以后，我们就可以记 $g(v)$ 表示 $T$ 中以 $v$ 为根的子树 $T_v$（包含 $v$ 本身） 的 $\mathrm{SG}$ 值（也就是假设局面只剩下 $T_v$ 时，局面的 $\mathrm{SG}$ 值）。计算 $g(v)$ 时，枚举下一步操作选择点 $u$ 将其到根的路径 $L$ 删除，记不在 $L$ 上且父节点在 $L$ 上的点的集合为 ${u_1,u_2,...,u_l}$，那么 $T$ 被分成了 $l$ 个连通块，第 $i$ 个连通块为以 $u_i$ 为根的子树，该子树内每个点到 $T$ 的根的路径去掉 $L$ 上的点之后就是该点到 $u_i$ 的路径，于是每个子树 $u_1,u_2,...,u_l$ 是独立的，从而转移到的状态 $\mathrm{SG}$ 值为 \begin{equation} g(u_1)\oplus g(u_2)\oplus...\oplus g(u_l) \label{SGval} \end{equation}
因此可以得到
其中 $u\in V_v$ 表示 $u$ 在以 $v$ 为根的子树中，${u_1,u_2,...,u_l}$ 为 $u$ 到 $v$ 路径以外与该路径相邻的点集。
最后，把每个连通块 $T_i$ 的根的 $g$ 值（也就是 $\mathrm{SG}(T_i)$）求出来之后，就能由 \eqref{SG} 式得到该局面 $T$ 的 $\mathrm{SG}(T)$，如果 $\mathrm{SG}(T)\ne 0$，则获胜方为 Alice，否则，获胜方为 Bob。
时间复杂度：
1、对于给定的圆构造森林 $T$ 时，暴力对每个圆 $i$ 枚举包含圆 $i$ 的最小的圆 $j$，将 $v_j$ 作为 $v_i$ 的父节点，复杂度为 $O(n^2)$；
2、计算 $g(v)$ 时可以用 DFS 枚举子树中的点 $u$，在 DFS 的过程中维护栈中的点连出栈外的点的 $g$ 值，这样就能在 $O(n)$ 时间内对每个 $u$ 求出 \eqref{SGval} 的值，进而得到 $g(v)$ 的值；对每个 $v$ 都要计算 $g(v)$，因此总复杂度为 $O(n^2)$。
以上两步的总复杂度为 $O(n^2)$。伪代码如下（为了方便，用整数 $0,1,...,n-1$ 代替 $T$ 中的节点 $v0,v_1,...,v{n-1}$）：
// 构造森林部分
构造森林 T，f[i] 表示 i 的父节点（根节点 f[i]=-1），初始时所有 f[i]=-1
for i = 0 to n - 1:
for j = 0 to n - 1:
if 圆j严格包含圆i 且 r[j]<r[f[i]]: // 假设 r[-1] 为正无穷大
令 f[i] = j
用邻接表存森林 T，方便查询子节点
// 计算SG值部分
定义集合 S
dfs1(i): // 计算以 i 为根的子树中所有点的 g 值
枚举 i 的子节点 j:
dfs1(j)
令集合 S 为空
dfs2(i, 0)
g[i] = 不属于 S 的最小自然数
dfs2(i, val): // 将能转移到的 SG 值加入 S，val 为与 L 相邻子树的 SG 值异或和
枚举 i 的子节点 j:
更新 val 为 val xor g[j]
S 中加入 val
枚举 i 的子节点 j:
dfs2(j, val xor g[j]) // 相当于加入了除 j 外所有子节点的 g 值
令 val = 0
枚举森林 T 的每个树的根节点 i:
dfs1(i)
更新 val 为 val xor g[i]
if val 不等于 0: 返回 Alice
else: 返回 Bob