主要是写一下nim博弈的理解,这个题有点奇怪,不知道为什么判断奇偶性,如果有大佬知道还请讲解一下.
//nim博弈
//a[0]~a[i] 异或结果为k 若k=0 则为平衡态 否则为非平衡态
//平衡态转化为非平衡态 :一定有 a[n]^k<a[n] a[0]^……a[n]^k……^a[i]=0
//二进制为什么能判断平衡态 并且转化 将每一对转化为二进制的小堆
/*,每个正整数都有对应的一个二进制数,
例如:57(10)à 111001(2) ,即:57(10)=25+24+23+20。
于是,我们可以认为每一堆硬币数由2的幂数的子堆组成。
这样,含有57枚硬币大堆就能看成是分别由数量为25、24、23、20的各个子堆组成。
如果每一种大小的子堆的个数都是偶数,我们就称Nim取子游戏是平衡的,
而对应位相加是偶数的称为平衡位,否则称为非平衡位。
7 0 1 1 1
9 1 0 0 1
12 1 1 0 0
15 1 1 1 1
找到 a[n]^k<a[n] 将a[n]转化为 a[n]^k 即为平衡态
*/
#include<stdio.h>
int main()
{
int n,t,a[120],z=1;
scanf("%d",&t);
while(t--)
{
int sum=0,flag=0;
scanf("%d",&n);
for(int i=0; i<n; i++)
{
scanf("%d",&a[i]);
if(a[i]!=1)
flag=1;
}
//printf("sum=%d\n",sum);
printf("Case %d:",z++);
if(flag)
{
for(int i=0; i<n; i++)
sum=sum^a[i];
if(sum==0)
printf(" Bob\n");
else
printf(" Alice\n");
}
else
{
if(n%2==1)
printf(" Bob\n");
else
printf(" Alice\n");
}
}
return 0;
}