博弈之sg函数（模板）

亦凉 2022-08-26 00:41 174阅读 0赞

组合博弈的通解就是sg函数，学习了sg函数之后一直没有咋用过。

学习博弈的可以在nyoj上面做10道取石子题目，作为了对博弈也就有一定理解了。

用的时候注意初始的时候只要初始sg\[0\]=0;

其他都通过函数求解。

这里贴一个求解sg函数的模板。

int sg[N];
    bool hash[N];
    void sg_solve(int *s,int t,int N)   //N求解范围 S[]数组是可以每次取的值，t是s的长度。
    {
        int i,j;
        memset(sg,0,sizeof(sg));
        for(i=1;i<=N;i++)
        {
            memset(hash,0,sizeof(hash));
            for(j=0;j<t;j++)
                if(i - s[j] >= 0)
                    hash[sg[i-s[j]]] = 1;
            for(j=0;j<=N;j++)
                if(!hash[j])
                    break;
            sg[i] = j;
        }
    }

用set容器实现的方法，原理一样。oj上容易超时

void sg_solve()
    {
        memset(sg,0,sizeof(sg));
        for(int i=1;i<N;i++)
        {
            set<int> v;
            for(int j=0;j<t;j++)
                if(i - s[j] >= 0)
                    v.insert(sg[i-s[j]]);
            int g=0;
            while(v.count(g)!=0)
                g++;
            sg[i]=g;
        }
    }

通过一道题目说一下。

hdoj 1536 和pku 2960 S-Nim

题意就是给出一个数组s。为每次可以取石子的数目。

然后给你n堆石子每堆si。求解先手能不能赢！标准的sg函数用法题目。

代码：

#include<stdio.h>
    #include<string.h>
    #include <string>
    #include <iostream>
    using namespace std;
    
    const int N = 10008;
    int s[108],t;
    int sg[N];
    bool hash[N];
    void sg_solve(int *s,int t,int N)   //N求解范围 S[]数组是可以每次取的值，t是s的长度。
    {
        int i,j;
        memset(sg,0,sizeof(sg));
        for(i=1;i<=N;i++)
        {
            memset(hash,0,sizeof(hash));
            for(j=0;j<t;j++)
                if(i - s[j] >= 0)
                    hash[sg[i-s[j]]] = 1;
            for(j=0;j<=N;j++)
                if(!hash[j])
                    break;
            sg[i] = j;
        }
    }
    
    int main()
    {
        int i,j,n,m,h;
        while(scanf("%d",&t),t)
        {
            string ans="";
            for(i=0;i<t;i++)
                scanf("%d",&s[i]);
            sg_solve(s,t,N);
            scanf("%d",&n);
            for(i=0;i<n;i++)
            {
                scanf("%d",&m);
                int res = 0;
                for(j=0;j<m;j++)
                {
                    scanf("%d",&h);
                    res ^= sg[h];
                }
                ans+=res?'W':'L';
            }
            cout<<ans<<endl;
        }
        return 0;
    }