「BZOJ1115」[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
题解
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
#include<iostream> #include<cstring> #include<cstdio> using namespace std; int T,n,a[1001]; inline int read() { int x=0;char ch=getchar(); while(ch<'0'||ch>'9'){ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } int main() { T=read(); while(T--) { int ans=0; n=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=n;i>1;i-=2) ans^=(a[i]-a[i-1]); if(n&1)ans^=a[1]; if(ans)printf("TAK\n"); else printf("NIE\n"); } return 0; } |
Subscribe
计数器 9774995
OI 课件=>
OI 课件=>