天天看点

hdu 1849 Rabbit and Grass Nim博弈

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

题意:游戏的规则是这样的:

  • 棋盘包含1*n个方格,方格从左到右分别编号为0,1,2,…,n-1;
  • m个棋子放在棋盘的方格上,方格可以为空,也可以放多于一个的棋子;
  • 双方轮流走棋;
  • 每一步可以选择任意一个棋子向左移动到任意的位置(可以多个棋子位于同一个方格),当然,任何棋子不能超出棋盘边界;
  • 如果所有的棋子都位于最左边(即编号为0的位置),则游戏结束,并且规定最后走棋的一方为胜者。

    给出初始棋子状态,输出先手赢,或者后手赢。

必胜态必败态

对于一个

hdu 1849 Rabbit and Grass Nim博弈

游戏的局面

hdu 1849 Rabbit and Grass Nim博弈

,它是

hdu 1849 Rabbit and Grass Nim博弈

当且仅当

hdu 1849 Rabbit and Grass Nim博弈

^

hdu 1849 Rabbit and Grass Nim博弈

^...^

hdu 1849 Rabbit and Grass Nim博弈

,其中^表示异或(xor)运算。

#include <iostream>
#include<cstdio>
#include<cmath>

using namespace std;

int main()
{
    int n;
    while(~scanf("%d",&n)&&n)
    {
        int ans=0;
        for(int i=0;i<n;i++)
        {
            int t;
            scanf("%d",&t);
            ans^=t;
        }
        if(ans) cout<<"Rabbit Win!"<<endl;
        else    cout<<"Grass Win!"<<endl;
    }
}