题解：P13309 演剧

chenxi2009 · 2025-07-17 20:07:57 · 题解

思路

怎么最高赞是个二分啊，那我来写一手。也许画个图会清楚些？

我们先讨论 a_i\in\{-1,1\}，当最后剩下一个 1 的时候先手赢，剩下 -1 时先手输。每次分割完之后交换先后手，同时根据题意原先的 1 变成 -1，-1 变成 1（因为先后手目标相反，为了保证对称性做出如上变换）。

我们根据博弈的状态开始讨论：

• 终止状态：剩下一个 1，胜态；剩下一个 -1，败态。
• 剩下若干数字，总和为正：可能可以分成两部分总和为正，此时对手的接续状态是总和为负；可能可以分成一部分总和为正，一部分总和为零，对手的接续状态是总和为负或总和为零。
• 剩下若干数字，总和为负：同上，对手总能合理选择使得接续状态是总和为正。

这个时候发现总和为正有胜态的雏形，总和为负有负态的雏形，但是还不够，继续讨论总和为零：

• 拟边界：总和为零且不能分割成两部分使得两部分总和均为零，此时先手划分出来的一定是一正一负，后手选择保留负段，故接续状态为和为正，所以这个边界暂定为败态；
• 总和为零，且如果分成尽可能多的和为 0 的段可以分出 k 段，k 为偶数，则下一步可以分成两个 k 为奇数，或两个 k 为偶数。

画个类似于自动机的状态图（s 表示总和，\text{odd}/\text{even} 表示能分成 s=0 的极小段的个数 k 的奇偶性）：

刚刚都是初步的推导，是为了确定我们要把什么作为胜态、什么作为负态去讨论，有了这个图我们就可以进行严谨的证明了：

严谨的证明

• 终止胜态是 s>0 的子集，终止负态是 s<0 的子集，指向胜态的是负态，指向的全是负态的是胜态，归纳可得 s>0 和 s=0,\text{even} 是胜态，s<0 和 s=0,\text{odd} 是负态。

综上，我们得出了 a_i\in\{-1,1\} 时的结论。这个时候已经有了二分答案的做法，大于等于答案的为 1，小于答案的为 -1，计算 s 和 k 就可以得到结果。

但是没有必要。可以发现当 n\equiv 1\pmod 2 时，答案为 a 的中位数满足 s>0，大于 a 的中位数则 s<0，所以此时答案就是 a 的中位数；n\equiv 0\pmod 2 时，取较小的中位数则有 s>0，取较大的中位数则 s=0，此时若 k 为偶数，则答案为较大的中位数；否则答案只能取较小的中位数。

取中位数可以做到线性，时间复杂度 O(Tn)。下面代码的实现基于排序，时间复杂度 O(Tn\log n)。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 200000;
int T,n,a[N],b[N],c[N],k,s;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> T;
    while(T --){
        cin >> n;
        for(int i = 1;i <= n;i ++) cin >> a[i],b[i] = a[i];
        sort(b + 1,b + n + 1);
        if((n & 1) || b[n / 2] == b[n / 2 + 1]) printf("%d\n",b[n / 2 + 1]);
        else{
            for(int i = 1;i <= n;i ++){
                if(a[i] > b[n / 2]) c[i] = 1;
                else c[i] = -1;
            }
            k = s = 0;
            for(int i = 1;i <= n;i ++){
                s += c[i];
                if(!s) k ++;
            }
            printf("%d\n",b[n / 2 + 1 - (k & 1)]);
        }
    }
    return 0;
}