题解：P13309 演剧

MPLN · 2025-07-16 19:08:51 · 题解

超好玩的题！

前言

场切了。

博弈论的那些专业的东西我也不懂，但是找规律我们小学就会对吧。比赛的时候觉得这题我怎么可能做出来，但是看到后面的题更不会，不死心，还是来硬刚这道。通过不断的排除和尝试，测试近百个小数据之后，终于发现了最重要的一个博弈规律，虽然场上没有严谨地证明（赛后 5 分钟就证出来了），但是直接写发现就 AC 了。

这告诉我们不要害怕难题，再难的想法，再复杂的算法，都是从最简单的东西里来的。这样的思维题若做不出来一定要不断尝试，因为看似捉摸不透的规律在数据之中便可一目了然。

思路

首先容易想到二分答案，为啥呢？例如我们要 check 雪能不能让最终剩下的数 \ge x，我们就可以给所有 \ge x 的 a_i 标记为 1，即最后剩下这个数是可以的；剩余的数标记为 0，即最后剩下这个数不行。

一番操作下来，我们只需要对于只有 0/1 的 a 序列判断最后剩下的数是 0 还是 1 就行了。如果最后是 1 那么雪“获胜”成功，如果最后剩下 0 那么 K 成功让雪做不到最后剩下 \ge x 的数。

我们从最最最简单的情况入手：

如果整个序列全是 1，这时候 K 没法玩了，雪一定获胜。

那么我们可以说句废话，如果雪要赢，最后肯定是全是 1。所以序列 1 多肯定是对雪有帮助的。

第一种情况

记序列 1 的数量为 c_1，0 的数量为 c_0，假设最开始序列就满足 c_1>c_0，那么有没有一种方法让雪一直保持住 c_1\ge c_0 的优势，从而最后拿下游戏？

当然是有的。

雪只需要保证自己每次分割都让序列变成这样两个序列：

• 其中一个序列 c_1=c_0，且不存在一个前缀或后缀也满足 c_1=c_0（这里的前后缀不能是自身）；
• 另一个序列随意，容易发现也满足 c_1>c_0。

这个分割一定是可以达成的，证明较简单便不赘述。

接下来 K 就过来删了，如果删 c_1=c_0 的序列，剩下的不就又满足 c_1>c_0 了。如果删另一个序列，那么接下来 K 就要开始分割 c_1=c_0 的序列了，因为这个序列满足不存在一个前缀或后缀 c_1=c_0，所以不管怎么分割总会剩下一个 c_1>c_0 的序列，雪直接挑走！

所以无论如何，这个序列都会一直满足 c_1\ge c_0，而显然最后只会剩下一个数字，那只能是 1！

综上，若原序列 c_1>c_0，则最后剩下 1。

第二种情况

假设最开始序列满足 c_1<c_0，那么有没有一种方法让 K 一直保持住 c_1\le c_0 的优势，从而最后拿下游戏？

因为 K 是后手，所以需要让雪先来分割，但是无论雪如何分割，总有一段会保持 c_1<c_0，K 直接选走，就换成 K 先手的情况了，剩余讨论和 c_1>c_0 的情况一样。

综上，若原序列 c_1<c_0，则最后剩下 0。

第三种情况

剩下的就是 c_1=c_0 的情况，这时候最后会剩下什么呢？

雪先来分割，雪非常想赢，雪直接拿出了自己之前的招式，分割成了这样：

• 其中一个序列 c_1=c_0，且不存在一个前缀或后缀也满足 c_1=c_0（这里的前后缀不能是自身）；

• 另一个序列随意，容易发现也满足 c_1=c_0。

  K 如果选了前者来分割，那他怎么分割都会有一个 c_1>c_0 的数列，被雪选走就转化成了之前的情况，必输，所以 K 只能选后者。

  雪发现这样似乎一眼看不到胜利的感觉，所以想着换种分割方法是不是更好，但是仔细一想，如果分割出来一个 c_1>c_0 的序列，一个 c_1<c_0 的序列后者被选走就更废了，只能分成两个 c_1=c_0 的序列稳妥。

  对于 K 也是同理，K 拿到序列后也必须这样分。

  那最后谁会赢呢？如果对方拿到一个不存在前缀或后缀也满足 c_1=c_0 的序列自己就赢了。

  为了方便考虑，我们可以先统计出原序列是由多少个存在前缀或后缀也满足 c_1=c_0 的子串组成的。因为雪和 K 的分割都不会擅自在某个这样的子串中间割开，否则自己就输了。

设这个数为 m。

如果一方需要对 m=1 的序列进行分割，那他就输了。

如果你对奇偶性敏感，很快就会发现一条规律，一方拿到任何奇数 m，都会输，相反拿到偶数 m 就会赢。

因为分割的时候奇数只能分成 奇数 + 偶数，对方选走偶数，然后分成 奇数 + 奇数，最后自己还是拿到一个奇数。如此往复下去，因为对方永远不会拿到奇数，而终将有人拿到 1 失败，那自己一定会输。

综上，若 m 为偶数，最后剩下 1，否则最后剩下 0。

总结

以上三种情况的判断即为 check 函数的全部任务，都可以做到线性，写起来也不复杂，最重要的还是构造博弈方法。

参考代码

时间复杂度 O(Tn\operatorname{log}V)，V 为最大的 a_i。离散化之后可以做到 O(Tn\operatorname{log}n)，但是完全没有必要。

#include<bits/stdc++.h>
using namespace std;
int T, n, a[100010], p[100010], q[100010], cnt[2];
bool c[100010];
bool chk(int x) {
    cnt[1] = cnt[0] = 0;
    for (int i = 1; i <= n; i++)
        cnt[c[i] = a[i] >= x]++;
    if (cnt[1] > cnt[0]) return 1;
    else if (cnt[1] < cnt[0]) return 0;
    int l1 = 0, l2 = 0, res = 0;
    for (int i = 1; i <= n; i++) {
        if (c[i]) l1++;
        else l2++;
        if (l1 == l2) res++;
    }
    if (res % 2 == 0) return 1;
    else return 0;
}
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        int l = 1, r = 1e9;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (chk(mid)) l = mid;
            else r = mid - 1;
        }
        cout << l << endl;
    }
    return 0;
}

后记

本篇题解到这里就结束了，希望大家都能在尝试与探索中找到乐趣，享受通过一次次努力得到结论的喜悦！