棋盘游戏

Time Limit:5000MS Memory Limit:65536K
Total Submit:21 Accepted:8
Case Time Limit:500MS

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

Sample Output

Source
囧。马上要期末考了。。颓废了半天。做道题放松一下。。
。这题让我更加深入的领会了Game Theory
首先看看有没有棋子可以一步到达（0，0）的。。有的话就先行者胜。。
然后把所有（0,x）,(x,0),(x,x)都看成必败态。。让其SG值为0.。接着算出所有其它点的SG值
Xor一下就OK了。。
上次忘发代码了悲剧囧。。补一下。。
Code：
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define Debug(x) cout<<#x<<"="<<x<<endl;
#define For(i,l,r) for(int i=l;i<=r;i++)
const int inf=~0U>>1,maxn=100;
using namespace std;
int Dp[maxn][maxn];
bool Set[maxn*3];
void Insert(int a,int b)
{
    if(a>0&&b>0&&a!=b)Set[Dp[a][b]]=true;
}
void PreDo()
{
    for(int i=1;i<maxn;i++)
        for(int j=1;j<maxn;j++)
        {
            memset(Set,0,sizeof Set);
            if(i!=j)
            {
                for(int k=1;k<maxn;k++)
                {
                    Insert(i-k,j);
                    Insert(i,j-k);
                    Insert(i-k,j-k);
                }
            }
            int&t=Dp[i][j]=0;
            while(Set[t])t++;
        }
}
void Solve()
{
    int n,x,y,s=0;bool win=false;
    scanf("%d",&n);
    rep(i,n)
    {
        scanf("%d%d",&x,&y);
        if(x==0||y==0||x==y)win=true;
        else s^=Dp[x][y];
    }
    if(win||s)puts("^o^");
    else puts("T_T");
}
int main()
{
    //freopen("in","r",stdin);
    PreDo();
    int t;cin>>t;rep(i,t)Solve();
}

^o^T_T数据范围T <= 10, N <= 1000

223 43 533 24 23 1