bzoj1115 [POI2009]石子游戏Kam

题目链接

solution

很容易想到先差分。这样在第(i)堆拿走(k)个石子，就相当于让(a_i-k,a_{i+1}+k)。

我们重新看这个问题，就是在差分后，每次可以将第(i)堆的石子拿出一部分放到第(i+1)堆。这样就成了阶梯(NIM)。

我们将从(n)开始数的奇数列看做石子来做普通(NIM)游戏。如果我们当前处于必胜态，那么如果对方将奇数列的石子移到了偶数列，那就相当于对方取走了这些石子，我们按照(NIM)游戏中的必胜策略进行就行。如果对方将偶数列的石子移到了奇数列，那么我们再将这些石子移到下一个偶数列，那么相当于这一回合什么都没干。局面不变。

所以，阶梯(NIM)的胜负情况和将奇数列抽出来做NIM游戏的胜负情况相同。

code

/*
* @Author: wxyww
* @Date:   2020-04-28 10:51:02
* @Last Modified time: 2020-04-28 10:53:26
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
#include<cmath>
using namespace std;
typedef long long ll;
const int N = 1010;
ll read() {
	ll x = 0,f = 1;char c = getchar();
	while(c < '0' || c > '9') {
		if(c == '-') f = -1; c = getchar();
	}
	while(c >= '0' && c <= '9') {
		x = x * 10 + c - '0'; c = getchar();
	}
	return x * f;
}
int a[N];
int main() {
	int T = read();
	while(T--) {
		int n = read();
		for(int i = 1;i <= n;++i) a[i] = read();
		for(int i = n;i >= 1;--i) a[i] -= a[i - 1];
		int ans = 0;
		for(int i = n;i >= 1;i -= 2) {
			ans ^= a[i];
		}
		puts(ans ? "TAK" : "NIE");
	}

	return 0;
}