type
status
date
slug
summary
tags
category
icon
password
Email
文章首发于我的个人博客：欢迎大佬们来逛逛
Nim游戏
题目要求：给你 n 堆石子，两个人轮流取石子，每次选择一堆，可以取出这一堆的任何数量的石子，直到某个人无法再取出任何石子，则另一个人就赢了。
例如：n=2 ：1 1
第一个人取第一堆，第二个人取第二堆，则第一个人必输。
n=2： 1 0
第一个人取第一堆，则第一个人必赢。
可以看出，如果出现：
- ：则是一个必胜态
- ：则是一个必输态
为什么？
考虑下面的案例：
n=2： 2 2
他们的异或值为 0，可以证明对于甲来说这一定是一个必输态
n=2： 2 3
他们的异或值不为0，则可以证明这一定是一个必胜态。
其实对于这个必胜态的过程，我们发现其实就是把必输态转移到了乙的身上.
则通过上面的描述，一个必胜态一定可以转换为必输态。
定理如下：
- 必胜态的后继状态至少存在一个必输态。
如果是必胜态，则一定存在 ，则假设 的最高位的二进制1 是第 位，则在原始序列 中的第 位一定存在奇数个1。用 去替换 则会存在以下的式子（这里假设是）： ，则可以证明，一个必胜态一定可以转换得到一个必输态。
- 必输态的后继状态全部都是必胜态
如果是必输态，则上面的等式 ，则每个 的第k位一定都是偶数个，因此如果去掉一个1一定全部都是奇数，则存在 ，则全部都是必胜态。
则我们根据上面的结论可以得到 代码：
方案
这道题目与上道题目基本一致，唯一的区别是这道题目还需要求出在先取必胜的前提下，第一次应该如何选？
- 必胜态的后继状态至少存在一个必输态。
因此如果甲先手赢，则乙一定处于一个必输态的状态。
因此可以考虑构造一个乙是必输态的情况，则就是甲先手赢的选择的情况。
由必胜态转换为必输态的，根据第一条定理：
则我们就是需要找出这样的一个状态： ，
则只需要减少一个数字，使得 即可。
同时找到之后，需要修改 位置的值。
台阶型
给你n堆石子，并且把他们放在不同的台阶上，每次可以将第 个台阶上的石子移动一些到 阶上去，直到最后台阶为0时，无法再移动，问能否先手必胜？
台阶型和上面的普通型其实是一个道理。
普通型：
- ： 先手必胜
台阶型：
- ：先手必胜
为什么？
始终记住上面的两条定理：
- 必胜态一定可以转换为一个必输态
- 必输态不可能转换为另一个必输态，之能转换为必胜态。
因此我们就可以创造先手的必胜态，则对于后手的来说一定是必输态。
如果创造呢？同样是要缩小一个数字，即找到 ，则一定可以替换 的位置，则最后就可以把一个必胜态转变为必输态。
即转换为：，则对于乙来说是必输的。
- 作者:Yuleo
- 链接:https://www.helloylh.com/article/d867a4b1-dd4e-4ae7-ac96-bc96d3e6e62c
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。