POI2009 KAM-Pebbles

wjh15101051's space

卧薪尝胆，厚积薄发。

POI2009 KAM-Pebbles

Date: Mon Oct 29 14:41:29 CST 2018

In Category: NoCategory

Description：

给 $n$ 堆石子，每次可以把一堆石子中拿掉一些，但是不能比上一个位置石子数更少，问先手是否有必胜策略。

$1\leqslant testcases\leqslant 10,1\leqslant n\leqslant 1000$

Solution：

差分一下，每次就是把当前位置一些放到后面，于是就是一个阶梯尼姆游戏。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 1010

int a[MAXN];

int c[MAXN];

void work()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

	for(int i = 1;i <= n;++i)c[i] = a[i] - a[i - 1];

	int res = 0;

	for(int i = n;i >= 1;i -= 2)res ^= c[i];

	if(res != 0)puts("TAK");

	else puts("NIE");

	return;

}

int main()

{

	int testcases;

	scanf("%d",&testcases);

	while(testcases--)work();

	return 0;

}

In tag: 数学-博弈论

wjh15101051