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

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