UVaLuoguVjudge分析SG 函数好题。我们把一个石头当做一个游戏,那么终态就是在一个没有出边的点上。考虑如何计算 SG 函数。注意到有些点可能会重复选,而选 $2$ 次对 SG 函数不会有影响( $a\oplus a=0$ ),于是只需要枚举 $2^{deg}$ 种状态,算出 SG 函数然后取 $\operatorname{mex}$ 即可。注意这里选的点数和选的次数的奇偶性要相同...
UVaLuoguVjudge分析设 $SG(i,j)$ 表示一堆是 $i$ ,另一堆是 $j$ 的 SG 函数值。打个表看下有没有规律:0 1 0 2 1 3 0 4 2 5 1 6 3 7 0 8 4 9 2 10 5 11 1 12 6 13 3 14 7 15 0 16 8 17 4 18 9 19 2 20 10 21 5 22 11 23 1 24 12 25 6 26 13 27...
LuoguBZOJ分析很神仙的一道博弈论题。首先发现必败态一定是所有的豆子都装在最后一个瓶子里。然后,每次的转移一定是拿出一颗豆子,放入两颗豆子。于是我们可以把每颗豆子看做一个单独的游戏了。继续观察发现,如果有两个在同一个瓶子里的豆子,那么可以直接忽略掉这两个,因为后手可以模仿先手。于是所有位置的豆子等价于$\text{这个位置上的豆子数}\%2$。现在问题成功简化为,有一颗在$i$位置的豆...
LuoguBZOJ分析0首先发现这是个$\mathrm{Multi-SG}$游戏,然后发现可以用 $SG$ 函数来做。显然的,对于任意的$x<F$,$SG(x)=0$。1先考虑怎么暴力求 $SG(x)$ 。大力枚举分成的堆数。如果将 $x$ 分成了$i$ 堆,那么这 $i$ 堆中有 $x\% i$ 堆$\left\lceil\frac{x}{i}\right\rceil$,有 $i-x...
LuoguBZOJ分析打表后发现 $SG(i)=i-1\text{的二进制表示}$。于是每一对数 $(i,j)$ 的 $SG$ 值就是 $\mathrm{mex}(i-1,j-1)$ 。然后每一对数的 $SG$ 值都异或起来就行了。代码//It is made by M_sea #include <algorithm> #include <iostream> #inc...