给出一个严格递增的正整数数列\(\{a_i\}\),每一次操作可以对于其中任意一个数减去一个正整数,但仍然要保证数列的严格递增性,现在两名玩家轮流操作,不能操作的玩家判负,询问先手是否能够必胜。
解
注意到除去严格递增性后,就是Nim游戏了,所以问题主体依赖于Nim定理,于是要设法转化为Nim游戏,这里采取捆绑法,也就是阶梯博弈,从最后一个数开始,每两个作为一对,第一个如果无数捆绑,则与0捆绑。
此时,对手如果对一对数中的前一个进行操作,你必然可以对这对数的后一个数进行同样的操作,即减掉相同的数,因此相对位移不会发生改变,而对手或者你对一对数中的后一个数进行操作,即改变了两个数的相对位移,所以实际上发生改变的,也就是影响最终局面的也就是相对位移。
于是我们可以排好序,捆绑好数,算出相对位移,套用Nim定理即可。
参考代码:
#include <iostream>
#include <cstdio>
#include <algorithm>
#define il inline
#define ri register
using namespace std;
int p[1001];
il void read(int&);
int main(){
int lsy,n,i,ans;read(lsy);
while(lsy--){read(n);
for(i=1;i<=n;++i)read(p[i]);
sort(p+1,p+n+1),ans&=0;
for(i=n;i>0;i-=2)ans^=(p[i]-p[i-1]-1);
puts(ans?"Georgia will win":"Bob will win");
}
return 0;
}
il void read(int &x){
x&=0;ri char c;while(c=getchar(),c<'0'||c>'9');
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
}