Georgia and Bob

Georgia and Bob

给出一个严格递增的正整数数列\(\{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();
}
上一篇:服务器设置静态IP


下一篇:【Matlab语音隐写】LSB语音信号数字水印嵌入提取(带面板)【含GUI源码 1676期】