P16251 [蓝桥杯 2026 省研究生组] 基态坍缩
Link: https://www.luogu.com.cn/problem/P16251
题目描述
一条量子链由
N
N
N 个节点按顺序连接而成，节点从前端到末端依次编号为
1
∼
N
1 \\sim N
1∼N。第
i
i
i 个节点的初始能级为正整数
A
i
A_i
Ai。
有两种控制模型 L 与 Q 在该链路上进行对抗，它们都采用最优策略并交替操作，且 L 先手。
每次轮到某个模型操作时，必须对当前量子链的末端节点（即当前序列的最后一个节点）进行一次降阶干预，规则如下：
- 设末端节点当前能级为
B
B
B。 - 必须将其能级重置为一个整数
x
x
x，满足0
≤
x
<
B
0 \\leq x < B
0≤x<B。 - 若重置后该节点能级变为
0
0
0，则该节点立即从链路中剥离；此时它前一个节点（若存在）成为新的末端节点。 - 若重置后该节点能级大于
0
0
0，则该节点仍留在链路末端，等待后续操作继续被降阶。
对抗会持续进行，直到量子链被完全剥离（即所有节点都被移除）。当某个模型轮到操作时，若链上已无节点，则该模型将因为无法执行操作而被判定为失败，另一方获胜。
请判断在双方均采取最优策略的情况下，最终获胜者是谁。
输入格式
第一行包含一个正整数
T
T
T，表示测试数据的组数。 接下来依次给出
T
T
T 组测试数据。对于每组测试数据：
- 第一行包含一个正整数
N
N
N，表示该次对抗推演中量子链的节点总数。 - 第二行包含
N
N
N 个正整数A
1
,
A
2
,
…
,
A
N
A_1, A_2, \\ldots, A_N
A1,A2,…,AN，依次表示从链路前端到末端各节点的初始能级，相邻数值之间以单个空格分隔。
输出格式
对于每组测试数据，输出一行一个字符串。若控制模型 L 能够取得最终胜利，请输出 L；若模型 Q 获胜，请输出 Q。
输入输出样例 #1
输入 #1
2
2
1 2
2
2 1
输出 #1
L
Q
说明/提示
【评测用例规模与约定】
对于
30
%
30\\%
30% 的评测用例，
1
≤
T
≤
100
1 \\leq T \\leq 100
1≤T≤100，
1
≤
N
≤
10
3
1 \\leq N \\leq 10^3
1≤N≤103，
1
≤
A
i
≤
10
3
1 \\leq A_i \\leq 10^3
1≤Ai≤103，所有测试数据中
N
N
N 的总和不超过
5
×
10
3
5 \\times 10^3
5×103。
对于所有评测用例，
1
≤
T
≤
10
4
1 \\leq T \\leq 10^4
1≤T≤104，
1
≤
N
≤
10
5
1 \\leq N \\leq 10^5
1≤N≤105，
1
≤
A
i
≤
10
9
1 \\leq A_i \\leq 10^9
1≤Ai≤109，所有测试数据中
N
N
N 的总和不超过
2
×
10
5
2\\times 10^5
2×105。
Solution
1. 题意
给了一个数组
{
a
i
}
\\{a_i\\}
{ai}，每次只能对最后一个元素操作，将其修改为一个比之前小的值，为零时将其移除。轮到谁操作时数组为空就输了。求先后手谁会赢。
2. 分析
不难看出，末尾不为
1
1
1 时，当前行动的玩家就占据上风，因为他可以选择将其修改为
1
1
1 迫使对手将其移除，也可以直接将其修改为
0
0
0 主动移除。
而当末尾为
1
1
1 时，他被迫将其移除，从而将主动权拱手让人（如果倒数第二个的初始值不为
1
1
1）。
如此一来就会发现，序列里每出现一个
1
1
1，先手必胜/必败的状态就会反转一次。
由于空状态是先手必败，因此如果全部节点都为
1
1
1，且节点数为奇数的话，则 L 胜利，否则则 Q 胜利。
如果有节点不为
1
1
1，那么整个序列相当于若干个仅由
1
1
1 构成的串（长度可以为零）随即穿插在整个序列里。谁先占领到第一个不为
1
1
1 的数字，就能根据
1
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");
}
}
}
}
