Week2训练赛（博弈论）

Sol： 先考虑特殊情况。当一棵树只有一个点时，先手必败。当一棵树成一条链时，先手必胜。当树有多条链时，就转化成普通Nim游戏，判断各子树大小异或值。对于一颗普通的树上的点x，我们进行分类讨论。

证明：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函数的值并不止代表自己本身，而是代表以当前节点为根的树的状态，并向上传递状态。

Sol： 考虑贪心。败者向胜者连边，求树的高度的最小值。树的高度相当于是每个人需要赢得最终胜利所需场数的max。我们可以把这个问题理解成子树合并。子树是通过已知胜负情况建立的。若子树高度高的先合并，那么到达根节点的路径更长。所以我们需要按子树高度升序排序，这样才能让最大场数最小

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必胜。

Sol： 根据普通Nim游戏，每堆石子异或值为0，后手必胜。所以我们可以先预处理第3堆到第n堆的异或值为res。我们要通过移动使得a[1]^a[2]=res，而a[1]+a[2]又是不变的。初始化A=B=0，我们可以从左到右遍历res的二进制的每一位，若res的第i位为1，若A+$2^{i-1}<a[1]$则更新A，反之更新B，这样可以使得A最大，移动到第二堆的石子数最小。但若res的第i位为0，我们无法确定，A和B的第i位。又因为A^B=A+B-2*(A&B)，通过A&B我们可以确定A和B的第i位，所以问题解决了。可以将A和B的初值直接赋成A&B，剩下只需要考虑res第i位为1的情况了。无解需要判断A的大小、B的大小以及移动后第一堆和第二堆的总数是否改变、A^B是否等于res