【简要题解】
将原题转化为阶梯博弈,将1格子前面空白格子数记为 $b_n$,将1,2棋子间空白格子数记为$b_{n-1}$,将2,3棋子间空白格子数记为$b_{n-2}$,……,将n-1,n棋子间空白格子数记为$b_1$。$b_{1\sim n}$ 分别代表阶梯博弈中第$1\sim n$阶梯上摆放的石子数,则根据阶梯博弈结论,有“$b_1 xor b_3 xor …\neq0$ 时Georgia赢”“反之Bob赢”。
【分析思路】
这部分主要讲阶梯博弈。
阶梯博弈是指从低到高n级阶梯,第i级阶梯上摆放有$a_i$个石子,每次操作可将第k级阶梯上的石子移一些到第k-1级阶梯上,特别地,从第一级阶梯移向第0级阶梯就直接掉下去。某一时刻一个人没有石子可以移了,他就输了,问先手是否必胜。
阶梯博弈可转化为nim博弈,结论是对奇数级阶梯上的石子进行nim博弈判胜负,方法为:每次我方将奇数级阶梯上的石子往下移(到偶数级阶梯上),从奇数级移到偶数级可以看成nim博弈中的拿走石子。如果对手将偶数级阶梯上的石子移到奇数级阶梯上,我们就赶紧把他移过去的那些石子移到再下一级阶梯上(偶数级),从而保证奇数级阶梯状态不受破坏。于是就只用考虑奇数级阶梯的nim游戏。
为什么不可以是偶数级阶梯上的nim游戏呢?因为当对手从第一级台阶移到第0级台阶(深渊)时,我们不再能把他移下去的那些石子从偶数级阶梯的石子状态中剥离走,状态因此被破坏。但如果是奇数级阶梯上的nim游戏,我们从第1级阶梯上丢下深渊的石子并不会破坏奇数级阶梯的状态。
#include <bits/stdc++.h>
using namespace std;
int a[1005],b[1005];
int main()
{
int T;
cin>>T;
while(T--){
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
for(int i=n;i>=1;i--) b[n-i+1]=a[i]-a[i-1]-1;
int res=0;
for(int i=1;i<=n;i+=2) res^=b[i];
if(res) puts("Georgia will win");
else puts("Bob will win");
}
}
为什么把a[n]-a[n-1]记为第一级台阶的石子,而不是a[i]-a[0]?