Week2训练赛（博弈论）
unknown_risk · · 个人记录
A:Game on Tree
Sol： 先考虑特殊情况。当一棵树只有一个点时，先手必败。当一棵树成一条链时，先手必胜。当树有多条链时，就转化成普通Nim游戏，判断各子树大小异或值。对于一颗普通的树上的点x，我们进行分类讨论。
- 若x是叶子节点，则SG(x)=0
- 若x不是叶子结点，且只有一个子节点y，则SG(y)=SG(x)+1
- 若x有多个子节点
y_{i} ，则SG(x)^=SG(y_{i} )+1
证明：1显然成立。把SG函数看成一个状态，与该节点不可到达的最小状态有关。比如当前SG(x)=0，则x的后继节点的SG值也为0。当SG非零与SG零相连，则表示当前状态可转换为先手必败态。对于一堆石子进行nim游戏，3个石子可以取走一个变成2个石子转化为先手必胜态，也可以直接取走3个转化为先手必败态。SG大于0都是先手必胜。对于当前节点x：若只有一个子节点y，删除以y为根的子树，SG(x)=0。删除其它子树，可通过数学归纳法可得，SG(x)=mex(0,1,……,SG(y))=SG(y)+1，结论2证毕；若x有多个子节点，可转化为只有一个子节点讨论，这就是结论3。总而言之，当前节点SG函数的值并不止代表自己本身，而是代表以当前节点为根的树的状态，并向上传递状态。
B:Tournament
Sol： 考虑贪心。败者向胜者连边，求树的高度的最小值。树的高度相当于是每个人需要赢得最终胜利所需场数的max。我们可以把这个问题理解成子树合并。子树是通过已知胜负情况建立的。若子树高度高的先合并，那么到达根节点的路径更长。所以我们需要按子树高度升序排序，这样才能让最大场数最小
D:Distinct Numbers
Sol： 高妙博弈论。当a[n]-a[n-1]>1,A先手将a[n]替换成a[n-1]+1。此时轮到B，若B必输，则A必胜。若B有必胜的策略，将a[n-1]+1替换成x（x<a[n-1]），那A则有必胜策略在第一步将a[n]移动到x,因此A必胜。当a[n]-a[n-1]=1，A若先手替换a[n],替换的数与a[n-1]之差大于1,则转化为第一种问题，此时B必胜，所以A只能将a[n]替换成a[n-1]-1，因此A和B就这样交替进行操作，每一次操作，空位-1。空位数=a[n]-(n-1)。若空位数为偶数，则B必胜，反之则A必胜。
E:Unfair Nim
Sol： 根据普通Nim游戏，每堆石子异或值为0，后手必胜。所以我们可以先预处理第3堆到第n堆的异或值为res。我们要通过移动使得a[1]^a[2]=res，而a[1]+a[2]又是不变的。初始化A=B=0，我们可以从左到右遍历res的二进制的每一位，若res的第i位为1，若A+