题解：P16264 [蓝桥杯 2026 省 Python B 组] 奇偶博弈

· · 题解

题目传送门：P16264 [蓝桥杯 2026 省 Python B 组] 奇偶博弈

题目分析：

本题是一个公平组合游戏（Impartial Combinatorial Game），给定一个全部由正奇数构成的数列 W_1, W_2, \dots, W_N，两人轮流操作。

每次操作：

选择一个大于 0 的数 W_i；

将其替换为一个严格小于它的非负整数 W_i'；

奇偶限制：

若 W_i 为奇数，则 W_i' = W_i - 1（固定）；

若 W_i 为偶数，则 W_i' 也必须为偶数（可以是 0）。

无法操作者输。

由于初始全是奇数，第一步必然将某个奇数变为偶数。之后偶数可以一步步减小（每次变为更小的偶数），直到 0。

思路：

每个数独立一次只改变一个数，整个游戏是多个子游戏的和（Nim 和）。

奇数操作固定：奇数 x 只能变成 x-1（偶数），没有选择。

偶数操作灵活：偶数 e 可以变成任意一个比它小的偶数，包括 0。

这等价于：你可以一次拿走任意偶数颗石子（包括全部）。

因此，每个偶数的子游戏就是：

一堆石子，每次可以拿走偶数颗，不能拿者输。

这是一个经典的偶数取子游戏。

SG函数的推导

偶数的 SG 值：

设 g(e) 表示偶数 e 的 SG 值。

边界：g(0) = 0。

对于 e > 0 且为偶数，可到达所有偶数 e'（0 \le e' < e）。

计算得：

g(2) = \operatorname{mex}{g(0)} = \operatorname{mex}{0} = 1 g(4) = \operatorname{mex}{g(0), g(2)} = \operatorname{mex}{0, 1} = 2 g(6) = \operatorname{mex}{g(0), g(2), g(4)} = \operatorname{mex}{0, 1, 2} = 3

归纳可得：

g(e) = \frac{a}{b}

奇数的 SG 值：

设 h(x) 表示奇数 x 的 SG 值。奇数只能到达 x-1（偶数），因此：

h(x) = \operatorname{mex}\{g(x-1)\} = \operatorname{mex}\left\{\frac{x-1}{2}\right\}

当 \frac{x-1}{2} = 0，即 x = 1 时，h(1) = \operatorname{mex}\{0\} = 1。

当 \frac{x-1}{2} \ge 1，即 x \ge 3 时，h(x) = \operatorname{mex}\{k\} = 0（其中 k \ge 1）。

因此：

h(x) = \begin{cases} 1, & x = 1 \\ 0, & x \ge 3 \end{cases}

那么，整体的SG函数值为

初始数列全为奇数，每个数的 SG 值为：

整体 SG 值为所有 W_i 的 SG 值异或和，即：

\operatorname{SG}_{\text{总}} = \bigoplus_{i=1}^{N} [W_i = 1]

其中 [W_i = 1] 为示性函数，值为 1 当且仅当 W_i = 1。

胜负判定：

若 \text{SG}_{\text{总}} \neq 0，则先手（小蓝）获胜，输出 L。

若 \text{SG}_{\text{总}} = 0，则后手（小桥）获胜，输出 Q。

由于 \text{SG}_{\text{总}} 等于数列中 1 的个数的奇偶性（奇数个 1 时异或值为 1，偶数个 1 时异或值为 0），胜负仅取决于 1 的出现次数的奇偶性。

算法步骤

读入测试用例组数 T。

对于每组测试用例：

读入 N。

遍历 N 个数，统计其中等于 1 的个数 \textit{cnt}。

若 \textit{cnt} 为奇数，输出 L；否则输出 Q。

时间复杂度 O(\sum N)，空间复杂度 O(1)。

代码实现：

#include <iostream>
using namespace std;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int cnt = 0;
        for (int i = 1;i <= n;i++) {
            int w;
            cin >> w;
            if (w == 1) cnt++;
        }
        if (cnt % 2 == 1) cout << "L" << endl;
        else cout << "Q" << endl;
    }
    return 0;
}