首页 > 代码库 > hdu 1850 Being a Good Boy in Spring Festival (尼姆博弈)

hdu 1850 Being a Good Boy in Spring Festival (尼姆博弈)

2024-07-18 11:39:17   226人阅读

Being a Good Boy in Spring Festival

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4658    Accepted Submission(s): 2781


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
35 7 90
 

 

Sample Output
1
 
 
尼姆博弈：

当nim游戏的某个位置：（x1,x2,x3），当且仅当其各部分的nim-sum = 0(即x1⊕x2⊕x3 = 0（也就是各部分的异或为0）)
当前位置为必败点，这对于多个堆的情况同样适用。

即，

有三堆各若干个物品，两个人轮流从某一堆取任意多的物品（或者最多m个，只需把每堆%m），规定每次至少取一个，多者不限，最后
取光者得胜。
a1^a2^a3^..^an结果为0.则先手必输，否则必赢。

样例：5 7 9

7^9 = 14

如果要拿走K个，那么如果要结果还是为0

则5-k = 14  k >=1 所以必须要 5 > 14（这里不成立）。 即 那一堆的数目 > 其他堆的异或和

 

 1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <string> 5 using namespace std; 6 #define maxn 1000010 7 int a[maxn]; 8 int M; 9 int main(){10     while(scanf("%d", &M) && M){11         for(int i = 1; i <= M; i++) scanf("%d", &a[i]);12         int sum = a[1];13         for(int i = 2; i <= M; i++){14             sum^=a[i];15         }16         if( sum == 0) cout<<0<<endl;17         else{18             sum = 0;19             int cnt = 0;20             for(int i = 1; i <= M; i++){21                 sum = 0;22                 for(int j = 1; j <= M; j++){23                     if(i == j) continue;24                     else sum ^= a[j];25                 }26                 if(sum < a[i] ) cnt++;27             }28             cout<<cnt<<endl;29         }30     }31     32     return 0;33 }

 

 


联系
我们