算法

POJ1740总结

A New Stone Game

题目来源

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

我的代码

我一开始想着用状态压缩来进行记忆化搜索,直到找到一个必胜点或者必败点,但是状态实在是太多了怎么压缩都不行,所以只好放弃。其实博弈题我没怎么做过,也没想到这一题的必胜态和必败态这么简单就能判断出来了(似乎博弈题都是要找规律,且几步之内必然出现结果)。

这题很灵活的是对一堆石子的处理方式十分灵活,可以舍弃也可以移动,数量上也没有限制。我看的是网上的解法,大家的方法大体上都是一致的,证明过程也不复杂。

#include<stdio.h>
#include<algorithm>

using namespace std;

int main()
{
	int n;
	while(scanf("%d",&n)==1&&n!=0)
	{
		int stones[11];
		for (int i=0;i<n;i++) scanf("%d",&stones[i]);
		if (n%2==1) printf("1\n");
		else
		{
			sort(stones,stones+n);
			int flag=0;
			for(int i=0;i<n;i=i+2)
			{
				if(stones[i]!=stones[i+1])
				{
					flag=1;
					break;
				}
			}
			printf("%d\n",flag);
		}
	}
	return 0;
}

关于拆分数值最大的堆来补全其它的堆,画个图就很好理解。

反思

最近急于去寻找一些dp律的题目做,毛毛躁躁的,这道题也没有好好去想。

发表评论