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

Link: https://www.luogu.com.cn/problem/P16264

题目描述

小蓝和小桥正在玩一个基于数列的博弈游戏。

初始时，给定一个长度为 $N$ 的数列 $W_1,W_2,\dots ,W_N$，数列中的每一个元素均为正奇数。

游戏由小蓝先手，两人交替进行操作。在每次操作中，当前操作者需要选择数列中一个严格大于 $0$ 的元素 $W_i$，并将其替换为一个严格小于它的非负整数 $W_i^{\prime }$（即 $0\le W_i^{\prime }<W_i$）。

该替换操作必须严格满足以下奇偶性限制：

1. 若选定的 $W_i$ 为奇数，则必须将其替换为 $W_i-1$。
2. 若选定的 $W_i$ 为偶数，则替换后的新数 $W_i^{\prime }$ 也必须是一个偶数。

当轮到某一方操作时，若其无法进行任何合法的替换，则该方输掉游戏，另一方获胜。

假设小蓝和小桥都绝顶聪明，均采取最优策略，请问最终谁将赢得这场游戏？

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的组数。

接下来依次输入 $T$ 组测试用例。

对于每组测试用例：

• 第一行包含一个整数 $N$，表示数列的长度。
• 第二行包含 $N$ 个正奇数 $W_1,W_2,\dots ,W_N$，相邻两个数字之间用空格隔开。

输出格式

对于每组测试用例，输出一行结果。如果小蓝获胜，输出 L；如果小桥获胜，输出 Q。

输入输出样例 #1

输入 #1

2
2
5 1
2
1 1

输出 #1

L
Q

说明/提示

【评测用例规模与约定】

对于所有的评测用例，$1\le T\le 10^3$，$1\le N\le 10^5$，$1\le W_i\le 10^9$。

保证所有测试用例中 $N$ 的总和不超过 $2\times 10^5$，且保证初始输入的所有 $W_i$ 均为奇数。

---

Solution

1. 题意

两个玩家游戏，一个数列，初始时全为正奇数。

玩家轮流操作，偶数必须替换为更小的非负偶数，奇数必须减一。轮到谁操作时数组全为零了就输了。

2. 分析

首先是一个最大的突破点，那就是数组里所有的数字是独立的（对一个数字操作不影响别的）。同时不难看出，有数字减为零则相当于将其移除。

这也就意味着拿到大于 $2$ 的偶数时，可以直接将其移除，也可以将其变为 $2$ 迫使对手将其移除。如此一来容易发现，顺着最优策略操作时：

• $1$ 和 $2$ 只能操作 $1$ 次；
• 其他大于 $1$ 的奇数只能操作 $2$ 次，因为第一次变为偶数后，下一步紧接着就是变为 $0$；
• 遇到大于 $2$ 的偶数直接将其清零移除（因为拿到大于 $2$ 的偶数如果没将其清零，对手拿到他就能根据场上局势选择将其清零还是变为 $2$，因此遇偶数不清零会给对手留下机会！），操作 $1$ 次。

因此只要统计一下整个数列在双方都使用最优策略时的总操作次数就可以了。

3. 代码

Python

t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    sg = 0
    for item in a:
        sg += (1 if item == 1 or item % 2 == 0 else 2)
    print("L" if sg % 2 == 1 else "Q")

C#

using System;
using System.Runtime.CompilerServices;

class P16264
{
    public static void Main()
    {
        int t, n, total_sg;
        string[] w;
        t = Convert.ToInt32(Console.ReadLine());
        while (t-- > 0)
        {
            total_sg = 0;
            n = Convert.ToInt32(Console.ReadLine());
            w = Console.ReadLine().Split();
            foreach (var item in w)
            {
                int x = Convert.ToInt32(item);
                if (x == 1 || (x & 1) == 0)
                {
                    total_sg++;
                }
                else
                {
                    total_sg += 2;
                }
            }
            Console.WriteLine((total_sg & 1) == 1 ? "L" : "Q");
        }
    }
}