「一本通 6.7 例 3」移棋子游戏

形式化题目

给定一个包含 $N$ 个节点、 $M$ 条有向边的有向无环图（DAG），图上有 $K$ 个棋子，初始分别位于指定的节点上（同一个节点上允许多枚棋子，且各棋子移动相互独立）。

两名玩家轮流行动。在每一次行动中，当前玩家任选一枚棋子，沿其所在节点的一条有向出边移动到相邻的后继节点。无法进行任何移动的玩家判负。

假设双方均采取最优策略，判定先手必胜还是先手必败。若先手必胜输出 win，否则输出 lose。

正解

思路

本题是标准的公平组合游戏（Impartial Combinatorial Game，简称 ICG），且游戏在有向无环图上进行，必然在有限步内终止。

每次操作只能移动一枚棋子，且每个棋子的移动规则独立、互不干扰。因此，整个游戏可以看作 $K$ 个独立的单棋子游戏的和（Sum of Games）。根据 Sprague-Grundy 定理（SG 定理）：

终端节点：没有出边的节点无法继续移动，其 SG 值为 $0$ ：
$SG(u) = 0 \quad (\operatorname{out\_degree}(u) = 0)$
一般节点：一个节点的 SG 值等于其所有出边后继节点 SG 值的集合的最小未出现非负整数（ $\operatorname{mex}$ 运算）：
$SG(u) = \operatorname{mex}(\{ SG(v) \mid (u, v) \in E \})$
复合游戏判定：整体游戏的胜负等价于各个棋子所在节点的 SG 值的按位异或和（Nim 和）：
$X = \bigoplus_{i=1}^{K} SG(p_i)$
- 若 $X \neq 0$ ，则先手必胜，输出 win；
- 若 $X = 0$ ，则先手必败，输出 lose。

由于图是有向无环图（DAG），我们可以先对图进行拓扑排序，随后按照拓扑逆序自底向上倒推，依次求出每个节点的 SG 值，最后计算所有棋子初始位置的 SG 异或和即可。

下图展示了样例给出的 DAG 以及逆序推导出的每个节点的 SG 值：

graph LR
    subgraph SG=0
        5["节点 5 (SG=0)"]
        6["节点 6 (SG=0)"]
    end
    subgraph SG=1
        4["节点 4 (SG=1)"]
        3["节点 3 (SG=1)"]
    end
    subgraph SG=2
        1["节点 1 (SG=2)"]
    end
    subgraph SG=0_or_other
        2["节点 2 (SG=0)"]
    end

    2 --> 1
    2 --> 4
    1 --> 4
    1 --> 5
    1 --> 3
    4 --> 5
    3 --> 5
    3 --> 6

以样例为例：

节点 $5, 6$ 没有出边， $SG(5) = SG(6) = 0$ ；
节点 $4$ 只能到达 $5$ ， $SG(4) = \operatorname{mex}(\{0\}) = 1$ ；
节点 $3$ 可以到达 $5, 6$ ， $SG(3) = \operatorname{mex}(\{0\}) = 1$ ；
节点 $1$ 可以到达 $3, 4, 5$ ， $SG(1) = \operatorname{mex}(\{1, 0\}) = 2$ ；
节点 $2$ 可以到达 $1, 4$ ， $SG(2) = \operatorname{mex}(\{2, 1\}) = 0$ 。

初始棋子位于节点 $1, 2, 4, 6$ ，其 SG 异或和为：

SG(1) \oplus SG(2) \oplus SG(4) \oplus SG(6) = 2 \oplus 0 \oplus 1 \oplus 0 = 3 \neq 0

因此先手必胜，输出 win。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-04-18 10:00
# update_at: 2026-04-18 10:00

import sys
from functools import reduce
from operator import xor


def compute_sg(graph: list[list[int]], n: int) -> list[int]:
    """按拓扑逆序计算 DAG 上所有节点的 SG 值。"""
    in_degree = [0] * (n + 1)
    for u in range(1, n + 1):
        for v in graph[u]:
            in_degree[v] += 1

    queue = [u for u in range(1, n + 1) if in_degree[u] == 0]
    topo_order: list[int] = []
    for u in queue:
        topo_order.append(u)
        for v in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)

    sg = [0] * (n + 1)
    for u in reversed(topo_order):
        seen = {sg[v] for v in graph[u]}
        mex = 0
        while mex in seen:
            mex += 1
        sg[u] = mex

    return sg


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m, k = next(data), next(data), next(data)

    graph: list[list[int]] = [[] for _ in range(n + 1)]
    for _ in range(m):
        u, v = next(data), next(data)
        graph[u].append(v)

    pieces = [next(data) for _ in range(k)]

    sg = compute_sg(graph, n)
    nim_sum = reduce(xor, (sg[p] for p in pieces), 0)

    print("win" if nim_sum != 0 else "lose")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 01:19
 * update_at: 2026-10-06 01:19
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2005;
const int MAXM = 6005;

typedef long long ll;

int n, m, k;
int head[MAXN], to[MAXM], nxt[MAXM], edge_cnt; // 链式前向星存图
int in_deg[MAXN];                             // 每个节点的入度，用于拓扑排序
int sg[MAXN];                                 // sg[u] 表示节点 u 的 SG 值
int q[MAXN];                                  // 拓扑排序的手写队列
int piece[MAXN];                              // 每颗棋子的初始位置
bool vis[MAXN];                               // 求 mex 时的标记数组

// 加一条 u -> v 的有向边。
void add_edge(int u, int v) {
    edge_cnt++;
    to[edge_cnt] = v;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
    in_deg[v]++;
}

// 读入图和棋子位置。
void read_input() {
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        add_edge(x, y);
    }
    for (int i = 1; i <= k; i++) {
        cin >> piece[i];
    }
}

// 拓扑排序后按拓扑逆序自底向上计算每个节点的 SG 值。
void solve() {
    // 入度为 0 的节点先进队，这些是 DAG 上没有前驱的节点
    int qhead = 1, qtail = 0;
    for (int i = 1; i <= n; i++) {
        if (in_deg[i] == 0) {
            qtail++;
            q[qtail] = i;
        }
    }
    while (qhead <= qtail) {
        int u = q[qhead];
        qhead++;
        // u 的 SG 值等于其后继 SG 值集合的 mex
        // 求 mex：先标记所有后继的 SG 值，再从小到大找第一个没出现的非负整数
        for (int e = head[u]; e; e = nxt[e]) {
            int v = to[e];
            if (sg[v] < n) {
                vis[sg[v]] = true;
            }
        }
        int mex = 0;
        while (vis[mex]) {
            mex++;
        }
        sg[u] = mex;
        for (int i = 0; i < mex; i++) {
            vis[i] = false; // 只清理实际标记过的范围
        }
        // 把后继的入度减一，减到 0 就入队
        for (int e = head[u]; e; e = nxt[e]) {
            int v = to[e];
            in_deg[v]--;
            if (in_deg[v] == 0) {
                qtail++;
                q[qtail] = v;
            }
        }
    }

    // SG 定理：整体胜负等于所有棋子所在位置 SG 值的异或和
    int xorsum = 0;
    for (int i = 1; i <= k; i++) {
        xorsum ^= sg[piece[i]];
    }
    if (xorsum != 0) {
        cout << "win" << endl;
    } else {
        cout << "lose" << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    solve();

    return 0;
}

复杂度

时间复杂度： $\mathcal{O}(N + M + K)$ 。拓扑排序与遍历每个节点的出边只需 $\mathcal{O}(N + M)$ ，求每个节点 mex 的集合操作总和亦为 $\mathcal{O}(N + M)$ ，最后对 $K$ 个棋子求异或和为 $\mathcal{O}(K)$ 。在 $N \leqslant 2000, M \leqslant 6000$ 范围内可毫秒级完成。
空间复杂度： $\mathcal{O}(N + M)$ 。用于存储图的邻接表、入度、拓扑序列以及每个节点的 SG 值。

总结

DAG 上的无偏博弈：所有有限步终止的公平博弈都可以抽象为 DAG 上的转移问题，每个状态的值由 SG 定理完全刻画。
多棋子独立游戏的和：各棋子独立移动时，状态复合为 Nim 堆的异或和，避开了指数级组合状态空间的直接搜索。
计算顺序：利用 DAG 的拓扑逆序，可以以线性的时间自底向上高效求得每个节点的 SG 值。

「一本通 6.7 例 3」移棋子游戏

目录

形式化题目

正解

思路

代码

复杂度

总结