Being a Good Boy in Spring Festival
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7382 Accepted Submission(s): 4490
春节回家 你能做几天好孩子吗
寒假里尝试做做下面的事情吧
陪妈妈逛一次菜场
悄悄给爸爸买个小礼物
主动地 强烈地 要求洗一次碗
某一天早起 给爸妈用心地做回早餐
如果愿意 你还可以和爸妈说
咱们玩个小游戏吧 ACM课上学的呢～
下面是一个二人小游戏：桌子上有M堆扑克牌；每堆牌的数量分别为Ni(i=1…M)；两人轮流进行；每走一步可以任意选择一堆并取走其中的任意张牌；桌子上的扑克全部取光，则游戏结束；最后一次取牌的人为胜者。
现在我们不想研究到底先手为胜还是为负，我只想问大家：
——“先手的人如果想赢，第一步有几种选择呢？”
题意： 二人小游戏：m堆扑克牌，每次可以取其中一堆中的任意张，最后没有牌取了则为败者（即最后一次取牌的人为胜者）。这道题不是简单的直接判断是否先手能够获胜，而是求如果先手能够获胜，那么第一步有多少种可行方案数。如果先手不能获胜，输出0。
思路：
1.先直接求出先手是否能够获胜，方法是
对于一个Nim游戏的状态(a1,a2,...,an)，如果a1^a2^...^an=0 ，那么先手必败。（也就是说，a1^a2^...^an ！=0，那么先生必胜）
2.看能否通过减少其中某一堆的数量，使其变成必败状态。
令当前状态为sum，
如果能够获胜，那么sum = a1^a2^...^an ！= 0；
现在从第1堆开始看，能否通过减少第1堆中牌的数量（因为只能取牌，所以是减少牌的数目），使状态变为必败状态，
如果想让下一个状态为必败状态，那么只要让 a1' =a2^a3^...^an 即可（此时 ，a1'^a2^...^an =(a2^a3^...^an)^(a2^a3^...^an)
= 0 ，状态变为必败状态）
那么问题来了，当前牌的数目能变成 a1' 吗？也就是说a1能变成
a1' 吗？
这里只需要判断 a1 大于
a1' 就可以了：
a1 大于
a1'，可以减少第1堆牌的数目变成必败状态。否则，不能。
相应的，通过判断 ai 大于
ai' ： ai大于ai'，可以减少第i堆牌的数目变成必败状态。否则，不能。
hint：这里在求ai' 的时候不必每次都求 a1^a2^...^ai -1 ^ ai +1^...^an ，而是利用第1步求出来的
当前状态 sum = a1^a2^...^an ，两边异或a1，
a1^sum =
a1^ a1^a2^...^an =
a2^...^an = a1'
a1' =a1 ^ sum
相应的 sum = a1^a2^...^ ai^...^an ，两边异或 ai，
ai^sum = a1^a2^...^ai ^ai ^...^an = ai'
ai' = ai ^ sum
推出，如果 (ai^sum) < ai ，那么方案可行。
代码：
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
int ni[110];
int m;
int i;
int sum;//状态
int ans;//可行的方案数
while(scanf("%d",&m),m){
sum=0;//初始化为0
for(i=0;i<m;i++){
scanf("%d",&ni[i]);
sum=sum^ni[i];
}
if(sum){
ans=0;
for(i=0;i<m;i++){
if((sum^ni[i])<ni[i]){//第i堆的数目多，可以减少第i堆数目，变成必败状态
ans++;
}
}
printf("%d
",ans);
}
else{
printf("%d
",0);
}
}
return 0;
}