Java教程

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 不会输的游戏的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!