非递归求SG函数的优化（从hdu1536 S-Nim谈起）

曾经终败给现在 2021-09-15 21:18 234阅读 0赞

求SG函数一般有递归和非递归两种写法，我们先来看看一般递归求SG函数的写法

#include <cstring>
    #include <cmath>
    #include <algorithm>
    #include <queue>
    #include <iostream>
    #include <cstdio>
    using namespace std;
    int sg[10005];
    int f[110];
    void getsg(int n)
    {
        int i,j;
        memset(sg,0,sizeof(sg));
        int hash1[10005];
        for(i=0; i<10005; i++)
        {
            memset(hash1,0,sizeof(hash1));
            for(j=0; j<n; j++)
            {
                if(i-f[j]>=0)
                    hash1[sg[i-f[j]]]=1;
            }
            for(j=0; j<10005; j++)
            {
                if(!hash1[j])
                {
                    sg[i]=j;
                    break;
                }
            }
        }
        return ;
    }
    int main()
    {
        int n;
        while(scanf("%d",&n)!=EOF&&n!=0)
        {
            for(int i=0; i<n; i++)
                scanf("%d",&f[i]);
            sort(f,f+n);
            getsg(n);
            int m;
    // for(int i=0; i<1000; i++)
    // cout<<sg[i]<<" ";
            scanf("%d",&m);
            for(int i=0; i<m; i++)
            {
                int t;
                int pp;
                int res=0;
                scanf("%d",&t);
                for(int j=0; j<t; j++)
                {
                    scanf("%d",&pp);
                    res=res^sg[pp];
                }
                if(res==0)
                    printf("L");
                else
                    printf("W");
            }
            printf("\n");
        }
        return 0;
    }

这是一份在hdu1536上的discuss板块上的**超时**代码，我们可以看看它在getsg()  
函数里面每进行一次循环就memset一次，时间复杂度为n^2

for(i=0; i<10005; i++)
        {
            memset(hash1,0,sizeof(hash1));//这里
            for(j=0; j<n; j++)
            {
                if(i-f[j]>=0)
                    hash1[sg[i-f[j]]]=1;
            }
            for(j=0; j<10005; j++)
            {
                if(!hash1[j])
                {
                    sg[i]=j;
                    break;
                }
            }
        }

那么我们可不可以将这个memset去掉呢？看看下面的代码

#include <bits/stdc++.h>
    using namespace std;
    #define rep(i,a,n) for (int i=a;i<n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define pb push_back
    #define mp make_pair
    #define all(x) (x).begin(),(x).end()
    #define fi first
    #define se second
    #define SZ(x) ((int)(x).size())
    typedef vector<int> VI;
    typedef long long ll;
    typedef pair<int,int> PII;
    const ll mod=1000000007;
    ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){
       if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
    // head//
    
    const int maxn = 10100;
    const int N = 110;
    int SG[maxn],f[N],s[maxn];
    
    int k,n,m,t;
    
    void getsg(int n,int nn)
    {
        SG[0] = 0;
        int tt = 0;
        for(int i = 1;i<=10000;i++)
        {
            tt++;
            //memset(s,0,sizeof s);
            for(int j = 0;f[j]<=i&&j<nn;j++)
            {
                s[SG[i-f[j]]] = tt;
            }
            for(int j = 0;;j++)
                if(s[j]!=tt)
            {
                SG[i] = j;
                break;
            }
        }
    }
    
    int main()
    {
        while(scanf("%d",&k)!=EOF&&k)
        {
            for(int i =0;i<k;i++)
                scanf("%d",&f[i]);
            sort(f,f+k);
            scanf("%d",&n);
            getsg(10000,k);
            for(int i = 0;i<n;i++)
            {
                int ans = 0;
                scanf("%d",&m);
                for(int i = 0;i<m;i++)
                    {
                        scanf("%d",&t);
                        ans^=SG[t];
                    }
                    if(ans)
                        cout<<"W";
                    else
                        cout<<"L";
            }
    
            cout<<endl;
        }
    }

我们之所以每一次循环都memset是为了将**上一状态的后继集合清零**，那么我们想要去掉memset要考虑的就是让每次循环既能不与上一状态有**冲突**，又能保存状态。  
这个时候我们让可以将它匹配的值不是1(true)，而是一个**递增**的值,这样我们就可以避免冲突，而且减少它的复杂度

*如有错误请及时联系本人*