演剧题解

出题人题解。

雪和 K 在一个长度为 $n$ 的序列上博弈。

雪和 K 轮流行动。雪先手。每次操作方可以把序列从一个分割点分成非空的两个部分，然后由博弈的另一方删去其中一个部分，继续对剩下的一部分博弈。

具体的，第一轮由雪分割 K 删去，第二轮由 K 分割雪删去，第三轮由雪分割 K 删去。

当最后只剩下一个数而一方无法操作时游戏终止。雪想让此时剩下的最后一个数尽量大，K 想让它尽量小。

假设两人绝对聪明，试求出最后剩下的数。

对于所有数据，$1\le T\le 10,1\le n\le 10^5,1\le a_i\le 10^9$。

若 $n$ 为奇数，则答案为中位数。

若 $n$ 为偶数，将序列较大的中位数记为 $x_1$，另一个记为 $x_2$，并把 $a_i\ge x_1$ 的数标记为 $b_i=1$，否则为 $b_i=-1$。

记 $b$ 可以分成的最多和为 $0$ 的连续段的数量 $C$。

当 $C$ 为奇数时答案为 $x_2$，否则答案为 $x_1$。

可以考虑归纳法证明。现在我们要证明大小为 $n$ 的序列，不妨假设 $<n$ 的序列都按照上文的结论判断答案。边界是简单的。

由于先后手交换，我们不妨套路的确定答案为 $y$，然后把 $\ge y$ 的数赋为 $1$，否则为 $-1$。每次让给对方以后每个数要取相反数。

重新写出结论：和为正时赢，和为负时输，和为 $0$ 时按照上文方法判断。

若和为正，则一定可以找到一个最小的分割点，满足左半边和为 $0$。或者是找到两边都和为正。切割以后显然赢。

若和为负，至少有一边会和为负，所以肯定输。

若和为 $0$，不能分成一正一负。只能分一段时肯定输，两段时肯定赢，三段输，以此归纳即可。