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

· · 题解

本题用 SG 定理（详见下文链接），推导出初始奇数中仅数值 1 的 SG 值为 1，其余大于 1 的奇数 SG 值均为 0，所以游戏胜负仅取决于数列中 1 的个数的奇偶性：如果 1 的个数为奇数则先手小蓝胜，否则后手小桥胜，那么只需统计 1 的个数即可。

  1. SG 定理。
  2. SG 定理。

:::info[详细解释] 设偶数为 a，奇数为 b。
设 k 为总 SG 值数列中 1 的个数。

  1. 那么 a 可变为 \{ 0,2,...,a - 2 \}，推导得 \operatorname{SG}(a) = \frac{a}{2}。
  2. - 当 $b = 1$ 时，$\operatorname{SG}(1) = \operatorname{mex} \{ 0 \} = 1$。 - 当 $b > 1$ 时，$\frac{b - 1}{2} \ge 1$，那么 $\operatorname{SG}(b) = \operatorname{mex} \{ \ge 1\} = 0$。
  3. 仅数值为 1 的项对应的 SG 值 1，其余奇数对应的值为 0。那么总 SG 值为 k \bmod 2。

:::

:::success[AC Code]{open}

#include <bits/stdc++.h>
#define int long long
using namespace std;
void solve(){
    int n;
    cin>>n;
    int ans=0;
    for (int i=0;i<n;i++) {
        int w; 
        cin>>w;
        if(w==1) ans++;
    } 
    if(ans%2!=0) cout<<"L"<<endl;
    else cout<<"Q"<<endl;

}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t;
    cin>>t;
    while(t--) solve();
    exit(0);
}

:::

感谢博客 IcyCheees 提供的资料。
感谢博客 Hypoc_ 提供的资料。