AcWing 1319：移棋子游戏 ← SG函数模板题
【题目来源】
【题目描述】
给定一个有 N 个节点的有向无环图，图中某些节点上有棋子，两名玩家交替移动棋子。
玩家每一步可将任意一颗棋子沿一条有向边移动到另一个点，无法移动者输掉游戏。
对于给定的图和棋子初始位置，双方都会采取最优的行动，询问先手必胜还是先手必败。
【输入格式】
第一行，三个整数 N，M，K，N 表示图中节点总数，M 表示图中边的条数，K 表示棋子的个数。
接下来 M 行，每行两个整数 X，Y 表示有一条边从点 X 出发指向点 Y。
接下来一行， K 个空格间隔的整数，表示初始时，棋子所在的节点编号。
节点编号从 1 到 N。
【输出格式】
若先手胜，输出 win，否则输出 lose。
【输入样例】
6 8 4
2 1
2 4
1 4
1 5
4 5
1 3
3 5
3 6
1 2 4 6
【输出样例】
win
【数据范围】
1≤N≤2000，
1≤M≤6000，
1≤K≤N
【算法分析】
● 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）至关重要，能将时间复杂度从指数级降低到线性级。
（4）本题中，每个节点 u 表示一个游戏状态，由 u 可达的所有结点 v 构成其后继状态集合。结点 u 的 SG 值，定义为其后继状态 SG 值集合的 mex 值，即从 0 开始的最小未出现非负整数。
// 计算节点 u 的 SG 值（Sprague-Grundy 函数）
// 核心作用：求解有向无环图（DAG）上组合游戏的胜负判定关键值
int sg(int u) {
// 1. 定义布尔数组 st，用于标记「当前节点 u 的后继节点」的 SG 值是否出现过
// st[t] = true 表示：值为 t 的 SG 值在后继节点中出现过
// 数组大小 N 是全局定义的节点最大数量（如 2e3+5），初始化为 false
bool st[N]= {false};
// 2. 记忆化剪枝：如果节点 u 的 SG 值已经计算过，直接返回（避免重复递归）
// f[u] 是全局数组，初始值为 -1（表示未计算），计算后存储最终 SG 值
if(f[u]!=-1) return f[u];
// 3. 遍历节点 u 的所有出边（链式前向星遍历邻接表）
// h[u]：节点 u 的邻接表头指针；i!=-1：遍历到邻接表末尾为止
for(int i=h[u]; i!=-1; i=ne[i]) {
// j 是节点 u 的后继节点（从 u 可以走到 j）
int j=e[i];
// 递归计算后继节点 j 的 SG 值，并赋值给 t
int t=sg(j);
// 标记 t 这个 SG 值已经出现过（后续求 mex 时会排除）
st[t]=true;
}
// 4. 求 mex 值（最小排除值）：找到最小的、未被标记的非负整数
// mex 是 SG 函数的核心，规则是「最小的不在后继 SG 值集合中的非负整数」
int i=0;
// 从 0 开始遍历，找到第一个 st[i] 为 false 的值（即未出现的 SG 值）
while(st[i]) i++;
// 5. 记录节点 u 的 SG 值，并存储到全局数组 f 中（记忆化）
f[u]=i;
// 6. 返回节点 u 的最终 SG 值
return f[u];
}
（5）最终，SG 值作为状态的 “特征值”，用于判断该状态是必胜态（SG 值 ≠ 0）还是必败态（SG 值 = 0）。
● SG 定理（Sprague-Grundy Theorem）
任何无偏博弈都可以等价转换为一个 Nim 堆，其大小等于该博弈状态的 SG 值。
● 针对普通的 Nim 博弈而言，每个堆的 SG 值就是 ai 本身。若 SG(a1)⊕SG(a2)⊕⋯⊕SG(an)≠0，先手必胜。若 SG(a1)⊕SG(a2)⊕⋯⊕SG(an)=0，先手必败。其中，a1, a2, …, an，分别为 n 堆石子的数量。
● 必胜态（N-position）& 必败态（P-position）
必胜态（N-position）：当前玩家存在至少一种行动，可以使对手进入必败态。其 SG 值不为 0。
必败态（P-position）：当前玩家无论采取什么行动，都无法避免失败的状态。其 SG 值为 0。
多个独立游戏的组合胜负，由各游戏 SG 值的异或和决定。异或和非零则先手胜，否则先手败。
【算法代码】
#include <bits/stdc++.h>
using namespace std;
const int N=2e3+5;
const int M=6e3+5;
int e[M],ne[M],h[N],idx;
int f[N];
int n,m,k;
void add(int a,int b) {
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int sg(int u) {
bool st[N]= {false};
if(f[u]!=-1) return f[u];
for(int i=h[u]; i!=-1; i=ne[i]) {
int j=e[i];
int t=sg(j);
st[t]=true;
}
int i=0;
while(st[i]) i++;
f[u]=i;
return f[u];
}
int main() {
memset(h,-1,sizeof h);
memset(f,-1,sizeof f);
scanf("%d%d%d",&n,&m,&k);
while(m--) {
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
}
int ans=0;
while(k--) {
int x;
scanf("%d",&x);
ans^=sg(x);
}
if(ans) printf("win\n");
else printf("lose\n");
return 0;
}
/*
in:
6 8 4
2 1
2 4
1 4
1 5
4 5
1 3
3 5
3 6
1 2 4 6
out:
win
*/
【参考文献】
浙公网安备 33010602011771号