注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ1457]棋盘游戏  

2015-03-17 07:28:59|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1457: 棋盘游戏

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 208  Solved: 109
[Submit][Status][Discuss]

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

Solution

如果只将(0,0)看作必败态的话,打出来的sg表示这样的:
0 1 2 3 4...
1 2 0 4 5...
2 0 1 5 3...
3 4 5 6 2...
4 5 3 2 7...
...
显然不符合样例,怎么办呢?
不妨换一个思路,将x=0,y=0,x=y三条直线看作必败态,然后打出来的sg表长这样:
0 0 0 0 0 0...
0 0 0 1 2 3...
0 0 0 2 3 1...
0 1 2 0 4 0...
0 2 3 4 0 5...
0 3 1 0 5 0...
...
这样就符合样例啦。注意要特判,如果存在一个棋子能直接转移到(0,0)的话就直接输出先手必胜。

Code

/**************************************************************
    Problem: 1457
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:52 ms
    Memory:852 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
int i,j,k,n,map[110][110],f[200],flag,t,sg;
int main(){
    n=100;
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)if(i!=j){
        memset(f,0,sizeof(f));
        for(k=1;k<i;k++)if(i-k!=j)f[map[i-k][j]]=1;
        for(k=1;k<j;k++)if(i!=j-k)f[map[i][j-k]]=1;
        for(k=1;k<i&&k<j;k++)f[map[i-k][j-k]]=1;
        for(k=0;f[k];k++);map[i][j]=k;
    }
    for(scanf("%d",&t);t--;){
        flag=sg=0;
        for(scanf("%d",&n);n--;){
            scanf("%d%d",&i,&j);
            if(i==0||j==0||i==j)flag=1;
            else sg^=map[i][j];
        }
        if(flag||sg)puts("^o^");
        else puts("T_T");
    }
}

  评论这张
 
阅读(71)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018