非常好玩的一道博弈论的题目，结论与证明都非常巧妙，在翻月赛题目时看到的。蒟蒻希望能尽可能地讲清楚思考过程和结论的证明，如有问题请指出。
原题链接。
题目分析
为方便叙述，我们称分割的人为先手，另外一个人为后手。
二分答案 \(x\)，将原序列中大于等于 \(x\) 的位置变为 \(1\)，反之变为 \(0\)。那么问题就转化为雪能否取到 \(1\)。
我们记新序列中 \(1\) 的个数为 \(cnt_1\)，\(0\) 的个数为 \(cnt_0\)。我们猜测，当 \(cnt_1 > cnt_0\) 时，雪一定能赢；当 \(cnt_1 < cnt_0\) 时，K 一定能赢。
证明：问题的关键就是证明某一方的优势能否一直保持。
-
当 \(cnt_1 > cnt_0\) 时，被 K 分割后回有两种情况：两段都是 \(cnt_1' > cnt_0'\)；一段是 \(cnt_1' > cnt_0'\)，一段是 \(cnt_1' = cnt_0'\)。我们只需考虑第二种情况。
\(cnt_1' = cnt_0'\) 的这一段非常特别，我们只考虑它在右边的情况。记 \(pre_{i,1}, pre_{i,0}\) 分别表示 \(1,0\) 个数的前缀和，这个序列只有最后一个位置满足 \(pre_{i, 1} = pre_{i, 0}\)，否则我们可以将前面这些 \(pre_{i, 1} = pre_{i, 0}\) 的小段合并到做左边的序列，这样也符合我们的设定。
这么说可能有点抽象，下面举个例子。比如
1 1 0 1 0 1 0这个序列，如果我们选择从 \(3\) 位置分开，即分成1 1 0和1 0 1 0。但是我们完全可以把第一段1 0合并到左边，即分成1 1 0 1 0和1 0。如果这个序列只有最后一个位置满足 \(pre_{i, 1} = pre_{i, 0}\)，那么在任何一个位置分，都会分成 \(cnt_1' > cnt_0'\) 和 \(cnt_1' < cnt_0'\) 的两段，雪完全可以选择 \(cnt_1' > cnt_0'\) 的这一段，那么雪的优势便能一直保持。
-
当 \(cnt_1 < cnt_0\) 时，证明与 \(cnt_1 > cnt_0\) 的方法一样，不多赘述。
我们再来想想 \(cnt_1 = cnt_0\) 时的情况，咱先来手模几个。1 0 1 0 雪能赢，1 0 1 0 1 0 K能赢，1 0 1 0 1 0 1 0 雪又能赢。我们发现每个人的输赢好像是交替出现的。
我们把满足 \(pre_{i, 1} = pre_{i, 0}\) 的 \(i\) 称为一个“前缀点”。观察上面的例子，猜测如果有奇数个前缀点，那么 K (后手)能赢；如果有偶数个前缀点，雪(先手)能赢。
首先要发现的一点是，雪和 K 都不可能在前缀点以外的位置分割，与上文一样，这样一定会分成 \(cnt_1' > cnt_0'\) 和 \(cnt_1' < cnt_0'\) 的两段，那么下一个人就可以根据自己的需求选择一段，从而获取胜利。
我们可以用归纳证明：设前缀点个数为 \(m\)。
-
\(m\) 为奇数：当 \(k = 1\) 时，根据情况1的结论，后手能赢。假设当 \(k = m\) 时成立，当 \(k = m + 2\) 时，前两轮先手都在倒数第二个前缀点分开 (这一定不会使答案变坏，可以仔细想想)，那么剩下的就是 \(k = m\) 的情况，注意此时的先手没变，情况完全相同。
-
\(m\) 为偶数：同样地，选择倒数第二个前缀点分开，情况变成了 \(n\) 为奇数时的情形，不过现在的后手是刚开始的先手，那么先手一定能赢。
所以我们只需要找到最大的满足 \(cnt_1 > cnt_0\) 的数即可，这在原序列中就是中位数。不过注意，当 \(n\) 为偶数时，还要判断 \(\frac{n}{2} + 1\) 位置上的数是否可行。
如果排序求中位数，时间复杂度为 \(O(n \log n)\)，如果是线性求，则可做到 \(O(n)\)。
Code
#include <bits/stdc++.h>
using namespace std;constexpr int N = 1e5 + 9;
int n;
int a[N], b[N], pre[2];void solve(){cin >> n;for(int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i];sort(b + 1, b + 1 + n);if(n & 1){cout << b[(n + 1) / 2] << '\n';//中位数return;}int x = b[n / 2 + 1];//偶数要特判int res = 0;for(int i = 1; i <= n; i++){int c = (a[i] >= x);pre[c]++;if(pre[0] == pre[1]) res++;}if(res & 1) cout << b[n / 2] << '\n';else cout << x << '\n';pre[1] = pre[0] = 0;
}int main(){int T;cin >> T;while(T--) solve();return 0;
}