学步园

题目：题目链接

题目的意思是说：两个人在一个1*N的格子内挪动棋子，刚开始在若干个位置上有若干个棋子，每一个选手可以进行的操作时选择一个棋子并把它向左方移动，当然不能越过其它的棋子，也不能超出边界。谁不能移动谁就输了。求谁会赢？

分析：

这道题目乍看木有思路，，我们把棋子按位置升序排列后，从后往前把他们两两绑定成一对。如果总个数是奇数，就把最前面一个和边界（位置为0）绑定。 在同一对棋子中，如果对手移动前一个，你总能对后一个移动相同的步数，所以一对棋子的前一个和前一对棋子的后一个之间有多少个空位置对最终的结果是没有影响的。于是我们只需要考虑同一对的两个棋子之间有多少空位。我们把每一对两颗棋子的距离(空位数)视作一堆石子，在对手移动每对两颗棋子中靠右的那一颗时，移动几位就相当于取几个石子,与取石子游戏对应上了,各堆的石子取尽,就相当再也不能移动棋子了。
我们可能还会考虑一种情况，就是某个玩家故意破坏，使得问题无法转换为取石子，例如前一个人将某对中的前者左移，而当前玩家不将这对中的另一移动，则会导致本堆石子增多了，不符合nim。但是这种情况是不会出现的。因为赢家只要按照取石子进行即可获胜，而输家无法主动脱离取石子状态。如果输家想要让某堆石子增多，那么赢家只需要让该堆减少回原状，这样输家又要面临跟上一回合同样的局面。

代码：

#include <iostream>
#include <stdio.h>
#include <algorithm>
#define  maxn 1010

using namespace std;

int main()
{
    int t,a[maxn];
    scanf("%d",&t);
    while(t--)
    {
        int n,sum=0;
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a[i]);
        }
        a[0]=0;
        sort(a+1,a+n+1);//要先排序，注意地址不要弄错。
        for(int i=n; i>0; i=i-2)
        {
            sum^=(a[i]-a[i-1]-1);
        }
        if(sum)printf("Georgia will win\n");
        else printf("Bob will win\n");
    }
    return 0;
}

努力努力...