POJ - 2234 Matches Game (尼姆博奕)

Dear 丶 2022-05-19 03:58 149阅读 0赞

# **                                        Matches Game** #

### Description ###

Here is a simple game. In this game, there are several piles of matches and two players. The two player play in turn. In each turn, one can choose a pile and take away arbitrary number of matches from the pile (Of course the number of matches, which is taken away, cannot be zero and cannot be larger than the number of matches in the chosen pile). If after a player’s turn, there is no match left, the player is the winner. Suppose that the two players are all very clear. Your job is to tell whether the player who plays first can win the game or not.

### **Input** ###

The input consists of several lines, and in each line there is a test case. At the beginning of a line, there is an integer M (1 <= M <=20), which is the number of piles. Then comes M positive integers, which are not larger than 10000000. These M integers represent the number of matches in each pile.

### **Output** ###

For each test case, output "Yes" in a single line, if the player who play first will win, otherwise output "No".

### **Sample Input** ###

2 45 45

3 3 6 9

### **Sample Output** ###

Yes

**题意描述：**

尼姆博奕，有m堆石子且数量不一定，两人轮流取石子，可以从任意一堆取任意数量的石子（不能为0）先取完石子的人获胜；问先手是否能够取得胜利。

**解题思路：**  
尼姆博弈将堆的石子全部按位异或若最后结果为0则先手输；否则先手赢。

#include<stdio.h>
    int main()
    {
    	int sum,a[100],i,n;
    	while(scanf("%d",&n)!=EOF)
    	{
    		sum=0;
    		for(i=1;i<=n;i++)
    		{
    			scanf("%d",&a[i]);
    			sum^=a[i];
    		}
    		
    		if(sum==0)
    			printf("No\n");
    		else
    			printf("Yes\n");
    	}
    	return 0;
    }