[洛谷 3480][POI2009] KAM-Pebbles【SG定理】

  • 2018-02-28
  • 0
  • 0

Problem:

题目描述

Johny and Margaret are playing "pebbles".

Initially there is a certain number of pebbles on a table, grouped in n piles.

The piles are next to each other, forming a single row.

The arrangement of stones satisfies an additional property that each pile consists of at least as many pebbles as the one to the left (with the obvious exception of the leftmost pile).

The players alternately remove any number of pebbles from a single pile of their choice.

They have to take care, though, not to make any pile smaller than the one left to it.

In other words, the piles have to satisfy the initial property after the move as well.

When one of the players cannot make a move (i.e. before his move there are no more pebbles on the table), he loses.

Johny always starts, to compensate for Margaret's mastery in this game.

In fact Margaret is so good that she always makes the best move, and wins the game whenever she has a chance.

Therefore Johny asks your help - he would like to know if he stands a chance of beating Margaret with a particular initial arrangement.

Write a programme that determines answers to Johny's inquiries.

有N堆石子,除了第一堆外,每堆石子个数都不少于前一堆的石子个数。两人轮流操作每次操作可以从一堆石子中移走任意多石子,但是要保证操作后仍然满足初始时的条件谁没有石子可移时输掉游戏。问先手是否必胜。

输入输出格式

输入格式:

In the first line of the standard input there is a single integer u (1<=u<=10) denoting the number of initial pebble arrangements to analyse.

The following 2u lines contain descriptions of these arrangements; each one takes exactly two lines.

The first line of each description contains a single integer n,1<=n<=1000 - the number of piles.

The second line of description holds non-negative integers separated by single spaces and denoting the numbers of pebbles in successive piles, left to right.

These numbers satisfy the following inequality a1<=a2...<=an.

The total number of pebbles in any arrangement does not exceed 1000.

多组输入,第一行一个整数u代表数据组数(1<=u<=10)

接下来共2*u行,每两行代表一组数据:

第一行只有一个整数n(1<=n<=1000),表示石子堆数;

第二行有n个整数用空格隔开,第i个整数ai表示第i堆的石子个数,保证a1<=a2<=a3...<=an。

对于每组数据,保证石子总数不超过10000。

输出格式:

Precisely u lines should be printed out on the standard output.

The i-th of these lines (for 1 ≤ i ≤ u) should hold the word TAK (yes in Polish), if Johny can win starting with the i-th initial arrangement given in the input, or the word NIE (no in Polish), if Johny is bound to lose that game, assuming optimal play of Margaret.

输出u行,如果第i组数据先手必胜,输出“TAK”,否则输出“NIE”。

输入输出样例

输入样例#1:

2
2
2 2
3
1 2 4

输出样例#1:

NIE
TAK

Solution:

本题是 Nim 游戏的变体,只要通过简单转化即可变为普通 Nim 游戏。

考虑需要保持每堆石子个数单调递增,我们可以将其差分,转化成保持差分值为自然数

然后我们发现,从第 i 堆取走 x 个石子的操作在差分数列中体现为第 i 堆减 x,第 i + 1 堆加 x

也就是等价于在以差分值为石子个数的游戏中,将第 i 堆的 x 个石子转移到第 i + 1 堆中。

而我们知道,Nim 游戏的著名变体 “阶梯 Nim” 中有一个将某一级的任意个石子搬到下一级的问题,只需独立考虑奇数级台阶即可。因为若对方将偶数级台阶的石子搬到奇数级,则己方总能够将这些石子重新搬回到奇数级,抵消对方的操作。

所以本题就可以直接套用 “阶梯 Nim” 的思想求解。

而且单次取石子数不限的 Nim 游戏还有一个有用的结论,即 SG(x) = x (x 为石子个数)

Code: O(un) [1988K, 0MS]

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

inline void getint(int &num){
	char ch;
	while(!isdigit(ch = getchar()));
	num = ch - '0';
	while(isdigit(ch = getchar())) num = num * 10 + ch - '0';
}

int u, n, a[1002];

int main(){
	getint(u);
	while(u--){
		getint(n);
		for(register int i = 1; i <= n; i++) getint(a[i]);
		for(register int i = n; i > 1; i--) a[i] -= a[i - 1];  // Differencing
		int nimsum = 0;
		for(register int i = n; i > 0; i -= 2) nimsum ^= a[i];  // SG[x] == x where x is the number of stones in a normal Nim
		puts(nimsum ? "TAK" : "NIE");
	}
	return 0;
}

评论

还没有任何评论,你来说两句吧



新博客地址: darkleafin.cf

常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
Please refresh the page if the code cannot be displayed normally.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai