其他题目

第17届蓝桥杯省赛C++研究生组真题个人解析—C题2026的出现次数
第17届蓝桥杯省赛C++研究生组真题个人解析—D题评测漏洞
第17届蓝桥杯省赛C++研究生组真题个人解析—F题基态坍缩
第17届蓝桥杯省赛C++研究生组真题个人解析—G题综合应变指标

一、题目描述

1.1题目大意

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

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

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

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

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

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

1.2输入格式

第一行包含一个正整数T，表示测试数据的组数。
接下来依次给出T组测试数据。对于每组测试数据：
第一行包含一个正整数N，表示该次对抗推演中量子链的节点总数。
第二行包含N个正整数A1,A2,…,AN，依次表示从链路前端到末端各节点的初始能级，相邻数值之间以单个空格分隔。

1.3输出格式

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

1.4示例

输入：
2
2
1 2
2
2 1
输出：
L
Q

1.5输入数据规模

对于30%的评测用例，1≤T≤100，1≤N≤10的3次方，1≤Ai≤10的3次方，所有测试数据中N的总和不超过5×10的3次方。
对于所有评测用例，1≤T≤10的4次方，1≤N≤10的5次方，1≤Ai≤10的9次方，所有测试数据中N的总和不超过2×10的5次方。

要求时间限制在1s，内存为256MB。

二、题目分析及解题代码

2.1题目分析

看到该题中提到两人轮流操作且双方均采取对自己最优的策略，会首先想到博弈论算法，而且是非常经典的Nim博弈。针对该类问题可以使用固定的定理公式去解决，但本文介绍一种不使用定理，依靠推理解题的思路，即使没有学过博弈论算法的读者也可以解决该类题目。

思路如下：

1. 假设最终获胜的是L，那么说明L是最先对A1节点操作的人，无论A1取值为多少，L最先操作则一定会将A1减到0，轮到Q时，Q没有节点可以操作，则L获胜；
2. 那么如何使得L最先对A1节点操作，这与A2的值有关。假设A2的值为1，那么最先对A2操作的人必须是Q，Q别无选择只能将A2减去1变为0，从而使得L最先对A1操作；
3. 如果A2的值大于1，那么最先对A2操作的人必须是L，L可以将A2的值减到1留给下一次操作的Q，Q别无选择只能将A2减去1变为0，使得L最先对A1操作，从而获胜；
4. 依此类推，可以计算出对An最先操作的人是L还是Q，如果是L，题目规定L执先手，则最终L获胜，反之Q获胜。

上述过程读者可以构造一些实例进行推理帮助理解。

2.2解题代码

#include<bits/stdc++.h>
using namespace std;

const int INF=1e5+10;
int a[INF];
int t,n;

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(int i=1; i<=n; i++) cin>>a[i];
		int flag=0;
		for(int i=2; i<=n; i++)
		{
			if(a[i]==1 && flag==0)
			{
				flag=1;
				continue;
			}
			if(a[i]>1 && flag==0)
			{
				flag=0;
				continue;
			}
			if(a[i]==1 && flag==1)
			{
				flag=0;
				continue;
			}
			if(a[i]>1 && flag==1)
			{
				flag=0;
				continue;
			}
		}
		if(flag==0) cout<<"L\n";
		else cout<<"Q\n";
	}
	return 0;
}

2.3代码说明

上述代码定义了一个变量flag，初始化为0，代表假定最先对A1操作的人是L，然后从A2开始对数组进行遍历，对每个元素是否等于1分为两种情况，分别对flag进行更新，最后判断flag是否等于0，如果等于0说明对An最先操作的人是L，而执先手的正是L，那么L获胜，反之Q获胜。

代码复杂度为O(n)，题目规定输入的测试数据N的总和不超过2×10的5次方，可以满足1s的时间要求。

三、洛谷平台提交验证

3.1洛谷链接

该题目在洛谷平台的链接地址为：https://www.luogu.com.cn/problem/P16251
题目名称为：P16251 [蓝桥杯 2026 省研究生组] 基态坍缩

3.2提交结果

提交解题代码结果如下图，测试用例全部通过：

四、小结

如果赛前已经学习过博弈论算法，那么该题目是一道基础的模板题。而如果没有学习过博弈论，刚开始面临这道题可能会觉得无从下手，需要一定的耐心和推理能力想出解题方法。