尼姆博弈（标题必须凑够五个字）

尼姆博弈讲解

标准的尼姆博弈的情形： 两个人按最优策略交替从n堆石子中的一堆里面取若干石子（不可以为0）,直到石子全部被取完，无法继续取石子的人败。

在将尼姆博弈前得先学点知识： 必败点： 在当前局势下，轮到我进行操作了，但是我无论怎么（合法）操作，最后我都会输，则称这个局势为必败点； 必胜点： 在当前局势下，轮到我进行操作了，我发现存在一种（合法）操作，可以让我必赢。 以上都是在之后的操作为最优策略的前提下。

如果我们知道当前局势是必败点还是必胜点，那么就可以轻易知道我先手到底会不会赢了。 如何确定当前局势是否为必败点？有个结论：每堆石子个数的异或和为0，则此局势为必败点。 那么很显然，非胜即败，异或和不为0，则局势为必胜点。 至于这个结论的证明可以不用知道。

尼姆博弈其实存在两种标准情形，背景相同，胜负条件不同：

1. 两个人按最优策略交替从n堆石子中的一堆里面取若干石子（不可以为0）,直到石子全部被取完，无法继续取石子的人败。
2. 两个人按最优策略交替从n堆石子中的一堆里面取若干石子（不可以为0）,直到石子全部被取完，无法继续取石子的人胜。或者说将石子取完的人败。

在上述两种情形中，异或和为0都对应必败点，即在第一种情形中异或和为0表示此局势下，先手为负，先手的人将最后无法取石子；在第二种情形种异或和为0表示此局势下，先手为负，先手的人会把石子取完。 又可以总结为“必败点”与题目所述的失败条件无关。

注意： 在第二种情形下，需要特殊判断石子堆中的石子数目是否全为1，在全为1的情况下，我们需要判断，石子堆的堆数的奇偶，若奇则先手必败，若偶则先手必胜。 而第一种情况就不存在这样的特殊判断，这是因为当石子堆中的石子数目全为1时，堆数为奇偶的结果与疑惑的结果一致，可以进行同一输出，无需特判。

例题

情形一模板题 情形二模板题 蓝桥杯 高僧斗法

代码 情形一代码

#include
using namespace std;

int n, x, sum;

int main()
{
	while(cin>>n) {
		sum = 0;
		for(int i = 1;i >x, sum ^= x;
		if(sum == 0) puts("No");
		else puts("Yes");
	}

	return 0;
}

情形二代码

#include
using namespace std;

int T, sum, n, x, flag;

int main()
{
	cin>>T;
	while(T--) {
		cin>>n; 
		sum = flag = 0;
		for(int i = 1;i >x, sum ^= x, flag = (x!=1?1:flag);
		if(flag) {
			if(sum == 0) puts("Brother");
			else puts("John");
		} else {
			if(n&1) puts("Brother");
			else puts("John");
		}
	} 

	return 0;
}

高僧斗法博客

[蓝桥杯][2013年第四届真题]高僧斗法

学习博弈的优质博客

这是个博客集