博弈论杂题

博弈论杂题

博弈论？有点玄学的东西。

做到博弈论题目的时候，我们虽然可以巧妙的利用几个小套路，但是大部分时候还是依赖选手的耐心和手玩能力。

以下仅给出题目链接和部分思路，不给出一句话题意和详细代码，请读者选择阅读。

威佐夫博弈

真是奇怪的东西。

手玩了一$\text{(wu)}$些$\text{(shu)}$组的小数据后发现后手获胜的情况很少，想必是满足一些特殊的性质。

而发现对于 $(2,1),(5,3)$ 这类的后手获胜情况，我们可以将其他的一些情况转移到这里来而使得先手获胜，那么意味着，对于出现了 $(2,1)$ 中的 $2$ 或 $1$ 而并非 $(2,1)$ 的类似情况一定是先手获胜。且对于满足 $y\leq x$ 的情况 $(x,y)$ 都满足 $x$ 在所有的后手获胜对中仅出现一次。此时重点则在于如何寻找到所有的后手获胜情况。

不会证明，所以我们选择手玩，发现 $(2,1),(5,3),(7,4),(13,8)$ 等等满足第 $i$ 对中差值为 $i$ 的为后手获胜情况。而且你会发现他们居然惊奇的满足黄金分割比率 $\frac{1+\sqrt{5} }{2}\approx 0.618$。（别问我怎么知道的，我也不会证明，所以只放了个结论在这里）

然而我们无法从任何一种博弈中都能明确的发现这样的奇妙关系，所以我们需要知道这样的套路：大量手玩，寻找特例，普遍转移，发现关系。

AT2400-[ARC072B]_Alice&Brown

考虑从两堆石头中轮流取石，每次取石要求取走某一石堆中 $2\cdot x$ 个石子，并将其中 $x$ 个石子放回另一石堆中，无法进行取石操作的人失败。

手玩一些数据后我们发现后手获胜的情况很少，必然存在某种特殊条件使得后手获胜。此时我们发现当 $(0,0),(1,0),(1,1)$ 等最终必输情况，而后手仅需保持后手状态至最终必输情况即可获胜。而大量手玩后我们发现必输情况似乎满足 $|a-b|\leq1$，一下给出证明。

当 $(a,b)$ 满足 $|a-b|\leq1$ 时，无论先手如何操作，后手都有方案使状态回归至 $|a-b|\leq1$，此时后手必胜；相应地，当 $|a-b|>1$ 时，先手有方案使得状态回归至 $|a-b|\leq1$，同时变换先后手顺序，此时先手必胜。

令此时状态为 $(n,m)$ 且 $n>m$，证明当状态满足 $n-m>1$ 如何一步转移至 $n-m\leq1$：考虑转移前状态 $(n,m)$ 满足 $n-m>1$，考虑在 $n$ 中取走 $2\cdot x$ 个石子，并放回 $x$ 个石子至 $m$ 堆中，此时转移后的状态 $(n-2\cdot x,m+x)$ 满足 $n-2\cdot x-(m+x)\leq1$ 即 $n-m-1\leq 3\cdot x$，带入 $n-m<1$ 得 $x>0$，故存在正整数 $x$ 使得状态满足一步转移。

尼姆博弈

先放个结论，你就会被震撼到了：当 $a_1\bigoplus a_2 \bigoplus \cdots \bigoplus a_n=0$，则为先手必败，否则先手必胜，其中 $\bigoplus$ 表示异或操作。

考虑到当初始状态时所有数的异或值为 $0$，而当先手无论如何怎样取走石头，都无法使得所有的数的异或值依旧为 $0$。相应地，作为后手则无论此时的所有数的异或值为多少，都有方案使得所有数的异或值重新变换回到 $0$。再考虑必胜的最终状态是当且仅当剩余两个数时，仅两个数相等时，后手每次取石仅需要与先手取石相同，则后手必胜，此时两数的异或值为 $0$。故而当初始状态所有数的异或值不是 $0$ 时，则先手可以通过操作使得变换先后手顺序而取得必胜。

这里一个特别重要的启示就是要找到一种必胜策略，而必败策略也可以由此转移。

CF1382B-Sequential_Nim

考虑两人从一些石堆中轮流取石，每次取石必须按照石堆编号顺序，且不得少于 $1$ 个。

那么考虑到当第 $1$ 堆石堆数量为 $1$ 时，我们没有其他的选择方案，等价于变换先后取石顺序。相应地，如果对于前奇数个石堆都满足数量为 $1$，则变换先后手。

当我们考虑到第 $1$ 个石堆数量大于 $1$ 时，先手可以通过取走至剩余 $1$ 个石头来保持先手状态。而当发现其后存在连续的 $n$ 石堆数量都为 $1$ 时，考虑 $n$ 为奇数时，先手依旧可以通过取走至剩余 $1$ 个石头来保持先手状态；相应地，当 $n$ 为偶数时，先手则可以通过取完这一整堆石头来保持先手状态，直到最后仅剩下 $1$ 个石堆时，直接取完来获得胜利。此时我们只需要确定直到某一石堆的数量大于 $1$ 时的先后取石顺序来判断输赢。注意特判全为 $1$ 的情况。

CF1383B-GameGame

考虑到异或操作的每一位仅对其产生影响，可以感性地理解为 “不进位加法”。

那么考虑到当某一最高位有胜负输赢，那么即使低位再多也对结果无法产生影响。

那么从高到低按位考虑，把每一个数拆分成二进制数后，当此时的最高位出现的 $1$ 的个数为偶数，那么无论怎么取数双方的结果都必然相同，此时我们考虑向低位转移。直到某一高位出现奇数个 $1$，否则最后为平局。考虑到此时的高位出现 $n$ 个 $1$，且 $n$ 为奇数。当 $4\mid (n+3)$ 时，由于先手只需要取走奇数个 $1$ 后必然取胜，而先手可以控制此类操作；当 $4\mid(n+1)$ 时，仅有当总数为偶数时，先手必胜，否则必败。

AT2307-[AGC010F]_Tree Game

奇怪的树上博弈，还挺好玩的

考虑到如何判断一个点作为起点能否是的先手有必胜策略，首先需要知道有哪些点是可以移动的。

当 $w_v\geq w_u$ 时，先手一定不会选择从 $u$ 移向 $v$，因为后手只需要再次从 $v$ 移向 $u$ 即可，而先手永远不可能通过到 $v$ 点；且当一个点如果经过则一定不会再次经过了，因为这样结局永远不会改变。

同时根据博弈规则，当对于下一步无限多的情况中，存在至少一次后手必胜，那么此刻则必然是先手必胜；相应地，先后手之间的博弈必胜不断交替变换，而使得直到起点判断是否必胜必败。

最后由于数据范围较小 $n\leq 2\times 10^3$，则可以对于每个点都进行 $\text{dfs}$ 后输出答案。

洛谷-P4643 [国家集训队]阿狸和桃子的游戏

伪博弈论？其实是一道妙妙的构造题

其实这道题除了题意描述和博弈论有所相似外，与博弈论并无关系，读者可以选择跳过，但是题目本身的确锻炼思维，也建议食用。

考虑到我们是选点，很难直接通过点集算出边权和，则此时考虑把边权转变为点权。

注意到我们需要求的是两人分数的差值。那么对于两个点都被同一人选中时，贡献的差值为 $w$，否则为 $0$。那么考虑将两个点的边权同时赋值 $\frac{w}{2}$，那么当同一个人选择了两个点时，他获得的贡献的差值为 $\frac{w}{2}+\frac{w}{2}=w$，否则他获得的差值为 $\frac{w}{2}-\frac{w}{2}=0$，符合题意要求。

故只需要把每条边的边权均分后转为点权，再对于所有的点从大到小排序，逐次选择，最后就可以输出差值作为答案。