Game Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 437 Accepted Submission(s): 340
Problem Description Here is a game for two players. The rule of the game is described below:
● In the beginning of the game, there are a lot of piles of beads.
● Players take turns to play. Each turn, player choose a pile i and remove some (at least one) beads from it. Then he could do nothing or split pile i into two piles with a beads and b beads.(a,b > 0 and a + b equals to the number of beads of pile i after removing)
● If after a player’s turn, there is no beads left, the player is the winner.
Suppose that the two players are all very clever and they will use optimal game strategies. Your job is to tell whether the player who plays first can win the game.
Input There are multiple test cases. Please process till EOF.
For each test case, the first line contains a postive integer n(n < 10 5) means there are n piles of beads. The next line contains n postive integer, the i-th postive integer a i(a i < 2 31) means there are a i beads in the i-th pile.
Output For each test case, if the first player can win the game, ouput “Win” and if he can’t, ouput “Lose”
Sample Input
1 1 2 1 1 3 1 2 3
Sample Output
Win Lose Lose
题意： 大家熟知的题意。有许多堆珠子，然后告诉你每堆珠子的数量，接下来就是两个人轮流操作了，每人每轮从任意一堆中拿走至少1个珠子，然后这个人可以对这堆珠子采取两种做法，1、什么事也不做（值当没说），2、将这堆珠子，分成另外两堆不为零的珠子。最后，没有珠子拿的人输，问第一个拿的人是赢了还是输了。
分析： 除了要分堆这个操作外，和原始的Nim是一样滴 但仔细想一下，Nim的规则是谁面对奇异局势谁就会输，如果先手面对奇异局势 不论他怎么取和分都无法让对手再次面对奇异局势。 相反只要他取了石子当前状态就不会再是奇异局势，和分堆是没有关系滴
#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <cstring> using namespace std; int main(){ freopen("in.txt","r",stdin); int n; while(cin>>n){ int sum=0,x; for(int i=1;i<=n;i++){ scanf("%d",&x); sum=sum ^ x; } if(sum) cout<<"Win"<<endl; else cout<<"Lose"<<endl; } return 0; }