首页 > 代码库 > hdu 2176 取(m堆)石子游戏

hdu 2176 取(m堆)石子游戏

题目:链接:http://acm.hdu.edu.cn/showproblem.php?pid=2176

题意:

思路:

    NIMM博弈。

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int m,n[200010];//m是石子的堆数,数组存储的是每堆石子的个数

int main()
{
    int s,sum;
    while(scanf("%d",&m) != EOF && m)
    {
        sum = 0;
        for(int i=0; i<m; i++)
        {
            cin>>n[i];
            sum ^= n[i];//根据NIMM博弈的推理策略,应该对每一堆的石子进行异或运算
        }
        if(sum == 0)//先取者总是遇见非奇异局势(第一次就是非奇异局势)
            cout<<"No"<<endl;
        else//否则,第一次面对的是奇异局势
        {
            cout<<"Yes"<<endl;
            for(int i=0; i<m; i++)
            {
                s = sum^n[i];
                if(s<n[i])//如果小于相应堆的是石子数,那么就输出
                    cout<<n[i]<<" "<<s<<endl;
            }
        }
    }
    return 0;
}