poj1704中阶梯博弈与nim博弈有何关联？

本文共计1630个文字，预计阅读时间需要7分钟。

漏了个阶梯博没有学，先前补充补充。

阶梯博给出的问题如下：从第0个阶梯起，每个阶梯上都有若干个石子，每次都可以从任意一个阶梯上取任意正整数个石子往下一阶放，但不能操作。

漏了个阶梯博弈没学，前来补补。。

阶梯博弈给出的问题如下：

从第0个阶梯起，每个阶梯上都有若干个石子，每次都可以从任一阶梯上取任意正整数个石子往下一个阶梯放，不能操作的人输

结论是：该状态的sg值为奇数阶梯上的石子的异或和

证明：

先证明这个模型可以转化为把奇数阶看成若干堆石子的nim博弈

如果对手从偶数阶往奇数阶放，那么我们可以从该奇数阶取相同的石子到下一阶，即将偶数阶的石子放到了下一个偶数阶，此时奇数阶的状态数不变

如果对手从奇数阶往偶数阶放，相当于把奇数阶上的石子拿掉了，此时可以根据nim博弈取相应的石子到达sg=0的状态

于是这个阶梯博弈就看成了奇数阶上的nim博弈，其sg值自然也是奇数阶上的石子数的异或和

再来看这个题。。我们需要将空隙看成石子，那么移动硬币相当于把空隙往右边放，相当于阶梯博弈中的把石子往下一个阶梯放，于是做个差分求个sg就可以了。。