首页 > 代码库 > HDU - 1851 - A Simple Game

HDU - 1851 - A Simple Game

2024-07-15 14:13:33   220人阅读

先上题目：

A Simple Game

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/65535 K (Java/Others)
Total Submission(s): 1104    Accepted Submission(s): 686


Problem Description
Agrael likes play a simple game with his friend Animal during the classes. In this Game there are n piles of stones numbered from 1 to n, the 1st pile has M1 stones, the 2nd pile has M2 stones, ... and the n-th pile contain Mn stones. Agrael and Animal take turns to move and in each move each of the players can take at most L1stones from the 1st pile or take at most L2 stones from the 2nd pile or ... or take Ln stones from the n-th pile. The player who takes the last stone wins.

After Agrael and Animal have played the game for months, the teacher finally got angry and decided to punish them. But when he knows the rule of the game, he is so interested in this game that he asks Agrael to play the game with him and if Agrael wins, he won‘t be punished, can Agrael win the game if the teacher and Agrael both take the best move in their turn?

The teacher always moves first(-_-), and in each turn a player must takes at least 1 stones and they can‘t take stones from more than one piles.
 

 

Input
The first line contains the number of test cases. Each test cases begin with the number n (n ≤ 10), represent there are n piles. Then there are n lines follows, the i-th line contains two numbers Mi and Li (20 ≥ Mi > 0, 20 ≥ Li > 0). 
 

 

Output
Your program output one line per case, if Agrael can win the game print "Yes", else print "No". 
 

 

Sample Input
2
1
5 4
2
1 1
2 2
 
 
Sample Output
Yes
No
 
　　题意：老师和学生玩游戏，游戏是这样的：n堆石头，每堆石头有mi个石子，每堆石头每次最多只能取li个石子，每次一定要取且只可以取某一堆的石子，老师先开始取，两个足够聪明，问学生能不能赢？
　　问题相当于问后手能不能赢，对于这个游戏来说，只需要对每一堆石子都求一次巴什博奕，然后将结果异或，如果结果等于零就学生赢，否则就是老师赢。为什么这里只需要将所有堆的结果异或就可以得到结果呢？我认为这里的原因在于每一堆石子都是相对独立的，它们的变化互不影响，同时对于而对于总体来说它们又是一个大的Nim模型里面的石子，所以可以这样解决。其实过于这一点，我还不是很理解，所以说的可能不是很正确，如果读者有自己的想法的可以留言，大家探讨一下。
 
上代码：
 
 1 #include <iostream> 2 using namespace std; 3  4 int main() 5 { 6     int t,n,x,y,ans; 7     ios::sync_with_stdio(false); 8     cin>>t; 9     while(t--){10         cin>>n;11         ans=0;12         for(int i=0;i<n;i++){13             cin>>x>>y;14             ans^=(x%(y+1));15         }16         if(ans) cout<<"No"<<endl;17         else cout<<"Yes"<<endl;18     }19     return 0;20 }
/*1851*/

 

 


联系
我们