ICG 最忌讳的就是在状态里区分 Alice 和 Bob。既然是 ICG，胜败只与局面有关，不应当区分玩家。

hdu summer 05 - 1006 支配游戏

两个玩家在一张无向图上进行博弈，任意两个节点之间最多一条边相连。这张图由若干个 互不相交的连通块 组成，每个连通块要么是一条 简单路径 （记为 1），要么是一个 简单环。
在游戏中，两个玩家轮流行动。在每一轮中，当前玩家必须选择一个顶点 u，该顶点需能 支配 至少一个 未被支配 的顶点，注意，该顶点并不要求是未被支配的。一个顶点 u 能够支配它自己以及所有与它相邻的顶点。
当某个顶点被选中后，它以及所有被其支配的顶点都会被标记为 已支配。
若某位玩家在其回合无法进行操作（即没有可以支配未被支配顶点的顶点可选），则该玩家输掉游戏。
判断在双方都采取最优策略的前提下，先手玩家是否必胜。

设 sg[n][i]sg[n][i] 为长度为 nn 且所有节点都没有被选择的链的两端有 ii 个已经被支配。
打表枚举选择每个点支配取 sgsg 。
长度为 nn 的环 sgsg 值为 bool(!sg[n - 1][2])。

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
// 打表
int sg[100][3]; //
sg[0][0] = 0;
sg[0][1] = 0;
sg[0][2] = 0;
sg[1][0] = 1; //
sg[1][1] = 0;
sg[1][2] = 0;
sg[2][0] = 1;
sg[2][1] = 1;
sg[2][2] = 0;
for (int i = 3; i < 100; i++) {
    for (int j = 0; j < 3; j++) {
        if (j == 0) { // kong
            set<int> st;
            for (int k = 0;  k < i; k++) {
                int kk = i - k - 1;
                st.insert(sg[k][1] ^ sg[kk][1]);
            }
            int cnt = 0;
            for (auto x : st) {
                if (x == cnt) {
                    cnt++;
                } else {
                    sg[i][0] = cnt;
                    break;
                }
            }
            sg[i][0] = cnt;
        } else if (j == 1) { // dan
            set<int> st;
            for (int k = 0; k < i; k++) {
                int kk = i - k - 1;
                st.insert(sg[k][2] ^ sg[kk][1]);
            }
            int cnt = 0;
            for (auto x : st) {
                if (x == cnt) {
                    cnt++;
                } else {
                    sg[i][1] = cnt;
                    break;
                }
            }
            sg[i][1] = cnt;

        } else { // shuang
            set<int> st;
            for (int k = 0; k < i; k++) {
                int kk = i - k - 1;
                st.insert(sg[k][2] ^ sg[kk][2]);
            }
            int cnt = 0;
            for (auto x : st) {
                if (x == cnt) {
                    cnt++;
                } else {
                    sg[i][2] = cnt;
                    break;
                }
            }
            sg[i][2] = cnt;
        }
    }
}
for (int i = 0; i < 100; i++) {
    cout << "sg[" << i << "][0] = " << sg[i][0] 
         << ", sg[" << i << "][1] = " << sg[i][1] 
         << ", sg[" << i << "][2] = " << sg[i][2] << endl;
}
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
// 解
int n;
cin >> n;
int sg = 0;
for (int i = 0; i < n; i++) {
    int x, num;
    cin >> x >> num;
    if (num == 0) { // 环
        int y = (x + 1) % 4;
        if (y) sg ^= 0;
        else sg ^= 1;
    } else { // 链
        if (x == 1 || x == 2 ) {
            sg ^= 1;
        } else if (x == 3) {
            sg ^= 2;
        } else {
            if (x % 4 == 0) {
                sg ^= 0;
            } else if (x % 4 == 1) {
                sg ^= 1;
            } else if (x % 4 == 2) {
                sg ^= 1;
            } else if (x % 4 == 3) {
                sg ^= 3;
            }
        }
    }
}
if (sg) {
    cout << "Yes" << endl;
} else {
    cout << "No" << endl;
}

2025 CCPC Online F（SG，Hash）

  • 圆周上 NN 个点，初始给定 MM 条弦，保证所有弦的所有端点互不相同。
  • ICG，每次操作选择两个未被使用过的点连成一条弦，新弦不得与任何已有弦相交，无法进行合法操作的一方判负。
  • 判断先手是否必胜。

博弈部分是 SG 打表。

为找到初始棋盘的子游戏大小，可以用一些数据结构精确维护。此外有随机化方法 XOR-Hash：对圆环用随机数 Hash 染色，颜色（即异或值）相同的在一个子游戏中。（这个 trick 在 CF Div3 中经常出现，如 CF1996G. Penacony：给定 nn 个点、nn 条双向边的环。有 mm 对点对 ai,bia_i,b_i，要求删掉尽可能多的边，使得删完后，每对 ai,bia_i,b_i 仍联通。求出剩余边数的最小值。）

赛时写了个离散化丑爆了，打 map 就行。复杂度 1log。

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define endl '\n'

int _sg[5000]; // nim 和不为 0 先手必胜

ll sg(ll x) { 
    int t = (x - 100) / 34;
    t = max(t, 0);
    return _sg[x - (t * 34)];
}

mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

void eachT() {   
    int n, m;
    cin >> n >> m;

    map<int, ull> diff;
    while (m--) {
        int l, r;
        cin >> l >> r;
        auto x = rnd();
        diff[l] ^= x;
        diff[r] ^= x;
    }
    map<ull, int> lens;
    int lst = -1;
    ull pre = 0;
    diff[n] = 0;
    for (auto& [x, val] : diff) {
        lens[pre] += x - lst - 1;
        pre ^= val;
        lst = x;
    }
    int ans = 0;
    for (auto& [_, x] : lens) {
        ans ^= sg(x);
    }
    if (ans) cout << "YES" << endl;
    else cout << "NO" << endl;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    for (int i = 1; i <= 200; i++) {
        _sg[i] = -1;
    }
    _sg[0] = 0;
    _sg[1] = 0;
    _sg[2] = 1;
    _sg[3] = 1;
    for (int x = 2; x <= 200; x++) {
        set<int> st;
        for (int i = 0; i <= x - 2; i++) {
            int j = x - i - 2;
            st.insert(_sg[i] ^ _sg[j]);
        }
        int mex = 0;
        for (auto s : st) {
            if (s == mex) mex++;
            else {
                _sg[x] = mex;
                break;
            }
        }
        _sg[x] = mex;
    }

    // for (int x = 0; x <= 200; x++) {
    //     assert(_sg[x] == sg(x));
    // }

    // for (int i = 0; i <= 500; i++) {
    //     // cout << "sg[" << i << "] == " << sg[i] << endl;
    //     cout << sg(i) << " ";
    //     if (i % 34 == 33) {
    //         cout << "\n";
    //     }
    // }
    
    int t;
    cin >> t;

    while (t--) {
        eachT();
    }

    return 0;
}

/*
0 0 1 1 2 0 3 1 1 0 3 3 2 2 4 0 5 2 2 3 3 0 1 1 3 0 2 1 1 0 4 5 2 7 
4 0 1 1 2 0 3 1 1 0 3 3 2 2 4 4 5 5 2 3 3 0 1 1 3 0 2 1 1 0 4 5 3 7
4 8 1 1 2 0 3 1 1 0 3 3 2 2 4 4 5 5 9 3 3 0 1 1 3 0 2 1 1 0 4 5 3 7
4 8 1 1 2 0 3 1 1 0 3 3 2 2 4 4 5 5 9 3 3 0 1 1 3 0 2 1 1 0 4 5 3 7
4 8 1 1 2 0 3 1 1 0 3 3 2 2 4 4 5 5 9 3 3 0 1 1 3 0 2 1 1 0 4 5 3 7
4 8 1 1 2 0 3 1 1 0 3 3 2 2 4 4 5 5 9 3 3 0 1 1 3 0 2 1 1 0 4 5 3 7
4 8 1 1 2 0 3 1 1 0 3 3 2 2 4 4 5 5 9 3 3 0 1 1 3 0 2 1 1 0 4 5 3 7
*/

2026 ICPC 深圳邀请赛 F. Astra

  • 给定一棵包含 NN 个节点的树和一个常数 KK，初始仅有节点 ss 被标记。
  • ICG，每次选择长度为 pp （1≤p≤K1 \le p \le K）的未被标记的简单链 a1,a2,⋯ ,apa_1, a_2, \cdots, a_p，满足 a1a_1 必须与某个已标记的节点相邻，将这 pp 个节点设为已标记状态。
  • 标记到树上最后一个节点的玩家获胜。
  • 对于每一个起始节点 s∈[1,N]s \in [1, N]，分别判断先手是否必胜。

每条边将树化为两棵子树，共计 O(N)\mathcal{O}(N) 个子树。每个子树是一个子游戏，有一个 SG 值，大子树的 SG 值可以用小子树的 SG 值得到，枚举 O(N)\mathcal{O}(N) 条可能的路径。