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

P16264 [蓝桥杯 2026 省 Python B 组] 奇偶博弈Link: https://www.luogu.com.cn/problem/P16264题目描述小蓝和小桥正在玩一个基于数列的博弈游戏。初始时给定一个长度为N NN的数列W 1 , W 2 , … , W N W_1, W_2, \dots, W_NW1​,W2​,…,WN​数列中的每一个元素均为正奇数。游戏由小蓝先手两人交替进行操作。在每次操作中当前操作者需要选择数列中一个严格大于0 00的元素W i W_iWi​并将其替换为一个严格小于它的非负整数W i ′ W_iWi′​即0 ≤ W i ′ W i 0 \leq W_i W_i0≤Wi′​Wi​。该替换操作必须严格满足以下奇偶性限制若选定的W i W_iWi​为奇数则必须将其替换为W i − 1 W_i - 1Wi​−1。若选定的W i W_iWi​为偶数则替换后的新数W i ′ W_iWi′​也必须是一个偶数。当轮到某一方操作时若其无法进行任何合法的替换则该方输掉游戏另一方获胜。假设小蓝和小桥都绝顶聪明均采取最优策略请问最终谁将赢得这场游戏输入格式输入的第一行包含一个整数T TT表示测试用例的组数。接下来依次输入T TT组测试用例。对于每组测试用例第一行包含一个整数N NN表示数列的长度。第二行包含N NN个正奇数W 1 , W 2 , … , W N W_1, W_2, \dots, W_NW1​,W2​,…,WN​相邻两个数字之间用空格隔开。输出格式对于每组测试用例输出一行结果。如果小蓝获胜输出 L如果小桥获胜输出 Q。输入输出样例 #1输入 #12 2 5 1 2 1 1输出 #1L Q说明/提示【评测用例规模与约定】对于所有的评测用例1 ≤ T ≤ 10 3 1 \leq T \leq 10^31≤T≤1031 ≤ N ≤ 10 5 1 \leq N \leq 10^51≤N≤1051 ≤ W i ≤ 10 9 1 \leq W_i \leq 10^91≤Wi​≤109。保证所有测试用例中N NN的总和不超过2 × 10 5 2 \times 10^52×105且保证初始输入的所有W i W_iWi​均为奇数。Solution1. 题意两个玩家游戏一个数列初始时全为正奇数。玩家轮流操作偶数必须替换为更小的非负偶数奇数必须减一。轮到谁操作时数组全为零了就输了。2. 分析首先是一个最大的突破点那就是数组里所有的数字是独立的对一个数字操作不影响别的。同时不难看出有数字减为零则相当于将其移除。这也就意味着拿到大于2 22的偶数时可以直接将其移除也可以将其变为2 22迫使对手将其移除。如此一来容易发现顺着最优策略操作时1 11和2 22只能操作1 11次其他大于1 11的奇数只能操作2 22次因为第一次变为偶数后下一步紧接着就是变为0 00遇到大于2 22的偶数直接将其清零移除因为拿到大于2 22的偶数如果没将其清零对手拿到他就能根据场上局势选择将其清零还是变为2 22因此遇偶数不清零会给对手留下机会操作1 11次。因此只要统计一下整个数列在双方都使用最优策略时的总操作次数就可以了。3. 代码Pythontint(input())for_inrange(t):nint(input())alist(map(int,input().split()))sg0foritemina:sg(1ifitem1oritem%20else2)print(Lifsg%21elseQ)C#usingSystem;usingSystem.Runtime.CompilerServices;classP16264{publicstaticvoidMain(){intt,n,total_sg;string[]w;tConvert.ToInt32(Console.ReadLine());while(t--0){total_sg0;nConvert.ToInt32(Console.ReadLine());wConsole.ReadLine().Split();foreach(variteminw){intxConvert.ToInt32(item);if(x1||(x1)0){total_sg;}else{total_sg2;}}Console.WriteLine((total_sg1)1?L:Q);}}}