POJ.1704GeorgiaandBob(博弈)xiaodangao

题目链接：Georgia and Bob
思路：之前是想的是必败态是有偶数个相邻的棋子，因为后手可以通过模仿先手的行为达到平衡，然后就能推出来两个相邻奇数堆是先手必胜，因为先手可以通过移动第二个奇数堆造成必败态。但是后来推不下去了。。。正解应该是将相邻的两个棋子视为一堆石子，那么为什么不将一个石子和他之前的石子视为一堆，从而有n堆呢？因为如果看成n堆，那么一堆向左移动时，会影响两堆的状态，这种状态是无法进行平衡操作的，而如果将相邻的棋子视为一堆的话，每一次移动只会影响一堆的状态，这样即使一个堆为0的石子被移动成9，那么后手可以直接再将其变成0，继而又轮到先手，这样不会影响到总体的状态，所以还是可以看成n/2堆石子。
$Code:$


#include<set>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define bep(i,a,b) for(int i=a;i>=b;--i)
#define lowbit(x) (x&(-x))
#define ch() getchar()
#define pc(x) putchar(x)
using namespace std;

template<typename T>void read(T&x){
static char c;static int f;
for(c=ch(),f=1;c<'0'||c>'9';c=ch())if(c=='-')f=-f;
for(x=0;c>='0'&&c<='9';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>void write(T x){
static char q[65];int cnt=0;
if(x<0)pc('-'),x=-x;
q[++cnt]=x%10,x/=10;
while(x)
    q[++cnt]=x%10,x/=10;
while(cnt)pc(q[cnt--]+'0');
}

const int N = 1e3+10;

int t,n;
int arr[N],p[N];
void solve(){
    read(t);
    while(t--){
        read(n);
        rep(i,1,n){
            read(p[i]);
        }
        //sort(p+1,p+1+n);
        if(n%2)p[n+1] = 0,n++;
        int now = 0;
        sort(p+1,p+1+n);
        int ans = p[2]-p[1] - 1;
        rep(i,4,n){
            ans ^= p[i] - p[i-1] - 1;
            i++;
        }
        if(!ans){
            printf("Bob ");
        }
        else printf("Georgia ");
        puts("will win");
    }
}

signed main(){solve(); return 0; }

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。