Bzoj 1115: [POI2009]石子游戏Kam

原题网址：http://www.lydsy.com/JudgeOnline/problem.php?id=1115

考虑将相邻两堆做差，那么原问题中一堆减少了就相当于新问题中一堆向右一动一格，那就变成了阶梯博弈，阶梯博弈又可以化归成奇数堆的nim游戏，因为奇数堆移到偶数堆相当于拿走了，因为偶数堆每移一次，可以再移一次再次移到偶数堆直至移除，所以偶数堆的相当于已经被移走了。

#include<bits/stdc++.h> const int N = 1050; int T,n,a[N]; int main(){ scanf("%d",&T); while (T--){ scanf("%d",&n); for (int i=1; i<=n; i++) scanf("%d",&a[i]); int t = 0; for (int i=n; i>0; i-=2) t ^= a[i] - a[i - 1]; if (t == 0) printf("NIE\n"); else printf("TAK\n"); } return 0; }