MENU

尼姆博弈(Nim Game)

April 15, 2018 • Read: 3936 • 算法阅读设置

简述

有若干堆石子,每堆石子的数量都是有限的,合法的移动是 “选择一堆石子并拿走若干颗(不能不拿)”,如果轮到某个人的时候所有石子堆都已经被拿空了,则判负(因为他此时没有任何合法的移动)

分析

这游戏看上去有些复杂,我们先从简单情况开始研究,如果轮到你时,只剩下一堆石子,那么此时必胜策略肯定是把这堆石子全部拿完,然后对手没有石子拿就输了;如果剩下两堆不相等的石子,必胜策略是通过取多的一堆石子将两堆石子变得相等,之后对手如果在某一堆拿若干颗,你就在另一堆拿同样多的数量,直至胜利;但是如果还剩三堆,应该怎么分析呢?假设有三堆石子(a,b,c),我们前面说到,如果只有两堆石子,并且石子数量满足(n,n),谁先手谁就输。其实我们可以把三堆石子问题转换成两堆,只要满足状态(0,n,n)并且此时是对方先手,那我方按照两堆石子的取法,就能获胜。对于这种(0,n,n)的局势,我们称为奇异局势。对任何奇异局势(a,b,c)都有 a^b^c=0(^ 表示异或),如果我们面对非奇异局势,要如何变为奇异局势呢?假设 a<b<c,我们只要将 c 变为 a^b 即可。道理很简单,因为 a^b^(a^b)=0。要将 c 变为 a^b 也很简单,只要从 c 中减去 c-a^b 即可

例(14,21,39),14^21=27,39-27=12,所以从 39 中拿走 12 个,即可变成奇异局势(14,21.27)

题目链接:HDU1849 Rabbit and Grass

题解

将输入的值存在数组中,然后连续求异或(0对任意数异或都得任意数本身)

代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int m;
    int a[1001];
    while(cin>>m&&m)
    {
        int res = 0;
        memset(a,0,sizeof(a));
        for(int i = 0;i < m;i++)
        {
            cin>>a[i];
            res ^= a[i];
        }
        if(res == 0)
            cout<<"Grass Win!"<<endl;
        else
            cout<<"Rabbit Win!"<<endl;
    }
    return 0;
}
Last Modified: October 7, 2018
Archives Tip
QR Code for this page
Tipping QR Code