【转载】尼姆博弈 - dblank

# 【转载】尼姆博弈

http://www.cnblogs.com/kuangbin/archive/2011/08/28/2156426.html

HDU 1850：Being a Good Boy in Spring Festival

http://acm.hdu.edu.cn/showproblem.php?pid=1850

①：当ans==0时为必输态T态（谁面对这种状态谁必输），否则为必赢态S态，其中所有苹果全被取完的状态

②：对于T态，无论怎么取都将变为S态，对于S态，一定有方法取成T态，这也是①的证明

③：对于S态每一项k[i]，如果ans^k[i]<k[i]，就说明可以从k[i]堆中取出一定数量的苹果使其剩下ans^k[i]个苹

#include<stdio.h>
int main(void)
{
int n, i, k[105], ans, sum;
while(scanf("%d", &n), n!=0)
{
ans = sum = 0;
for(i=1;i<=n;i++)
{
scanf("%d", &k[i]);
ans ^= k[i];
}
for(i=1;i<=n;i++)
{
if((ans^k[i])<=k[i])
sum++;
}
if(ans==0)
printf("0n");
else
printf("%dn", sum);
}
return 0;
}

HDU 2509：Be the Winner

http://acm.hdu.edu.cn/showproblem.php?pid=2509

#include<stdio.h>
int main(void)
{
int n, i, k[105], ans, flag, sum;
while(scanf("%d", &n)!=EOF)
{
ans = flag = sum = 0;
for(i=1;i<=n;i++)
{
scanf("%d", &k[i]);
ans ^= k[i];
if(k[i]>1)
flag = 1;
if(k[i]>0)
sum++;
}
if(flag==0)
{
if(sum%2==0)
printf("Yesn");
else
printf("Non");
}
else
{
if(ans==0)
printf("Non");
else
printf("Yesn");
}
}
return 0;
}