Nim游戏（一堆/N堆）-博弈

分手后的思念是犯贱 2022-08-22 03:56 185阅读 0赞

## 问题一： ##

Alice和Bob在玩这样一个游戏：给定k个数字a1，a2…ak。一开始，有x个石子，Alice和Bob轮流取石子。每次所取石子的个数一定要在a1~ak中。Alice先取。取走最后一个石子的一方获胜。当双方都采取最优策略时，谁会获胜？题目假定a1~ak中一定有1.

可以看成一堆的Nim游戏。

#include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    #define MAXN 1010
    int x,k,a[MAXN];
    bool sg[MAXN];
    void solve()
    {
        sg[0]=false;
        for(int j=1; j<=x; ++j)
        {
            sg[j]=false;
            for(int i=0; a[i]<=j&&i<k; ++i)
                if(!sg[j-a[i]])
                    sg[j]|=!sg[j-a[i]];
        }//a|=b的意思就是把a和b按位或然后赋值给a
        if(sg[x]) puts("Alice");//先手必胜
        else puts("Bob");
    }
    
    int main()
    {
        cin>>x>>k;
        for(int i=0; i<k; ++i)
            cin>>a[i];
        solve();
        return 0;
    }
    /*
    9
    2
    1 4
    */

## 问题二： ##

Alice和Bob在玩这样一个游戏：给定k个数字a1，a2…ak。一开始，有n堆石子，每堆各有xi个石子。Alice和Bob轮流从其中某一堆取一些石子。每次所取石子的个数一定要在a1~ak中。Alice先取。取光石子的一方获胜。当双方都采取最优策略时，谁会获胜？题目假定a1~ak中一定有1.

可以看成N堆的Nim游戏。

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