Description
有一个100 * 100的棋盘，其中左下角的编号为(0, 0), 右上角编号为(99, 99)。棋盘上有N个Queen，最开始第i个Queen的位置为(Xi, Yi)。现在有两个玩家依次来操作，每一次一个玩家可以选择其中一个Queen，将它跳到(Xi – k, Yi)或(Xi, Yi - k)或(Xi – k, Yi - k), 其中k > 0。注意在游戏的过程中，一个格子里面可能出现多个Queen。如果谁先将任意一个Queen移动到(0, 0), 谁就获胜。问先手必胜还是后手必胜?
Input
注意本题是多组数据。 第一行有一个数T, 表示数据组数。 接下来有T组数据，每组数据的第一行一个正整数N表示Queen的个数。接下来N行每行两个数表示第i个Queen的初始位置Xi, Yi(0 <= Xi <= 99, 0 <= Yi <= 99)。
Output
对于每一组数据，你需要输出是先手必胜还是后手必胜。 如果是先手必胜，输出“^o^“, 如果是后手必胜，输出”T_T”。
Sample Input
2

2

3 4

3 5

3

3 2

4 2

3 1

Sample Output
^o^

T_T

数据范围

T <= 10, N <= 1000

解法：显然SG函数，但是这题奇葩一些就在于这题的胜利条件不是拿走最后一张牌了而是走到(0,0)。

然后就需要大概的转化一下了。

观察到SG函数中如果没有石子了，说明不能移动了，此时SG=0。

首先我们将所有能一步走到(0,0)的位置A集合特殊考虑，这些位置显然是先手必胜的，那么有一些位置B是只

能走到这些先手必胜的位置上的，我们就可以把它们的SG函数定为0了。

然后现在的问题成了一个棋盘，走到B集合就不能再移动了，不能移动者输。

于是就是一个很经典的NIM游戏了，注意在SG函数的推导中那些A集合中的点是不考虑的。

///BZOJ 1457

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1010;
const int maxm = 110;
int t, n, sg[maxm][maxm];
struct node{int x, y;}a[maxn];
int SG(int x, int y){
    if(x==0||y==0||x==y) return sg[x][y]=0;
    if(sg[x][y]!=-1) return sg[x][y];
    bool vis[maxn];
    memset(vis, 0, sizeof(vis));
    for(int k=1;;k++){
        if(x-k<=0&&y-k<=0) break;
        if(x-k>0&&x-k!=y) vis[SG(x-k,y)]=1;
        if(y-k>0&&y-k!=x) vis[SG(x,y-k)]=1;
        if(x-k>0&&y-k>0) vis[SG(x-k,y-k)]=1;
    }
    for(int i=0;;i++){
        if(!vis[i]){
            return sg[x][y]=sg[y][x]=i;
        }
    }
}
int main()
{
    scanf("%d", &t);
    memset(sg, -1, sizeof(sg));
    while(t--){
        scanf("%d", &n);
        int flag = 0;
        for(int i=1; i<=n; i++){
            scanf("%d%d", &a[i].x,&a[i].y);
            if(a[i].x==0||a[i].y==0||a[i].x==a[i].y) flag = 1;
        }
        if(flag){
            puts("^o^");
            continue;
        }
        int ans = 0;
        for(int i=1; i<=n; i++){
            ans ^= SG(a[i].x, a[i].y);
        }
        if(ans == 0) puts("T_T");
        else puts("^o^");
    }
    return 0;
}