「一本通 6.7 例 2」取石子游戏 2

题目描述

有 $2$ 名玩家和 $N$ 堆石子，第 $i$ 堆有 $X_i$ 颗。双方轮流操作，每次选一个非空的堆并从中取走至少 $1$ 颗石子；轮到某人取时已没有石子可取，该人算负。两名玩家都采取最优策略，先手获胜输出 win，后手获胜输出 lose。输入：第一行一个整数 $N$ ；第二行 $N$ 个空格间隔的整数 $X_i$ 。输出：仅一行，win 或 lose。数据范围： $N \leqslant 5 \times 10^4$ ， $1 \leqslant X_i \leqslant 10^5$ 。样例输入 4 与 7 12 9 15，样例输出 win。

思路

这是经典 Nim 博弈，由 Bouton 定理：把 $N$ 堆石子数全部按位异或得到 Nim 和 $S$ ，先手必胜当且仅当 $S \neq 0$ 。原因是 $S \neq 0$ 时总能从最高位有 $1$ 的那一堆取石子把局面一步归零，而 $S = 0$ 时任何取法都会使异或和重新非零，必胜方由此始终把 $S = 0$ 的必败局面留给对手，于是只需一遍异或即可判定。

参考代码

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#!/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-10-01 00:46
# update_at: 2026-10-01 00:46

import sys
from functools import reduce
from operator import xor


def solve() -> None:
    """Nim 博弈：先手必胜当且仅当各堆石子数的异或和不为 0。"""
    data = iter(sys.stdin.buffer.read().split())
    n = int(next(data))
    piles = [int(next(data)) for _ in range(n)]
    nim_sum = reduce(xor, piles)  # Nim 和：把每堆数量按位异或起来
    print("win" if nim_sum 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/**
 * 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:45
 * update_at: 2026-10-06 01:45
 */

#include <cstdio>

typedef long long ll;

ll n;       // 石子堆数
ll x;       // 当前读入的一堆石子数
ll s;       // Nim 和：全部堆数的按位异或

int main() {
    scanf("%lld", &n);
    s = 0;
    for (ll i = 1; i <= n; i++) {
        scanf("%lld", &x);
        s ^= x; // 边读边异或，无需保存每堆数量
    }
    // Bouton 定理：Nim 和不为 0 先手必胜，为 0 先手必败
    if (s != 0)
        printf("win\n");
    else
        printf("lose\n");
    return 0;
}