HDU 2311-Nim or not Nim?（Nim博弈-打sg表找规律）

爱被打了一巴掌 2022-07-24 04:07 124阅读 0赞

# Nim or not Nim? #

**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 1493 Accepted Submission(s): 738**

Problem Description

Nim is a two-player mathematic game of strategy in which players take turns removing objects from distinct heaps. On each turn, a player must remove at least one object, and may remove any number of objects provided they all come from the same heap.  
  
Nim is usually played as a misere game, in which the player to take the last object loses. Nim can also be played as a normal play game, which means that the person who makes the last move (i.e., who takes the last object) wins. This is called normal play because most games follow this convention, even though Nim usually does not.  
  
Alice and Bob is tired of playing Nim under the standard rule, so they make a difference by also allowing the player to separate one of the heaps into two smaller ones. That is, each turn the player may either remove any number of objects from a heap or separate a heap into two smaller ones, and the one who takes the last object wins.

Input

Input contains multiple test cases. The first line is an integer 1 ≤ T ≤ 100, the number of test cases. Each case begins with an integer N, indicating the number of the heaps, the next line contains N integers s\[0\], s\[1\], ...., s\[N-1\], representing heaps with s\[0\], s\[1\], ..., s\[N-1\] objects respectively.(1 ≤ N ≤ 10^6, 1 ≤ S\[i\] ≤ 2^31 - 1)

Output

For each test case, output a line which contains either "Alice" or "Bob", which is the winner of this game. Alice will play first. You may asume they never make mistakes.

Sample Input

2
    3
    2 2 3
    2
    3 3

Sample Output

Alice
    Bob

Source

[2009 Multi-University Training Contest 13 - Host by HIT][]

Recommend

gaojie

## 题目意思： ##

两个人从n堆石子中取小石子或者将某一堆石子分成两堆，Alice先手，求谁能赢。

## 解题思路： ##

对sg值打表，根据找出的规律再写代码。  
啊摔！(╯°Д°)╯( ┻━┻)！！一开始木有注意到庞大的数据量，还每次都调用函数求sg，再判断，果断超时超内存。。  
  
先贴AC代码，解释在后面

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #include <algorithm>
    using namespace std;
    
    int main()
    {
        int t,n,i,a,res;
        scanf("%d",&t);
        while(t--)
        {
            res=0;
            scanf("%d",&n);
            for(i=0; i<n; i++)
            {
               cin>>a;
                if(a%4==3) res^=(a+1);
                else if(a%4==0) res^=(a-1);
                else res^=a;
            }
            if(res) cout<<"Alice"<<endl;
            else cout<<"Bob"<<endl;
        }
        return 0;
    }

## 打表函数： ##

n是从1~t，每打完一次n的表就系统暂停一次。当n=1/2/3/4时木有任何规律可循，当n越大，规律就越明显。  
注意一点：sg\[j\]^sg\[i-j\];//是可以分成两堆的情况

#include<iostream>
    #include<cstdio>
    #include<set>
    #include<cstdlib>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    #define MAXN 10000010
    int n;//n堆
    int k;//可取情况的数目
    int x[MAXN];//n堆分别的数目
    int a[MAXN];//可取情况
    int sg[MAXN];//等价于Nim中的石子数
    void init()
    {
        int cnt=0;
        for(int i=0; i<MAXN; ++i)
            a[i]=++cnt;
    }
    void solve()
    {
        int Max=*max_element(x,x+n);
        sg[0]=0;//轮到自己还剩0枚时是必败态
        for(int i=1; i<=Max; ++i)
        {
            set<int>s;//存储当前所能到达状态的sg值
            for(int j=0; j<i; ++j)
                s.insert(sg[j]^sg[i-j]);//可以分成两堆
            for(int j=0; j<i; ++j)
                s.insert(sg[j]);//不分成两堆，直接取
            int cnt=0;//寻找当前状态的最小排斥值
            while(s.count(cnt)!=0)//返回值为cnt的元素个数
                ++cnt;
            sg[i]=cnt;
            cout<<i<<" "<<sg[i]<<endl;
        }
        /*int res=0;
        for(int i=0; i<n; ++i)
            res^=sg[x[i]];
        if(res)puts("Alice");//先手必胜
        else puts("Bob");*/
    }
    
    int main()
    {
        int t;
        scanf("%d",&t);
        init();
        n=1;
        while(t--)
        {
            int cnt=0;
            for(int i=0; i<n; ++i)
                x[i]=++cnt;
            solve();
            ++n;
            system("pause");
        }
        return 0;
    }

![Center][] ![Center 1][]

## 规律如下： ##

sg\[4k+1\]=4k+1

sg\[4k+2\]=4k+2

sg\[4k+3\]=4k+4

sg\[4k+4\]=4k+3

至此，SG值都知道了，就可以XOR求结果判断啦~

[2009 Multi-University Training Contest 13 - Host by HIT]: http://acm.hdu.edu.cn/search.php?field=problem&key=2009+Multi-University+Training+Contest+13+-+Host+by+HIT&source=1&searchmode=source
[Center]: https://img-blog.csdn.net/20160512162058716?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 1]: /images/20220722/4c9c2ed3ed8e4c078aaa84348d489b78.png