题解：P13309 演剧
wing_heart
·
·
题解
P13309 演剧
更好的阅读体验
题意
A 和 B 在玩游戏。
给你一个长度为 n 的序列。A 先手。
每一轮，先手会选择一个切割点，把序列分成两份。然后后手选择留下其中一部分。然后交换先后手。
最后只剩下一个数字的时候，游戏结束。
A 希望剩下的数字尽可能大，B 希望剩下的数字尽可能小。
求剩下的数字。
## 思路
参考了出题人题解。
想试试我能不能把我的想法有理有据的讲出来。
----------
除了 A 先手之外，其他条件都是完全公平的。
于是我们大胆猜测留下来的一定是中位数。（序列长度为偶数时，我们认为有两个中位数）
-----------
我们试着证明无论哪个人先手，都不能取到比中位数大的数字。（求比中位数小的数是对称的）
钦定比中位数大的数字的权值是 `+1`，其他是 `-1`。
序列为偶数时，我们可以加一个 $inf$ 变成序列为奇数的情况，不影响比中位数排名加一的数字。因此考虑序列为奇数的情况。
当 A 先手时，它一定可以把序列分成两份，其中一份的权值和是 `-1`，另一份的权值和是 `0`。B 选择 `-1` 的那份。下一轮，B 把序列分成 `-1` 和 `0`，A 选择 `0`。
因此最后只剩下一个数字的时候，权值一定是 `-1`。
证毕。
-----------
现在只需要求出，对于序列长度为偶数，且两个中位数不相等的情况，答案是哪个中位数。
较小的中位数为 $x_1$，较大的中位数为 $x_2$。
钦定 $\ge x_2$ 的数字权值为 $1$，其他数字权值为 $-1$。
什么时候可以取到 `1`？
考虑一个极端情况（为了好看，这里把 `-1` 写作 `0`）：`0000011111`。
A 先手，把序列分成 `000001111 1`。
B 选择前者。然后把序列分成 `0 00001111`。
这种情况不能取到 `1`。
对于序列 `0001010111` 之类，也是同样结果。
对于这类序列，先手不得不把它分成权值和为 `-1`，`1` 两部分。后手有选择其中一个的权力，因此先手必输。
即，对于一个长度极小的，权值和为 `0` 的序列，先手必输。
对于还能分成若干个权值和为 `0` 的序列，先手会把序列分成 `0` 和 `0`。
假设原序列可以分成两个极小 `0` 序列。那么后手输。
假设原序列可以分成三个极小 `0` 序列，那么左边有一个极小 `0` 序列，右边有两个极小 `0` 序列，后手选择左边，然后先手输。
假设原序列可以分成四个极小 `0` 序列，因为 1、3 必输，所以先手必胜。
因此假设原序列可以分成 $cnt$ 个极小 `0` 序列。$cnt$ 奇数时先手输，偶数时先手赢。
## code
使用 `nth_element()` 函数可以做到平均 $O(n)$。
```cpp
#include<bits/stdc++.h>
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
namespace wing_heart {
constexpr int N=1e5+7;
int T;
int n,a[N],b[N];
void main() {
sf("%d",&T);
while(T--) {
sf("%d",&n);
rep(i,1,n) sf("%d",&a[i]);
memcpy(b,a,sizeof(b));
if(n&1) {
nth_element(b+1,b+(n>>1)+1,b+n+1);
int x = b[(n>>1)+1];
pf("%d\n",x);
} else {
nth_element(b+1,b+(n>>1),b+n+1);
int x1 = b[n>>1];
nth_element(b+1,b+(n>>1)+1,b+n+1);
int x2 = b[(n>>1)+1];
int cnt=0, sum=0;
if(x1==x2) pf("%d\n",x1);
else {
rep(i,1,n) {
if(a[i]>=x2) sum++;
else sum--;
if(sum==0) ++cnt;
}
if(cnt&1) pf("%d\n",x1);
else pf("%d\n",x2);
}
}
}
}
}
int main() {
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("my.out","w",stdout);
#endif
wing_heart :: main();
}
```