LightOJ1186——Incredible Chess(nim游戏)

LightOJ1186——Incredible Chess

题意：

n*n的棋盘，每一列有一个黑棋子和一个白棋子，只能上下移动并且不能越过棋子，先手为白棋，问最后谁能够赢。

思路：

upc前几天做过的。

首先可以知道的是有效区域为每一列中两个棋子中间的区域，因为如果向最上面或是最下面走对输赢是不会产生影响的。

抽象一下游戏过程就是有n个间隔，每个人都可以走任意步，就是nim游戏嘛。

异或值为0，先手必败。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=510;
int a[maxn],b[maxn];
int main(){
	int T,Case=1;
	cin>>T;
	while(T--){
		int n;cin>>n;
		for(int i=1;i<=n;i++) cin>>a[i];
		for(int i=1;i<=n;i++) cin>>b[i];
		int res=0;
		for(int i=1;i<=n;i++)
			res^=(b[i]-a[i]-1);
		cout<<"Case "<<Case++<<":";
		if(res) printf(" white wins
");
		else puts(" black wins");
	}
	return 0;
}