AcWing 893：集合-Nim游戏 ← SG函数

​【题目来源】
https://www.acwing.com/problem/content/895/

【题目描述】
给定 n 堆石子以及一个由 k 个不同正整数构成的数字集合 S。
现在有两位玩家轮流操作，每次操作可以从任意一堆石子中拿取石子，每次拿取的石子数量必须包含于集合 S，最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。

【输入格式】
第一行包含整数 k，表示数字集合 S 中数字的个数。
第二行包含 k 个整数，其中第 i 个整数表示数字集合 S 中的第 i 个数 si。
第三行包含整数 n。
第四行包含 n 个整数，其中第 i 个整数表示第 i 堆石子的数量 hi。​​​​​​​

【输出格式】
如果先手方必胜，则输出 Yes。
否则，输出 No。​​​​​​​

【输入样例】
2
2 5
3
2 4 7​​​​​​​

【输出样例】
Yes

【数据范围】
1≤n,k≤100，
1≤si,hi≤10000​​​​​​​

【算法分析】
● SG 函数（Sprague-Grundy）
（1）SG 函数的核心是为每个游戏状态计算一个SG 值。其计算依赖于该状态所有后继状态 SG 值的集合，并取该集合的 mex 值（即不在集合中的最小非负整数）作为当前状态的 SG 值。（显然，SG 值一定是非负整数。）
（2）据上所述，可知对于一个游戏状态 u，其 SG 值 SG(u) 的数学表述为：SG(u)=mex{SG(v)∣v∈Γ(u)}（其中 Γ(u) 表示 u 的后继状态集合）。
例如，已知状态 u 的后继状态为 v1，v2，v3，…，vn，则 SG(u) = mex {SG(v1), SG(v2), SG(v3), …, SG(vn)}。易知，mex{0,1,3}=2。
（3）f 数组：是记忆化数组，用于缓存已计算的 SG 值，避免重复计算，优化时间复杂度。memset(f, -1, sizeof f); 将 f 数组的所有元素初始化为 -1。这里的 -1 是一个标记值，表示该节点的 SG 值尚未被计算。如果已经计算过，就直接返回存储在 f 数组中的值，而不需要重新计算。这对于处理较大的图结构（如题目中的 N=2e3+5）至关重要，能将时间复杂度从指数级降低到线性级。

【算法代码一：No STL set】
注意：代码中的 st 数组，必须是 sg 函数中的局部数组，不能是全局数组。

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

const int N=1e2+5;
const int M=1e4+5;
int a[N],f[M];
int n,m;

int sg(int x) {
    bool st[M]= {false};

    if(f[x]!=-1) return f[x];

    for(int i=0; i<m; i++) {
        int sum=a[i];
        if(x>=sum) st[sg(x-sum)]=1;
    }

    int i=0;
    while(true) {
        if(!st[i]) return f[x]=i;
        i++;
    }
}

int main() {
    cin>>m;
    for(int i=0; i<m; i++) {
        cin>>a[i];
    }

    cin>>n;
    memset(f,-1,sizeof(f));

    int res=0;
    for(int i=0; i<n; i++) {
        int x;
        cin>>x;
        res^=sg(x);
    }

    if(res) printf("Yes");
    else printf("No");

    return 0;
}

/*
in:
8
4 22 12 36 15 14 48 1
10
14 16 21 31 3 14 42 41 21 23

out:
No
*/

【算法代码二：STL set】

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

const int N=1e2+5;
const int M=1e4+5;
int a[N],f[M];
int n,m;

int sg(int x) {
    if(f[x]!=-1) return f[x];
    set<int> s;
    for(int i=0; i<m; i++) {
        int sum=a[i];
        if(x>=sum) s.insert(sg(x-sum));
    }

    for(int i=0;; i++) {
        if(!s.count(i)) return f[x]=i;
    }
}

int main() {
    cin>>m;
    for(int i=0; i<m; i++) {
        cin>>a[i];
    }

    cin>>n;
    memset(f,-1,sizeof(f));

    int res=0;
    for(int i=0; i<n; i++) {
        int x;
        cin>>x;
        res^=sg(x);
    }

    if(res) printf("Yes");
    else printf("No");

    return 0;
}

/*
in:
8
4 22 12 36 15 14 48 1
10
14 16 21 31 3 14 42 41 21 23

out:
No
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/158767991
https://blog.csdn.net/hnjzsyjyj/article/details/158802621
https://www.acwing.com/solution/content/23435/
 

​