「一本通 6.7 练习 3」取石子

形式化题目

$N$ 堆石子排成一排，两人轮流（Alice 先手）二选一操作：① 从某堆取走 1 个石子；② 合并任意两堆石子（合成一堆，个数相加）。无法操作者输。判断 Alice 是否有必胜策略。

正解

思路

1. 游戏的不变量与量

石子总数 $s = \sum a_i$ 只被操作①减少 1，被操作②保持不变；
堆数 $n$ 只被操作②减少 1，被操作①保持不变；
因此 $s + n$ 是"总操作量"的度量：每步恰好减少 1。游戏必然在 $s+n$ 步内终止，没有平局循环。

2. 必败态的分类讨论

这题不能套普通 Nim/SG（合并操作把两堆耦合在一起，子游戏不独立），但状态由三个量刻画：大小为 1 的堆数 $k_1$ 、大小为 2 的堆数 $k_2$ 、总数 $s$ 、堆数 $n$ 。对玩法做博弈分析（SG 打表找规律 + 归纳证明）可得：

存在大于 2 的堆时：必败 $\iff$ $k_1$ 为偶数且 $(s+n)$ 为奇数。直觉：大堆可以当"缓冲"灵活调节奇偶，胜负完全由 $k_1$ 与总操作量的奇偶决定。

只有大小 1 和 2 的堆时（无大堆可借用）边界更细：

$k_2 = 0$ （全 1）：必败 $\iff k_1 \equiv 0 \pmod 3$ ；
$k_2 = 1$ ：必败 $\iff k_1 \equiv 0 \pmod 3$ ；
$k_2$ 为奇数且 $k_2 \ge 3$ ：必败 $\iff k_1$ 为偶数；
$k_2$ 为偶数：先手必胜。

这些分支经小数据 SG 打表验证（本题 main.py 的 losing 即该判定的直接实现）。

3. 实现

每组数据用 Counter 统计堆大小频次， $O(n)$ 一次遍历算出 $k_1, k_2, s, n$ 与 max(count)，按上表判定输出 YES/NO。多组数据总复杂度线性。

代码

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 01:22
# update_at: 2026-10-01 01:22

import sys
from collections import Counter


def losing(count: Counter) -> bool:
    """当前局面先手是否必败。k1/k2 = 大小为 1/2 的堆数，n = 堆数，s = 石子总数。"""
    k1, k2 = count[1], count[2]
    n = sum(count.values())
    s = sum(a * c for a, c in count.items())
    if max(count) > 2:  # 有大堆：必败 ⇔ k1 为偶数 且 (s+n) 为奇数
        return k1 % 2 == 0 and (s + n) % 2 == 1
    # 只有 1、2 堆：k2<=1 时看 k1 模 3；k2 为奇数时看 k1 奇偶；k2 为偶数(>=2)时必胜
    return k1 % 3 == 0 if k2 < 2 else k1 % 2 == 0 if k2 % 2 else False


def solve() -> None:
    it = iter(map(int, sys.stdin.buffer.read().split()))
    print('\n'.join(  # 先读 T，再对每组先读 n、后读 n 个数
        "NO" if losing(Counter(next(it) for _ in range(next(it)))) else "YES"
        for _ in range(next(it))))


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/**
 * 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:29
 * update_at: 2026-10-06 01:29
 */
#include <iostream>
using namespace std;

typedef long long ll;

const int MAXN = 55;

ll a[MAXN]; // a[i] 表示第 i 堆石子的数量

// 判断当前局面是否先手必败。
// k1/k2 为大小为 1/2 的堆数，n 为堆数，s 为石子总数，maxv 为最大堆。
bool is_losing(ll k1, ll k2, ll n, ll s, ll maxv) {
    if (maxv > 2) {
        // 存在大于 2 的堆：必败 ⇔ k1 为偶数 且 (s+n) 为奇数。
        return k1 % 2 == 0 && (s + n) % 2 == 1;
    }
    // 只有大小为 1、2 的堆：k2<=1 时看 k1 对 3 取模；
    // k2 为奇数(>=3) 时看 k1 奇偶；k2 为偶数(>=2) 时先手必胜。
    if (k2 < 2) {
        return k1 % 3 == 0;
    }
    if (k2 % 2 == 1) {
        return k1 % 2 == 0;
    }
    return false;
}

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

    int T;
    cin >> T;
    while (T--) {
        ll n;
        cin >> n;
        ll k1 = 0;   // 大小为 1 的堆数
        ll k2 = 0;   // 大小为 2 的堆数
        ll s = 0;    // 石子总数
        ll maxv = 0; // 最大堆的大小
        for (ll i = 1; i <= n; i++) {
            cin >> a[i];
            s += a[i];
            if (a[i] == 1) k1++;
            if (a[i] == 2) k2++;
            if (a[i] > maxv) maxv = a[i];
        }
        // 先手必败输出 NO，否则输出 YES（Alice 先手）。
        if (is_losing(k1, k2, n, s, maxv)) {
            cout << "NO\n";
        } else {
            cout << "YES\n";
        }
    }
    return 0;
}

复杂度

时间复杂度： $O(\sum N)$ ，每堆只统计一次，判定 $O(1)$ 。
空间复杂度： $O(n)$ 存堆大小频次表。

总结

「取 1 或合并」的博弈没有子游戏独立性，不能直接上 SG 定理；正确路径是小数据打表找规律 + 奇偶/模 3 不变量归纳证明。
$s+n$ 每步恰减 1 的观察是分析基础：游戏长度确定，奇偶性成为核心判据。
$k_1$ （大小 1 堆数）是另一个核心：它既是"可单取"的资源，又控制合并操作的节奏。