取火柴游戏，最后取者败

题意：n堆火柴，2人每次从任意一堆中取至少1个，也可以将整堆取完，取得最后一根火柴的人输

定义：若所有火柴数异或为0，则该状态被称为利他态，用字母T表示；否则，为利己态，用S表示。
火柴大于等于2的堆称为充裕堆火柴为1 的堆称为称为孤单堆

S T后的数字代表充裕堆的数量如果充裕堆大于等于2 就用2表示

S2 S1 T0 先手必胜
T2 S0 先手必败

S1 （2 1 1）先手把2变成1 变成S0
S1 （2 1 1 1）先手把2 拿完变成S0
T0 (1 1) 偶数个1 先手必胜
S0 (1) 奇数个1 先手必败
T2 （3 3）先手必败先手拿1个变成S2 拿2个变成S1 拿3个也是变成S1
S2 （3 4）先手必胜先手从4拿走一个转化成T2

T2态，只能转变为S2态或S1态
S2态可一次转变为T2态

HDU 1907

n堆火柴，2人每次从任意一堆中取至少1个，也可以将整堆取完，取得最后一根火柴的人输
Sample Input
2
3
3 5 1
1
1

Sample Output
John
Brother

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 const int maxn=101;
 6 int a[maxn];
 7 int main()
 8 {
 9     int t;
10     cin>>t;
11     while(t--)
12     {
13         int n;
14         cin>>n;
15         int ans=0;  //异或 
16         int sum1=0; //充裕堆 
17  
18         for(int i=0;i<n;i++)
19         {
20             cin>>a[i];
21             if(a[i]>=2)
22                 sum1++;
23 
24             ans^=a[i];
25         }
26         if((ans!=0&&sum1>0)||(ans==0&&sum1==0)) // S2 S1 T0 先手胜 
27             cout<<"John"<<endl;
28         else if((ans!=0&&sum1==0)||(ans==0&&sum1>1)) // S0 T2 后手胜 
29             cout<<"Brother"<<endl;
30     }
31     return 0;
32 }

View Code

HDU 2509

题目大意：有n堆苹果，每堆有mi个。两人轮流取，每次可以从一堆苹果中取任意连续个苹果，最后取光者为输。Fra先下，问是否可以获胜。 *** 可变为 ** 或 * 或* *（拿中间的）
Sample Input
2
2 2
1
3

Sample Output
No
Yes

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 const int maxn=101;
 6 int a[maxn];
 7 int main()
 8 {
 9         int n;
10         while(cin>>n)
11         {
12         
13         int ans=0;  //异或 
14         int sum1=0; //充裕堆 
15 
16         for(int i=0;i<n;i++)
17         {
18             cin>>a[i];
19             if(a[i]>=2)
20                 sum1++;
21 
22             ans^=a[i];
23         }
24         if((ans!=0&&sum1>0)||(ans==0&&sum1==0)) // S2 S1 T0 先手胜 
25             cout<<"Yes"<<endl;
26         else if((ans!=0&&sum1==0)||(ans==0&&sum1>1)) // S0 T2 后手胜 
27             cout<<"No"<<endl;
28         }
29    
30     
31         
32     return 0;
33 }

View Code