首页 > ACM题库 > HDU-杭电 > hdu 2176 取(m堆)石子游戏-线性结构-[解题报告]C++
2013
12-30

hdu 2176 取(m堆)石子游戏-线性结构-[解题报告]C++

取(m堆)石子游戏

问题描述 :

m堆石子,两人轮流取.只能在1堆中取.取完者胜.先取者负输出No.先取者胜输出Yes,然后输出怎样取子.例如5堆 5,7,8,9,10先取者胜,先取者第1次取时可以从有8个的那一堆取走7个剩下1个,也可以从有9个的中那一堆取走9个剩下0个,也可以从有10个的中那一堆取走7个剩下3个.

输入:

输入有多组.每组第1行是m,m<=200000. 后面m个非零正整数.m=0退出.

输出:

输入有多组.每组第1行是m,m<=200000. 后面m个非零正整数.m=0退出.

样例输入:

2
45 45
3
3 6 9
5
5 7 8 9 10
0

样例输出:

No
Yes
9 5
Yes
8 1
9 0
10 3

Nim博弈

解法和HDU1850相似:http://blog.csdn.net/qinmusiyan/article/details/7949557

#include<iostream>
#include<cstdio>
using namespace std;
const int N=200002;
int a[N];
int main()
{
    int m,sum,s,i;
	while(scanf("%d",&m)!=EOF&&m)
	{
	    sum=0;
		for(i=0;i<m;i++)
		{ 
			scanf("%d",&a[i]);
			sum=sum^a[i];
		}
		if(sum==0) printf("No\n");
		else
		{
		   printf("Yes\n");
		   for(i=0;i<m;i++)
		   {
		       s=sum^a[i];
			   if(s<a[i])
				   printf("%d %d\n",a[i],s);
		   
		   }
		
		}
	
	}
   return 0;
}

解题转自:http://blog.csdn.net/qinmusiyan/article/details/7949958