题解：P13309 演剧

思路

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

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

严谨的证明

• $s>0$ 时，可能可以分成两段 $s>0$ 使得对手进入 $s<0$ 的状态；如果不能，那么一定可以分成一段 $k=1,s=0$ 和一段 $s>0$，使对手要么进入 $s<0$ 状态，要么进入 $s=0,\text{odd}$ 状态；
• $s<0$ 时，无论怎么分都必有一段 $s<0$，对手一定可以进入 $s>0$ 状态；
• $s=0,\text{odd}$ 时，要么分成一段 $s>0$，一段 $s<0$，对手可以进入 $s>0$ 状态；要么分成一段 $\text{odd}$，一段 $\text{even}$，对手可以进入 $\text{even}$ 状态；
• $s=0,\text{even}$ 时，一定可以分成两段 $\text{odd}$，使对手进入 $\text{odd}$ 状态。
• 终止胜态是 $s>0$ 的子集，终止负态是 $s<0$ 的子集，指向胜态的是负态，指向的全是负态的是胜态，归纳可得 $s>0$ 和 $s=0,\text{even}$ 是胜态，$s<0$ 和 $s=0,\text{odd}$ 是负态。

代码

#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;
}