POJ - 1740 A New Stone Game （博弈）

不念不忘少年蓝@ 2022-05-19 02:37 367阅读 0赞

#                                      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

**题意描述：**

有n堆石头两名玩家，玩家从任意一堆中取走任意数量的石头（必须要取），然后可以将任意数量的石头分配给其他的堆上（也可以选择不分配）；最后取完石头的获胜。

**解题思路：**

从网上看了别人的题解，懂得了游戏胜负判断：

分析：

首先看两堆：1 1 的状态肯定是先手输~~但是俩数不一样的话就是先手赢了。。

再看三堆：1 1 1的状态肯定是先手赢，1 2 1也是先手赢。。。1 2 2也是先手赢。。总之都是先手赢。。

再看四堆：1 1 2 2 这样的肯定是先手输。。1 1 2 3 这样的就是先手赢了。。。1 2 3 4是先手赢。。

再看五堆：1 1 1 1 1 是先手赢。。1 1 1 1 2 先手赢。。。。…………都是先手赢。。1 2 3 4 1  也是先手赢。。。。各种先手赢。。

综上：奇数堆，先手必胜，偶数堆只要不是成对出现的数量先手也是赢；也就是说除了偶数堆且所有数量成对的情况，其他情况都是先手赢。

#include<stdio.h>
    #include<string.h>
    int main()
    {
    	int n,num[105],i,m,f;
    	while(scanf("%d",&n))
    	{
    		if(n==0)
    		{
    			break;
    		}
    		memset(num,0,sizeof(num));
    		for(i=1;i<=n;i++)
    		{
    			scanf("%d",&m);
    			num[m]++;
    		}
    		if(n%2==1)
    			printf("1\n");
    		else
    		{
    			f=0;
    			for(i=1;i<=100;i++)
    				if(num[i]%2==1)
    				{
    					f=1;
    					printf("1\n");
    					break;
    				}
    			if(f==0)
    				printf("0\n");
    		}
    	}
    	return 0;
    }