HDU 1850

男娘i 2022-06-17 14:12 93阅读 0赞

# Being a Good Boy in Spring Festival #

**Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 7357    Accepted Submission(s): 4474**

Problem Description

一年在外 父母时刻牵挂  
春节回家 你能做几天好孩子吗  
寒假里尝试做做下面的事情吧  
  
陪妈妈逛一次菜场  
悄悄给爸爸买个小礼物  
主动地 强烈地 要求洗一次碗  
某一天早起 给爸妈用心地做回早餐  
  
如果愿意 你还可以和爸妈说  
咱们玩个小游戏吧 ACM课上学的呢～  
  
下面是一个二人小游戏：桌子上有M堆扑克牌；每堆牌的数量分别为Ni(i=1…M)；两人轮流进行；每走一步可以任意选择一堆并取走其中的任意张牌；桌子上的扑克全部取光，则游戏结束；最后一次取牌的人为胜者。  
现在我们不想研究到底先手为胜还是为负，我只想问大家：  
——“先手的人如果想赢，第一步有几种选择呢？”

Input

输入数据包含多个测试用例，每个测试用例占2行，首先一行包含一个整数M(1<M<=100)，表示扑克牌的堆数，紧接着一行包含M个整数Ni(1<=Ni<=1000000，i=1…M)，分别表示M堆扑克的数量。M为0则表示输入数据的结束。

Output

如果先手的人能赢，请输出他第一步可行的方案数，否则请输出0，每个实例的输出占一行。

Sample Input

3
    5 7 9
    0

Sample Output

起初想的是这题有什么特殊情况。将所有特殊情况判断一下就行，以为答案会比较小。

然而事实并非如此

**[转自][Link 1]**

这题里说的是尼姆博弈的问题，尼姆博弈说的是三堆，但是他的方法却可以推广到任意堆。  
  
姆博奕（Nimm Game）：有三堆各若干个物品，两个人轮流从某一堆取任意多的  
物品，规定每次至少取一个，多者不限，最后取光者得胜。  
  
这种情况最有意思，它与二进制有密切关系，我们用（a，b，c）表示某种局势，首先（0，0，0）显然是奇异局势，无论谁面对奇异局势，都必然失败。第二种奇异局势是（0，n，n），只要与对手拿走一样多的物品，最后都将导致（0，0，0）。仔细分析一下，（1，2，3）也是奇异局势，无论对手如何拿，接下来都可以变为（0，n，n）的情形。  
  
计算机算法里面有一种叫做按位模2加，也叫做异或的运算，我们用符号（+）表示这种运算。这种运算和一般加法不同的一点是1+1=0。先看（1，2，3）的按位模2加的结果：  
  
1 =二进制01  
2 =二进制10  
3 =二进制11 （+）  
———————  
0 =二进制00 （注意不进位）  
  
对于奇异局势（0，n，n）也一样，结果也是0。  
  
任何奇异局势（a，b，c）都有a（+）b（+）c =0。  
  
如果我们面对的是一个非奇异局势（a，b，c），要如何变为奇异局势呢？假设 a < b< c,我们只要将 c 变为 a（+）b,即可,因为有如下的运算结果: a（+）b（+）(a（+）b)=(a（+）a)（+）(b（+）b)=0（+）0=0。要将c 变为a（+）b，只要从 c中减去 c-（a（+）b）即可。  
  
例1。（14，21，39），14（+）21=27，39-27=12，所以从39中拿走12个物体即可达到奇异局势（14，21，27）。  
  
例2。（55，81，121），55（+）81=102，121-102=19，所以从121中拿走19个物品  
就形成了奇异局势（55，81，102）。  
  
例3。（29，45，58），29（+）45=48，58-48=10，从58中拿走10个，变为（29，4  
5，48）。

#include<stdio.h>
    int main()
    {
        int x,m,a[110],i,ans;
        while(scanf("%d",&m),m)
        {
             x=ans=0;
             for(i=0;i<m;i++)
             {
                    scanf("%d",&a[i]);
                    x^=a[i];//把所有数都（+）起来，存在x里面 
             }
             for(i=0;i<m;i++)
             ans+=(a[i]>(x^a[i]));//这里把x跟a[i]异或，可以得到出a[i]外所有数异或的结果。如果a[i]-(x^a[i])是正数，说明方法数可以加一 
             printf("%d\n",ans);
        }
        return 0;
    }

[Link 1]: http://www.cnblogs.com/huzhenbo113/p/3263479.html