Solution Of 不会输的游戏

本文主要是介绍Solution Of 不会输的游戏，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

注：\(\oplus\) 为异或符号 ，\(\land\) 表示逻辑与，\(\lor\) 表示逻辑或

这是一道魔改题，为luogu P7841 100%不公平的游戏 的弱化版

请先了解 \(SG\) 函数的相关内容，否则本文可能不太友好

对 \(SG\) 函数不了解的可以参考博弈论

显然每棵树是一个 \(SG\) 游戏，而整个森林为这些 \(SG\) 游戏的和

由 \(SG\) 定理，整个游戏的 \(SG\) 值为所有 \(SG\) 子游戏的 \(SG\) 值的异或和

即\(SG(X)=SG(x_1) \oplus SG(x_2) \oplus ...\oplus SG(x_k)\)

当且仅当 \(SG(X)=0\) 时有先手必败

考虑如何计算一颗树的 \(SG\) 值（接下来只对单棵树分析）

设 \(SG(u,k)\) 表示状态 \((u,k)\) 的 \(SG\) 值

状态 \((u,k)\) 表示：

「目前选择的边的端点中深度最大的为\(u\) ； 从根节点到节点 \(u\) 的路径上还有 \(k\) 条边未被选择」

设 \(T_u\) 表示节点 \(u\) 的子树（不包括 \(u\) 自身）

则状态 \((u,k)\) 可以到达 \(\Big(v_{(v \in T_u)}\ ,k+depth_v-depth_u-1\Big)\)

若 \(k > 0\) 则状态\((u,k)\) 还可以到达 \((u,k-1)\)

记状态 \(X\) 可到达的状态（后继状态）集合为 \(S_X\)，则 \(SG(X)=mex\{SG(x)|x \in S_X\}\) （此为定义式，其中 \(mex\) 是对自然数集的运算，表示该自然数集中未出现过的最小自然数）

以下证明一些命题（记 \(\text{leaf}\) 为叶节点集合）

//

命题一：\(SG(u,k)=SG(u,k\ \text{mod}\ 2)\) ，即 \(SG(u,?)\) 存在长度为 \(2\) 的循环节

对于边界情况 \(u \in \text{leaf}\) ,显然有 \(SG(u,0)=0\) 又 \(SG(u,1)=mex\{SG(u,0)\}=1\ ,\ SG(u,2)=mex\{SG(u,1)\}=0\ ,\ ...\ ,\ SG(u,k)=k\ \text{mod}\ 2\)

于是当 \(u \in \text{leaf}\)，命题成立

接下来考虑归纳法，试证：若命题对所有 \(v \in T_u\) 成立，则命题对 \(u\) 成立

假设命题对所有 \(v \in T_u\) 成立

则对于所有 \((u,k)\)，其后继状态为（暂不考虑\((u,k-1)\)） \(\big\{(v,k+depth_v-depth_u-1)|v \in T_u\big\}\) ，对确定的 \(u,v\) 其 \(depth_v-depth_u-1\) 固定，那么 \(depth_v-depth_u-1\) 的奇偶性也固定

则对于奇偶性相同的 \(k_1 , k_2\) ，状态 \((u,k_1),(u,k_2)\) 后继状态的 \(SG\) 值： \(SG(v,k_1+depth_v-depth_u-1)=SG\Big(v\ ,(k_1+depth_v-depth_u-1)\ \text{mod}\ 2\Big)=SG\Big(v\ ,(k_2+depth_v-depth_u-1)\ \text{mod}\ 2\Big)=SG(v,k_2+depth_v-depth_u-1)\)

令 \(k\ \text{mod}\ 2=0\) 的\((u,k)\) 后继状态 \(SG\) 值集合为 \(A\)，\(k\ \text{mod}\ 2=1\) 的\((u,k)\) 后继状态 \(SG\) 值集合为 \(B\)

计算状态 \((u,?)\) 的 \(SG\) 值：

\(SG(u,0)=mex{A}=a\ ,\ SG(u,1)=mex{(B \cup \{a\})}=b\)，显然 \(b \neq a\)，那么\(SG(u,2)=mex{(A \cup \{b\})}=mex{A}=a\)，循环发生，命题一证明完毕。

//

命题二：\(SG(u,0)\oplus SG(u,1)=1\)

对于边界情况 \(u \in \text{leaf}\) ,显然有 \(SG(u,0)=0\) 又 \(SG(u,1)=mex\{SG(u,0)\}=1\ ,\ SG(u,2)=mex\{SG(u,1)\}=0\ ,\ ...\ ,\ SG(u,k)=k\ \text{mod}\ 2\)

于是当 \(u \in \text{leaf}\)，命题成立

接下来考虑归纳法，试证：若命题对所有 \(v \in T_u\) 成立，则命题对 \(u\) 成立（复读）

假设命题对所有 \(v \in T_u\) 成立

对自然数集 \(X\)，定义 \(X\oplus 1=\{x\oplus 1|x\in X\}\)

则对于自然数集 \(X=\{x|\lfloor\frac{x}{2}\rfloor < \text{(const)}\}\)，有 \(X \oplus 1=X\)

命题一已证明，那么借用命题一中的 \(SG\) 集合\(A\)和\(B\)

则 \(B=A\oplus 1\)，\(mex{A}=a\)

令自然数集 \(X=\{x|\lfloor\frac{x}{2}\rfloor < \lfloor \frac{a}{2}\rfloor\}\)

则有 \(X \oplus 1=X\ ,\ X \subseteq A\)，又由于\(B=A\oplus 1\)，所以 \(X \subseteq B\) ，即是说 \(\forall \Big(x \in N \land x \in [0,min\{a,a\oplus 1\})\Big) ,有\Big(x \in A \land x\in B \Big) \tag{@}\)

分类讨论:

\(1^{\circ}\)： \(a\ \text{mod}\ 2=0\)

则 \(a \oplus 1 = a+1\)，\(\because a \notin A\ \ \therefore (a \oplus 1) \notin (A \oplus 1)\)，即 \((a \oplus 1) \notin B\)

又 \(\because (@) \Rightarrow \forall \Big(x \in N \land x \in [0,a)\Big) ,有 x\in \big(B\cup \{a\}\big)\ \ \ 且显然\ \ \ a\in \big(B\cup \{a\}\big)\)

\(\therefore mex{\big(B\cup \{a\}\big)}=a+1=a \oplus 1\)

\(2^{\circ}\)： \(a\ \text{mod}\ 2=1\)

则 \(a \oplus 1 = a-1\)，\(\because a \notin A\ \ \therefore (a \oplus 1) \notin (A \oplus 1)\)，即 \((a \oplus 1) \notin B\)

又 \(\because (@) \Rightarrow \forall \Big(x \in N \land x \in [0,a \oplus 1)\Big) ,有 x\in \big(B\cup \{a\}\big)\)

\(\therefore mex{\big(B\cup \{a\}\big)}=a-1=a \oplus 1\)

综上，\(SG(u,0)=mex{A}=a\ ,\ SG(u,1)=mex{(B\cup \{a\})}=(a \oplus 1)\)，于是 \(SG(u,0) \oplus SG(u,1)=1\)，命题二证明完毕

//

命题三: 记 \(\lfloor\frac{SG(u,0)}{2} \rfloor =f(u)\)， 则对于 \(u\) 的所有直系子节点 \(v\) ，\(f(u)-max\{f(v)\}= 0 或 1\)

仍旧是归纳法

设 节点 \(t\) ，使 \(t\) 是 \(u\) 的直系子节点，且对于 \(u\) 的所有直系子节点 \(v\)，有 \(f(t)=max\{f(v)\}\)

延续前文的 \(A,B\) 集合，由于 \(u\) 相对于 \(v\) ，其 \(depth\) 的奇偶性发生变化

\(SG(u,0)=mex{A_u}=a_u\ ,\ SG(v,0)=mex{A_v}=a_v\ ,\ SG(v,1)=mex{(B_v\cup \{a_v\})}\) ，则有 \(\big((A_v\oplus 1)\cup \{a_v\}\big)\subseteq A_u\)，即 \((B_v\cup \{a_v\})\subseteq A_u\)

那么对于 \(u\) 的所有直系子节点 \(v\)，有 \((B_v\cup \{a_v\})\subseteq A_u \Rightarrow mex{A_u}\geq mex{(B_v\cup \{a_v\})}=SG(v,1) \Rightarrow f(u) \geq f(v)\)，因此 \(f(u) \geq f(t)\) ，也就是说 \(f(u) - f(t) \geq 0\)

接下来证明 \(f(u) - f(t) \leq 1\)，即 \(f(u) \leq f(t)+1\)

易发现边界情况成立，利用归纳法，假设对子树均成立

那么发现 \(A_v=\Big[0\ ,max\{a_v,a_v\oplus 1\}\Big]\setminus \{a_v\}\ ,\ B_v=\Big[0\ ,max\{a_v,a_v\oplus 1\}\Big]\setminus \{a_v\oplus 1\}\) （注：\(X\setminus Y=\{x|x \in X \land x \notin Y\}\)）

于是 \(\forall \lfloor \frac{x}{2} \rfloor > g(v) 有 x \notin A_v \land x \notin B_v\)

而 \(\lfloor \frac{x}{2} \rfloor > g(t) \Rightarrow \lfloor \frac{x}{2} \rfloor > g(v)\)，所以 \(\forall \lfloor \frac{x}{2} \rfloor > g(t) 有 x \notin A_v \land x \notin B_v\)，因此 \(SG(u,0) \leq 1+max\{a_t,b_t\} \Rightarrow f(u) \leq f(t)+1\)

\(f(t)\leq f(u) \leq f(t)+1 \Rightarrow f(u)-f(t)=0或1\)，命题三证明完毕

在命题三的证明过程中，可以发现 \(SG(u)\) 只与 \(f(v)=f(t)\) 的节点 \(v\) 有关，因为其他的贡献都会被这些覆盖掉

更具体的，由以上三个命题，可以写出 \(SG(u,0)\) 的计算式：

\[SG(u,0)= \begin{cases} 0 & ,T_u=\varnothing \\ SG(t,0)\oplus 1 & ,\forall v \in T_u \land f(v)=f(t),st\ SG(v,0)=SG(t,0)\\ max\{SG(t,0),SG(t,1)\}+1 & ,\exists v \in T_u \land f(v)=f(t),st\ SG(v,0) \neq SG(t,0) \end{cases} \]

回到开头，显然每棵树是一个 \(SG\) 游戏，而整个森林为这些 \(SG\) 游戏的和

那么对每棵树求出其 \(SG(root,0)\)，令 \(flag=\bigoplus{SG(root,0)}\) （所有根节点 \(SG\) 值的异或和）

则当且仅当 \(flag=0\) 时先手必败，否则先手必胜

直接做树形DP，复杂度\(O(n)\)

赛后被参赛者发现了新规律

假设\(\lfloor\frac{SG(root,0)}{2} \rfloor =U\)的树至少\(K\)个节点

那么\(\lfloor\frac{SG(u,0)}{2} \rfloor =U+1\)的树至少要有两颗不重叠的\(\lfloor\frac{SG(root,0)}{2} \rfloor =U\)的子树，于是\(\lfloor\frac{SG(u,0)}{2} \rfloor =U+1\)的树至少有\(2K+1\)个节点，这也就意味着，\(SG\)值是\(log\)级别的，那么可以直接用\(bitset\)求\(mex\)

这篇关于Solution Of 不会输的游戏的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！