首页 > 代码库 > BZOJ 1115: [POI2009]石子游戏Kam
BZOJ 1115: [POI2009]石子游戏Kam
1115: [POI2009]石子游戏Kam
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 883 Solved: 545
[Submit][Status][Discuss]
Description
有N堆石子，除了第一堆外，每堆石子个数都不少于前一堆的石子个数。两人轮流操作每次操作可以从一堆石子中移走任意多石子，但是要保证操作后仍然满足初始时的条件谁没有石子可移时输掉游戏。问先手是否必胜。
Input
第一行u表示数据组数。对于每组数据，第一行N表示石子堆数，第二行N个数ai表示第i堆石子的个数(a1<=a2<=……<=an)。 1<=u<=10 1<=n<=1000 0<=ai<=10000
Output
u行，若先手必胜输出TAK，否则输出NIE。
Sample Input
2
2
2 2
3
1 2 4
2
2 2
3
1 2 4
Sample Output
NIE
TAK
TAK
HINT
感谢MT大牛翻译.
Source
分析
转换成阶梯Nim游戏.
代码
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define read(x) scanf("%d",&x) 4 main(){ 5 int cas;read(cas); 6 while(cas--){ 7 int n,t=0,l=0;read(n); 8 for(int i=1,x;i<=n;++i) 9 read(x),t^=((n-i)&1)?0:x-l,l=x; 10 puts(t?"TAK":"NIE"); 11 } 12 }
记得在和谁比缩代码来着，不知不觉就写难看了……
@Author: YouSiki
BZOJ 1115: [POI2009]石子游戏Kam
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。