POJ1704 Georgia and Bob(尼姆博弈)

题目链接

题意:x轴(从1开始)上有n个点,每个人可以将某个点向左移动,不能超过或覆盖左边的点。不能移动的人就输了。给定点的位置输出胜者。

如果n是奇数,在0的位置填一个点构成偶数。把这些点按照顺序两两分成一组,每组间的距离可以看成尼姆博弈中的一堆石子的个数,移动后一个棋子相当于从石头堆中取出若干个石头,移动前一个棋子可以通过移动后一个棋子恢复到原来的状态,接下来就是个裸的尼姆博弈的题了。

#include<cstring>
#include<cstdio>
#include<cstring>
#include<cmath>
#include <vector>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
int a[10002];
int main(){
    //freopen("a.txt", "r", stdin);
    int t, n;
    cin >> t;
    while(t--){
        cin >> n;
        for(int i = 0; i < n; i++)
            cin >> a[i];
        if(n&1) a[n++] = 0;
        sort(a, a+n);
        int ans = 0;
        for(int i = 0; i < n-1; i+=2){
            ans ^= (a[i+1]-a[i]-1);
        }
        if(ans) cout<<"Georgia will win"<<endl;
        else cout << "Bob will win" << endl;
    }
    return 0;
}
Zhao Li /
Published under (CC) BY-NC-SA in categories 算法  tagged with 博弈  尼姆博弈