POJ 1704

  1. 云栖社区>
  2. 博客>
  3. 正文

POJ 1704

prime7 2013-02-26 11:24:00 浏览626
展开阅读全文

这题好像nim博弈的变形 主要在于找到变成奇异局势的方式,那么可以想到最近的两个棋子移动到相邻 如果n为奇数那么把0点也看作是一个棋子 如果变完后那么后手只需要模仿先手就可以赢了 所以之前是nim博弈

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int main()
{
    int t,n,a[1010];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=0; i<n; i++)
            scanf("%d",&a[i]);
        if(n&1)
            a[n++]=0;
        sort(a,a+n);
        int ans=0;
        for(int i=n-1; i>0; i-=2)
            ans^=a[i]-a[i-1]-1;
        if(ans)
            puts("Georgia will win");
        else
            puts("Bob will win");

    }
    return 0;
}


网友评论

登录后评论
0/500
评论
prime7
+ 关注