形式化题目

在一条从左到右编号 $1,2,3,\dots$ 的格子带上放着 $N$ 个棋子，任何两个棋子不同格。两名玩家轮流操作：选择一个棋子向左移动至少一格，移动后不得越过任何其他棋子，也不得越过左边界（即不能到 1 号格左侧），且每格最多一个棋子。无法移动任何棋子的玩家输。双方均采取最优策略，先手者是否必胜？

正解

思路

第一步：把棋盘切成"间隙"。 把棋子按位置从左到右排序，记位置为 $p_0 < p_1 < \dots < p_{n-1}$。棋子的实际布局完全由 $n$ 个间隙决定：

• 第 $0$ 个棋子左边能自由移动的空间 $g_0 = p_0 - 1$（左边界是 1 号格的左侧）；
• 第 $i$ 个棋子与左邻棋子之间的空格数 $g_i = p_i - p_{i-1} - 1$（$i \geqslant 1$）。

向左移动第 $i$ 个棋子 $d$ 格，效果是：$g_i$ 减少 $d$，同时它的右邻间隙（第 $i+1$ 个棋子左边的空隙）增加 $d$；移动最右棋子时右侧没有棋子，等于把这 $d$ 个"空格"扔出游戏。所以这个游戏是从右往左搬运石子的博弈。

第二步：翻个方向，变成阶梯博弈。 想象石子（空格）受重力从右往左流：把最右棋子右侧的空隙与棋子间空隙重新编号，第 $1$ 段在最右边（石子流出即消失），每次操作是"任选第 $j \geqslant 1$ 段，把若干颗石子从第 $j$ 段搬进第 $j-1$ 段"。这正是经典的阶梯博弈（staircase Nim）：

第 $1, 3, 5, \dots$ 段（从右数奇数段）石子数的异或和 $P = s_1 \oplus s_3 \oplus s_5 \oplus \cdots$，若 $P \neq 0$ 则先手必胜，$P = 0$ 则先手必败。

证明分三步（把操作后棋子全挤到最左、所有间隙为 0 的局面记为终局，终局 $P=0$）：

1. $P \neq 0$ 时先手能把它变成 $0$。 标准 Nim 论证给出一个奇数段 $s_j$，减少若干颗后 $P$ 变 $0$：
   • 如果"减少"合法（通常就是这种情况），直接照做；
   • 如果那个奇数段必须增加才行，就取最靠右的可增奇数段 $s_j$（$j \geqslant 3$），把 $d$ 颗石子从 $s_j$ 搬进它的右邻——第 $j-1$ 段。第 $j-1$ 段是偶数段，不参与异或，所以 $P$ 同样变成 $0$；而 $d$ 颗石子的来源不成问题，因为 $s_j$ 右侧更靠右的奇数段里必有可减的段。
2. $P = 0$ 时任何一步都会让 $P \neq 0$。 动奇数段，奇数段异或和改变；动偶数段 $s_j$，是把石子送进奇数段 $s_{j-1}$，同样改变奇数段异或和。
3. 于是 $P \neq 0$ 的局面总能一步走到 $P = 0$，且终局 $P = 0$，故 $P \neq 0$ 当且仅当先手必胜。

回到本题：从右往左数，处于第 $1, 3, 5, \dots$ 位的棋子左侧间隙对应"奇数段"。实现上就是把排序后的间隙数组从右往左隔一个取一个做异或。

用样例二 $\{1,5,6,7,9,12,14,17\}$ 验证：间隙 $[0, 3, 0, 0, 1, 2, 1, 2]$，从右数奇数段是 $2, 2, 1, 0$，异或和 $2 \oplus 2 \oplus 1 = 1 \neq 0$，Georgia（先手）必胜，与样例一致。而样例一 $\{1,2,3\}$ 的间隙为 $[0,0,0]$，异或和为 $0$，Bob 必胜。

:::tip 方向搞反会怎样 如果错误地从左往右取奇数段（即取 $g_0, g_2, \dots$），结论方向恰好相反。真实数据里 “5 4 3 2 1” 这一组（$g = [4,0,0,0,0]$）就能暴露这一错误：从右取异或和为 $0$，Bob 必胜；取错方向会输出 Georgia。最左棋子的左界是 1 号格左侧，所以 $g_0 = p_0 - 1$ 而不是 $p_0$，这一点同样要小心。 :::

代码

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#!/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-09-28 21:30
# update_at: 2026-09-28 21:30

import sys


def nim_xor(gaps: list[int]) -> int:
    """奇数位间隔（从最右棋子数起第 1、3、5……段）的异或和：0 表示先手必败。"""
    xor_sum = 0
    for i in range(len(gaps) - 1, -1, -2):  # 从右往左，隔一个取一个
        xor_sum ^= gaps[i]
    return xor_sum


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    T = next(data)

    for _ in range(T):
        n = next(data)
        pos = sorted(next(data) for _ in range(n))  # 按网格编号从左到右排列

        # gaps[i] = 第 i 个棋子左边可自由移动的空间，最左棋子以 1 号格为左界
        gaps = [pos[0] - 1] + [pos[i] - pos[i - 1] - 1 for i in range(1, n)]

        # 阶梯 Nim：动第 0、2、4……段（从右数奇数段）等价于取石子堆，
        # 动其余段总能被对手镜像回去，所以只看奇数段异或和
        winner = "Georgia will win" if nim_xor(gaps) else "Bob will win"
        out.append(winner)

    print("\n".join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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 18:57
 * update_at: 2026-10-06 18:57
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;

typedef long long ll;

ll T;
ll n;
ll pos[MAXN]; // pos[i]：第 i 个棋子所在的网格编号，排序后从左到右

void solve() {
    cin >> T;
    while (T--) {
        cin >> n;
        for (ll i = 1; i <= n; i++) {
            cin >> pos[i];
        }
        sort(pos + 1, pos + n + 1);

        // 把棋子间的空格看成沿阶梯从右往左流动的石子：
        // gap[i] = 第 i 个棋子左边可自由移动的空格数，最左棋子以 1 号格左侧为界。
        // 从右往左数第 1、3、5……段参与 Nim 异或，这里直接从最右棋子隔一个取一个。
        ll nim_sum = 0;
        for (ll i = n; i >= 1; i -= 2) {
            if (i == 1) {
                nim_sum ^= pos[i] - 1;
            } else {
                nim_sum ^= pos[i] - pos[i - 1] - 1;
            }
        }

        if (nim_sum != 0) {
            cout << "Georgia will win\n";
        } else {
            cout << "Bob will win\n";
        }
    }
}

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

    solve();

    return 0;
}

复杂度

每组数据排序 $O(n \log n)$，异或 $O(n)$；总计 $O\!\left(\sum n \log n\right)$，$n \leqslant 1000$、$T \leqslant 20$，空间 $O(n)$，远低于限制。

图示解析

阶梯重编号示意图

下图把样例二 $\{1,5,6,7,9,12,14,17\}$ 的间隙按"石子从右往左流"的方向重新编号，标出哪些段参与异或：

flowchart LR
    G0["g0=0<br/>第8段"] --> G1["g1=3<br/>第7段"]
    G1 --> G2["g2=0<br/>第6段"] --> G3["g3=0<br/>第5段 ⭐"]
    G3 --> G4["g4=1<br/>第4段"] --> G5["g5=2<br/>第3段 ⭐"]
    G5 --> G6["g6=1<br/>第2段"] --> G7["g7=2<br/>第1段 ⭐"]
    G7 --> OUT["流出游戏"]

棋子越靠右，其左侧间隙的"阶梯编号"越小；标 ⭐ 的第 1、3、5 段是参与 Nim 异或的奇数段。观察重点：向左移动任何一个棋子，都恰好是"某段减 $d$、右邻段加 $d$"，与阶梯搬石子一一对应；最右棋子的移动则把石子直接送出游戏。

样例一推演

$\{1,2,3\}$ 的三个间隙全为 $0$：

奇数段异或和 $0 \oplus 0 = 0$，先手必败。直观理解：先手随便动一个棋子，后手都能把等量的空隙"还"回去（或继续向左推最右棋子），直到所有棋子贴到左边界，先手无棋可动。

总结

• 关键转化：排序后用相邻间隙描述局面，移动棋子 = 石子沿阶梯向左搬一段。
• 阶梯博弈：从右数奇数段石子异或和为 $0$ 则先手必败，否则必胜；证明核心是"$P=0$ 时任何操作都会破坏它，而 $P \neq 0$ 时总能一步修复"。
• 两个易错点：最左间隙是 $p_0 - 1$；异或的是从右数的奇数段。
• 复杂度 $O(n \log n)$，代码核心只有一行异或循环。