这是一道变种的NIM博弈。
我们把两个相邻的棋子捆绑成一对。(如果有奇数个就添加一个0)
那么,如果一个人挪动一对中的左边位置,另一个人就一定可以挪动相同的距离使得两个位置的距离不变。性质1
如果我们把两个人之间的距离看作一堆石子的话,我们可以发现以下规律。
- 如果若干堆石子数都为0,当然有石子数异或和一定为0. 同时这一定是必败态。(性质1)
- 每次可以取一堆石子中的若干个石子。那么如果一开始异或和不为0的话,通过一次操作就一定能给对方一个异或和为0的状态。——给对方一个必败态,就是自身必胜。
代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1010;
int T,n,a[N];
int main() {
scanf("%d",&T);
while(T--) {
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+n+1);
int ans=0;
for(int i=n;i>0;i-=2)ans^=a[i]-a[i-1]-1;
ans?puts("Georgia will win"):puts("Bob will win");
}
return 0;
}