P16251 [蓝桥杯 2026 省研究生组] 基态坍缩

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

题目描述

一条量子链由 $N$ 个节点按顺序连接而成，节点从前端到末端依次编号为 $1\sim N$。第 $i$ 个节点的初始能级为正整数 $A_i$。

有两种控制模型 L 与 Q 在该链路上进行对抗，它们都采用最优策略并交替操作，且 L 先手。

每次轮到某个模型操作时，必须对当前量子链的末端节点（即当前序列的最后一个节点）进行一次降阶干预，规则如下：

• 设末端节点当前能级为 $B$。
• 必须将其能级重置为一个整数 $x$，满足 $0\le x<B$。
• 若重置后该节点能级变为 $0$，则该节点立即从链路中剥离；此时它前一个节点（若存在）成为新的末端节点。
• 若重置后该节点能级大于 $0$，则该节点仍留在链路末端，等待后续操作继续被降阶。

对抗会持续进行，直到量子链被完全剥离（即所有节点都被移除）。当某个模型轮到操作时，若链上已无节点，则该模型将因为无法执行操作而被判定为失败，另一方获胜。

请判断在双方均采取最优策略的情况下，最终获胜者是谁。

输入格式

第一行包含一个正整数 $T$，表示测试数据的组数。
接下来依次给出 $T$ 组测试数据。对于每组测试数据：

• 第一行包含一个正整数 $N$，表示该次对抗推演中量子链的节点总数。
• 第二行包含 $N$ 个正整数 $A_1,A_2,\dots ,A_N$，依次表示从链路前端到末端各节点的初始能级，相邻数值之间以单个空格分隔。

输出格式

对于每组测试数据，输出一行一个字符串。若控制模型 L 能够取得最终胜利，请输出 L；若模型 Q 获胜，请输出 Q。

输入输出样例 #1

输入 #1

2
2
1 2
2
2 1

输出 #1

L
Q

说明/提示

【评测用例规模与约定】

对于 $30\%$ 的评测用例，$1\le T\le 100$，$1\le N\le 10^3$，$1\le A_i\le 10^3$，所有测试数据中 $N$ 的总和不超过 $5\times 10^3$。

对于所有评测用例，$1\le T\le 10^4$，$1\le N\le 10^5$，$1\le A_i\le 10^9$，所有测试数据中 $N$ 的总和不超过 $2\times 10^5$。

---

Solution

1. 题意

给了一个数组 { a i } \{a_i\} {ai​}，每次只能对最后一个元素操作，将其修改为一个比之前小的值，为零时将其移除。轮到谁操作时数组为空就输了。求先后手谁会赢。

2. 分析

不难看出，末尾不为 $1$ 时，当前行动的玩家就占据上风，因为他可以选择将其修改为 $1$ 迫使对手将其移除，也可以直接将其修改为 $0$ 主动移除。

而当末尾为 $1$ 时，他被迫将其移除，从而将主动权拱手让人（如果倒数第二个的初始值不为 $1$）。

如此一来就会发现，序列里每出现一个 $1$，先手必胜/必败的状态就会反转一次。

由于空状态是先手必败，因此如果全部节点都为 $1$，且节点数为奇数的话，则 L 胜利，否则则 Q 胜利。

如果有节点不为 $1$，那么整个序列相当于若干个仅由 $1$ 构成的串（长度可以为零）随即穿插在整个序列里。谁先占领到第一个不为 $1$ 的数字，就能根据 $1$ 的分布决定将其移除还是迫使对手移除。

因此我们只要判断最后一个出现的非 $1$ 节点的下标是否为奇数即可，是则后手 Q 胜利，否则先手 L 胜利。

3. 代码

using System;

class P16251
{
    static void Main()
    {
        int T = Convert.ToInt32(Console.ReadLine());
        while (T-- > 0)
        {
            int n = Convert.ToInt32(Console.ReadLine());
            string[] inputs = Console.ReadLine().Split();
            int pos = -1; 
            for (int i = 1; i <= n; i++)
            {
                int x = Convert.ToInt32(inputs[i - 1]);
                if (x > 1) pos = n - i + 1;
            }
            if (pos == -1) 
            {
                if (n % 2 == 1) Console.WriteLine("L");
                else Console.WriteLine("Q");
            }
            else
            {
                if (pos % 2 == 1) Console.WriteLine("L");
                else Console.WriteLine("Q");
            }
        }
    }
}