1115: [POI2009]石子游戏Kam
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大牛翻译.
博弈论
#include<cstdio>
#define MaxN 1010
int T;
int N,A[MaxN],Ans;
int main(){
scanf("%d",&T);
for (;T--;){
scanf("%d",&N);
for (int i=1;i<=N;++i)
scanf("%d",&A[i]);
Ans=0;
for (int i=N;i>1;i-=2)
Ans^=(A[i]-A[i-1]);
if (N%2) Ans^=A[1];
if (Ans) printf("TAK\n");
else printf("NIE\n");
}
}
评论 (0)
