hdu 5011 nim博弈变形

约定不等于承诺〃 2022-08-08 14:51 87阅读 0赞

# Game #

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)  
Total Submission(s): 1008    Accepted Submission(s): 657**

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

Source

[2014 ACM/ICPC Asia Regional Xi'an Online ][2014 ACM_ICPC Asia Regional Xi_an Online]

题意：给定n堆石子，每堆石子有ai个，两个人轮流取石子，轮到某个人时，可以选择某一堆，然后取这堆的至少一个石子，取完后可以将这堆石子分成两对，

最后全部取完的人胜利。

分析： 试了好多数据，发现分堆是不影响的，于是就是经典的nim博弈。 因此只要计算XOR异或值，就可以判断胜负。

首先一旦从XOR为零的状态取走至少一颗石子，XOR就一定会变成非零，因此，可以证明必败态只能转移到必胜态。

接下来，我们来证明必胜态总是能转移到某个必败态，观察XOR的二进制表示的最高位的1，选取石子的二进制来表示对应位也为1的某堆石子。只要从中取走使得该位变为0，且其余XOR中的1也反转的数量的石子，XOR就可以变为0。

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    const int N=100010;
    
    ll a[N];
    int main()
    {
        int n;
        while(~scanf("%d",&n))
        {
            ll ans=0;
            for(int i=0;i<n;i++)
            {
                scanf("%I64d",&a[i]);
                ans^=a[i];
            }
            puts(ans==0? "Lose" : "Win");
        }
        return 0;
    }

[2014 ACM_ICPC Asia Regional Xi_an Online]: http://acm.hdu.edu.cn/search.php?field=problem&key=2014+ACM%2FICPC+Asia+Regional+Xi%27an+Online&source=1&searchmode=source