【POJ】A New Stone Game（博弈论）

时间：2023-03-09 13:23:19
【POJ】A New Stone Game（博弈论）

http://poj.org/problem?id=1740

题目大意就是，对于n堆石子，每堆若干个，两人轮流操作，每次操作分两步，第一步从某堆中去掉至少一个，第二步（可省略）把该堆剩余石子的一部分分给其它的某些堆。最后谁无子可取即输。

看了题解感觉太神了。

首先我们来分析：

当只有一堆时，先手必胜，直接一次取完即可

当有两堆时，分两种情况，一是两堆相同时，先手必输，因为无论先手怎样取，后手总有办法再次平衡两堆；而是两堆不同时，先手必胜，因为先手总有办法先平衡两堆，然后就像一的情况。

当有三堆时，先手总有办法平衡为两堆。（将最多的那堆部分，然后将剩余的补满另外两堆最少的）

当有偶数堆并且从小到大排序后两两相等（即1、2堆相等，3、4堆相等，5、6堆相等...），先手必输，因为无论先手怎样取，后手总能将堆数平衡为偶数堆且两两相等。

当有奇数堆时，先手必胜，因为将所有堆从小到大排序后，取最大的一堆并一定能够补满一一对应的堆平衡，成为第四种情况（将前边的堆的高度差映射到y轴，可以发现总和一定小于，注意是小于最高的那堆，所以一定能够平衡这些一一对应的堆）

当有偶数堆时，从小到大排序后有一一对应的堆不平衡时，先手必胜，因为先手总能先将这些偶数堆平衡，成为第四种情况，（最大的堆去掉至少一个后，将剩余石头与最小堆的高度差的石头移动到其它堆平衡，而且一定能够平衡！同上一种情况，映射到y轴即可）

所以我们只要判断当偶数堆时是否一一对应的石头一定平衡，如果是，那么先手必输，如果不是，先手必胜。

#include <cstdio>

#include <cstring>

#include <cmath>

#include <string>

#include <iostream>

#include <algorithm>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); ++i)

#define for1(i,a,n) for(int i=(a);i<=(n);++i)

#define for2(i,a,n) for(int i=(a);i<(n);++i)

#define for3(i,a,n) for(int i=(a);i>=(n);--i)

#define for4(i,a,n) for(int i=(a);i>(n);--i)

#define CC(i,a) memset(i,a,sizeof(i))

#define read(a) a=getint()

#define print(a) printf("%d", a)

#define dbg(x) cout << #x << " = " << x << endl

#define printarr(a, n, m) rep(aaa, n) { rep(bbb, m) cout << a[aaa][bbb]; cout << endl; }

inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }

inline const int max(const int &a, const int &b) { return a>b?a:b; }

inline const int min(const int &a, const int &b) { return a<b?a:b; }

const int N=1000;

int a[N], n;

int main() {

	while(~scanf("%d", &n) && n) {

		rep(i, n) read(a[i]);

		if(n&1) puts("1");

		else {

			bool flag=0;

			sort(a, a+n);

			for(int i=0; i<n; i+=2) if(a[i]!=a[i+1]) { flag=1; break; }

			if(flag) puts("1");

			else puts("0");

		}

	}

	return 0;

}

Description

Alice and Bob decide to play a new stone game.At the beginning of the game they pick n(1<=n<=10) piles of stones in a line. Alice and Bob move the stones in turn.
At each step of the game,the player choose a pile,remove at least
one stones,then freely move stones from this pile to any other pile that
still has stones.

For example:n=4 and the piles have (3,1,4,2) stones.If the player
chose the first pile and remove one.Then it can reach the follow states.

2 1 4 2

1 2 4 2（move one stone to Pile 2）

1 1 5 2（move one stone to Pile 3）

1 1 4 3（move one stone to Pile 4）

0 2 5 2（move one stone to Pile 2 and another one to Pile 3）

0 2 4 3（move one stone to Pile 2 and another one to Pile 4）

0 1 5 3（move one stone to Pile 3 and another one to Pile 4）

0 3 4 2（move two stones to Pile 2）

0 1 6 2（move two stones to Pile 3）

0 1 4 4（move two stones to Pile 4）

Alice always moves first. Suppose that both Alice and Bob do their best in the game.

You are to write a program to determine who will finally win the game.

Input

The
input contains several test cases. The first line of each test case
contains an integer number n, denoting the number of piles. The
following n integers describe the number of stones in each pile at the
beginning of the game, you may assume the number of stones in each pile
will not exceed 100.

The last test case is followed by one zero.

Output

For each test case, if Alice win the game,output 1,otherwise output 0.

Sample Input

3

2 1 3

2

1 1

0

Sample Output

1

0

Source

相关文章