题目

题目链接

题解

博弈，尼姆博弈。

尼姆博弈

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

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

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

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

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

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

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

附
情形一模板题
情形二模板题
代码在本文末尾

本题讲解

先将其转化为尼姆博弈。

将每两个相邻的和尚进行匹配，它们之间的台阶数就相当于尼姆博弈中石子堆中石子的数量。

为什么我们可以忽略两对之间的台阶数量呢？
因为对于每一对中的靠近终点的人来说，如果本次操作法师控制他往终点方向走若干步，那么另一个法师在下一次操作中就可以控制这一对中的另一个人也向终点走相同的步数，相当于石子堆中的石子个数没变。同理对于左侧的人进行向终点前进的操作，那么右侧的也可以进行相同的操作实现石子堆中的石子数目不变。

配对我们就要考虑奇偶，假如输入的个数为奇数，很显然最后一个为终点根本不配：

假如输入的个数为奇数，很显然最后一个石子堆的石子个数还是他们之间的台阶数差：

其实，看看代码，理解代码之后就可以理解为什么不用分奇偶了。

我们首先判断当前当前的局势是否为“必败点”，若为“必败点”则直接输出-1；
否则我们就要找到一个可以由当前局势转移过去的必败局势（必败点），这样下一个法师操作的时候才会输，我才会赢（没错，我就是先手法师）。找到的这个必败点还要满足被操作的和尚的初始位置尽可能地靠左（台阶上尽可能靠下）。

代码实现上，我们从靠左的和尚开始遍历，判断当前和尚是否存在一种移动方式，使得局势变为必败点。先遍历到的满足必败点的和尚肯定就是我们要输出的答案。

代码注释很详细。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 110;

int a[N]; // 保存每个人初始位置 
int dif[N]; // dif[i]表示第i个人与第i+1个人之间的台阶个数 
int n, x;

bool check() { // 判断是否处于比必败点 
	int res = 0;
	for(int i = 1;i < n;i += 2) res ^= dif[i];  
	return res == 0; // 异或和等于0说明处于必败点 
}

int main()
{
	while(cin>>a[++n]) ;n--; // 输入a 

	for(int i = 1;i < n;i ++) dif[i] = a[i+1] - a[i] - 1; // 求dif 
	
	if(check()) puts("-1"); // 初始状态下就已经是必败点了，那就输出-1 
	else { // 初始状态为必胜点，那我就去找个一个操作使得对手进入必败点，还得保证尽可能对靠左的和尚进行操作 
		for(int i = 1;i < n;i ++) { // 从最左侧的和尚开始遍历 
			for(int j = 1;j <= dif[i];j ++) { // 遍历这个和尚和他的后一个和尚的台阶，之所以遍历这个，我们是想找到一个状态，正是上面所说的状态，即处于必败点的状态 
				dif[i] -= j; // 我让这个和尚向上走j个台阶，那么这个和尚和他的上一个和尚的距离就要-j 
				dif[i-1] += j; // 那么这个和尚和他的下一个和尚的距离就要+j
				if(check()) {printf("%d %d", a[i], a[i]+j); return 0;} // 判断一下这个状态是不是我们要找的状态，即必败点 
				dif[i] += j; // 若不是必败点，那么我就将这个和尚恢复到原来的位置，那么这个和尚和他的上一个和尚的距离就要+j 
				dif[i-1] -= j; // 那么这个和尚和他的下一个和尚的距离就要-j
			}
		}
	}
	return 0;
}

另附

情形一代码

#include<iostream>
using namespace std;

int n, x, sum;

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

	return 0;
}

情形二代码

#include<bits/stdc++.h>
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 <= n;i ++) cin>>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;
}