Written by razrlele
10:00 July 29, 2014
Matches Game
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 9306 | Accepted: 5372 |
Description
Here is a simple game. In this game, there are several piles of matches and two players. The two player play in turn. In each turn, one can choose a pile and take away arbitrary number of matches from the pile (Of course the number of matches, which is taken away, cannot be zero and cannot be larger than the number of matches in the chosen pile). If after a player’s turn, there is no match left, the player is the winner. Suppose that the two players are all very clear. Your job is to tell whether the player who plays first can win the game or not.
Input
The input consists of several lines, and in each line there is a test case. At the beginning of a line, there is an integer M (1 <= M <=20), which is the number of piles. Then comes M positive integers, which are not larger than 10000000. These M integers represent the number of matches in each pile.
Output
For each test case, output “Yes” in a single line, if the player who play first will win, otherwise output “No”.
Sample Input
|
1 2 |
2 45 45 3 3 6 9 |
Sample Output
|
1 2 |
No Yes |
Source
POJ Monthly,readchild
这是个典型NIM游戏，
据说该游戏起源于中国，经由当年到美洲打工的华人流传出去。它的英文名字「NIM」是有广东话「拈」（取物之意）音译而来。这个游戏一个常见的变种是将12枚硬币分三列排成[3,4,5]再开始玩。我们这里讨论的是一般意义上的「拈」游戏。－－《编程之美》p71
题目本身大概的意思就是说有M个火柴堆，A和B可以依次先后（按照ABABABABAB的顺序）从任一火柴堆中那出数目大于零且不大于所选择火柴堆的数量的火柴，谁最后一个拿完全部火柴谁就是赢家，然后题目要求判断所给的情况中先动手的即A是否可以取胜。 万万没想到，这个题目要用异或（XOR）来解。 最后取胜的状态XOR（0，0，0，0，0，0，0。。。） = 0，然后再加上两个最关键的结论：
结论一
- 当XOR(M1, M2, …Mn) != 0 时，总是可以通过改变一个Mi的值，就可以让XOR(M1, M2, …Mn) = 0
结论二
- 当XOR(M1, M2, …Mn) = 0 时，任意一个Mi的值的改变，就可以让XOR(M1, M2, …Mn) != 0 也就是说如果一开始XOR(M1, M2, …Mn) = 0，那么先手者肯定会使XOR(M1, M2, …Mn) != 0，后手者无论如何都可以使XOR(M1, M2, …Mn) = 0，如此循环至最终XOR（0，0，0，0，0，0，0。。。） = 0，后手者必赢，所以XOR(M1, M2, …Mn) = 0就是必输局面，相反，如果一开始XOR(M1, M2, …Mn) != 0，那么就是必胜局面。
AC代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
/************************************************************************* > File Name: poj2234.cpp > Author: razrLeLe > Personal homepage: https://razrLeLe.com > Created Time: Mon 28 Jul 2014 06:38:22 PM CST ************************************************************************/ #include using namespace std; int main() { int m, n; int a; while(cin >> m) { a = 0; for(int i = 0; i < m; i++) { cin >> n ; a ^= n; } if(a) cout << "Yes" << endl; else cout << "No" << endl; } } |
短的出翔，但是事实就是如此。。。