G60 有向图游戏 SG函数【博弈论】

视频程序会超时：

#include <bits/stdc++.h>
using namespace std;

const int N = 1005, M = 10005;
int n, m, x;
int a[N], f[M];

int sg(int x)
{
    // 记忆化搜索
    if (f[x] != -1)
        return f[x];
    // 把子节点的sg值插入集合
    set<int> S;
    for (int i = 0; i < m; i++)
        if (x >= a[i])
            S.insert(sg(x - a[i]));
    // mex运算求当前节点的sg值并记忆
    for (int i = 0;; i++)
        if (!S.count(i))
            return f[x] = i;
}
int main()
{
    while(cin >> m , m)
    {
        for (int i = 0; i < m; i++) cin >> a[i];
        int t;cin >> t;
        while (t--)
        {
            cin >> n;
            memset(f, -1, sizeof f);
            int res = 0;
            for (int i = 0; i < n; i++)
                cin >> x, res ^= sg(x);
            if (res) printf("W");
            else printf("L");
        }
        printf("\n");
    }
    return 0;
}

标程：

#include<bits/stdc++.h>
using namespace std;
int sg[11000],k[110],re[110];
bool v[11000];
int main()
{
    int K;
    while(scanf("%d",&K)!=EOF&&K)
    {
        memset(v,true,sizeof(v));
        for(int i=1;i<=K;i++)scanf("%d",&k[i]);
        memset(sg,0,sizeof(sg));
        for(int i=1;i<=10000;i++)
        {
            for(int j=1;j<=K;j++)if(k[j]<=i)
            {
                v[sg[i-k[j]]]=false;
            }
            for(int j=0;j<=10000;j++)
            {
                if(v[j])
                {
                    sg[i]=j;
                    break;
                }
            }
            for(int j=1;j<=K;j++)if(k[j]<=i)
            {
                v[sg[i-k[j]]]=true;
            }
        }
        int T;scanf("%d",&T);
        for(int t=1;t<=T;t++)
        {
            int n,ans=0,x;scanf("%d",&n);
            for(int i=1;i<=n;i++)scanf("%d",&x),ans^=sg[x];
            re[t]=ans;
        }
        for(int t=1;t<=T;t++)
        {
            if(re[t]==0)printf("L");
            else printf("W");
        }
        printf("\n");
    }
    return 0;
}