题目链接:https://vjudge.net/contest/299140#problem/E
密码:2019
题目大意:
爱丽丝和鲍勃正在玩MisèreNim游戏。MisèreNim是一个玩k堆石头的游戏,每堆都包含一块或多块石头。球员交替游戏,并且在每个回合中玩家可以选择其中一个堆,并且可以从该堆中移除若干石块,除非堆是空的。在每个回合中,玩家必须从任何堆中移除至少一块石头。爱丽丝首先开始。移除最后一块石头的玩家将输掉游戏。
如果Alice赢了,打印案例编号和’Alice’,否则打印’Bob’。
思路:nim博弈就是胜利和失败的条件换了一下。当然还有一个特例:就是所有堆的石子都为1时。这个时候判断石头的堆数的奇偶性判断输赢。
#include <bits/stdc++.h>
#define LL long long
using namespace std;
int main()
{
int T, CUT=0;
scanf("%d",&T);
while(T--)
{
CUT++;
int n, a, ans=0, k=0;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&a);
if(a==1)
{
k++;
}
ans^=a;
}
if(k!=n)
{
if(ans)
{
printf("Case %d: Alice\n",CUT);
}
else
{
printf("Case %d: Bob\n",CUT);
}
}
else
{
if(k%2)
{
printf("Case %d: Bob\n",CUT);
}
else
{
printf("Case %d: Alice\n",CUT);
}
}
}
return 0;
}