题解：P16666 [CSPro 25] 博弈论与石子合并

pangun · 2026-10-22 19:40:54 · 题解

题意

有小 c 与小 z 两位玩家玩一个游戏，轮流操作一个序列 a_{1 \dots n}，每次可以删除两端的一个数或把相邻数合并为其和。这样直到序列只剩一个数，小 c 会最小化这个数，而小 z 相反。给定先手，保证 n \le 10^5。

题解

首先观察特殊性质，发现与奇偶性和先后手有关，于是分类讨论。具体的，我们经过简单的手模，发现最后一个操作的人决定了这个游戏的性质，于是分开处理。

小 z 最后操作

这个比较简单。我们观察到小 z 是不希望自己的合并过的东西被删除的，而且似乎他的确有方法避免这一点：即在中间进行合并。

形式化的，我们令 l = \left\lfloor \frac{n}{2} \right\rfloor + 1, S = \min_{1 \le i \le n - l + 1} \sum_{i \le j \le i + l - 1} a_j，那么可以证明 S 即为答案。

证明从两个方向进行：首先是小 c 可以用某些操作取到 S，这是显然的，只需要删去区间外的数即可；如果小 z 的一些操作导致没法这么做，那一定是合并了区间外的数或删数了，两种都只会节省小 c 的操作次数，答案只可能更小，所以小 z 不可能这么做。

然后是小 z 也可以取得 S。因为 l 大于总长一半，那么一定覆盖了中点，于是合并总可以合并中间，因此可以保证小 c 删不到小 z 合并过的数。如果小 c 删除了小 z 本应合并的数，那么小 z 也可以更改区间，而且因为原来是最小值，这个区间一定是对小 z 不劣的。小 c 合并也同理，不可能使得答案更小了。

这样双方会达成一种默契，使得小 z 在中间合并，小 c 在两边删数，直到达成 S。

小 c 最后操作

这时小 c 几乎一定会删到小 z 合并过的数，因此上面的推理不适用了。

我们在反复手模后提出如下猜想：如果可以把区间划分为若干段，使得小 z 足以合并出来且小 c 无法全破坏完，那么答案一定不小于那些段的和的最小值。

这看上去很有前途（虽然我找不出更合理的引入了），所以我们仔细算一下，发现只要有 L = \left\lfloor \frac{n}{2} \right\rfloor + 1 段就够用了，因为这正好比小 c 的操作次数多 1。

那么现在唯一的问题就是证明了。这也是本题解的主要内容：

形式化的，我们定义 V(A) 为序列 A 的答案，G(A, x) 表示把 A 最多可以划分为几个和不小于 x 的段。我们需要证明：

引理

引理 1（单调性）：对 A 做任何一次合法操作得 A'，均有 G(A', x) \le G(A, x)。

证明：任一 A' 的 k 段划分，在 A 中均可还原为至少 k 段（合并的逆是拆开，删除的逆是把该元素并入相邻段或独立成段）。故 G(A, x) \ge G(A', x)。

引理 2（丢弃端点）：若 G(A, x) \ge k，则丢弃 A 的任一端点得 A'，有 G(A', x) \ge k - 1。

证明：由对称性，只需考虑左端点。若左端点在 A 的划分中独立成段，那么直接舍弃就可以得到 k - 1 下界；若不是独立成段，那么把该段和后面一段合并，一定也不小于 x 且最多减小 1。

引理 3（合并段内元素）：若 A 的某 k 段划分中，有相邻两元素同属一段，则合并它们得 A'，仍有 G(A', x) \ge k。

证明：合并只改变该段内部结构，段数不变。

引理 4（贪心划分）：G(A, x) 可以由贪心算法给出：从左到右累加，如果当前段和 \ge x，那么把这一段切出来计数，然后从下一个元素继续开始。若剩余部分和 < x 则不计数。

证明：（太典了，这也要证吗？）令贪心得到的段的第 k 个右端点为 s_k，任意划分的第 k 个右端点为 r_k，我们归纳证明 s_k \le r_k，从而证明贪心得到的解不劣于任意解。

2. 此时有 s_k \le r_k，如果 r_{k + 1} 存在，那么因为 A 中均为正整数，从 s_k + 1 到 r_{k + 1} 的和必然不小于 x，所以 s_{k + 1} 不晚于 r_{k + 1} 取得，有 s_{k + 1} \le r_{k + 1}。

归纳证明

对 |A| 归纳。|A| = 1 时，V(A) = A_1，G(A, x) = [A_1 \ge x]，结论显然成立。

设结论对 |A| - 1 成立，证 |A| 的情况。分两种回合。

小 c 回合

这时有 |A| = 2L - 2，且回合结束后有 L \leftarrow L - 1。

因为小 c 希望值最小，所以我们有：

那么只需证：

充分性（\Rightarrow）：有 G(A, x) \ge L，证任意操作后 G(A', x) \ge L - 1。

• 合并 A_i, A_{i + 1}：在 A 的划分中，这两元素或同段（段数仍 \ge L），或异段（段数变为 L - 1）。均有 \ge L - 1。
• 丢弃端点：由引理 2，G(A', x) \ge L - 1。

必要性（\Leftarrow）：有 G(A, x) \le L - 1，证存在操作使 G(A', x) \le L - 2。

若 G(A, x) \le L - 2，由引理 1，任意操作即可。下设 G(A, x) = L - 1。

设贪心切分为 S_1, \dots, S_{L - 1} 加剩余 R（可空），共 L 个部分，总长 2L - 2。

简单讨论，我们发现要么存在长为 1 的段，要么全是长为 2 的段且 R = \varnothing。

情形 1：某 S_i 长度为 1，即 S_i = \{ y \}，y \ge x。

• 否则我们可以把 S_i 和其前面一个元素合并。根据引理 4，我们考虑贪心合并的流程，发现 S_i 及其之前的段数减 1，而之后的部分不受影响。所以 G(A', x) \le L - 2。

情形 2：所有 S_i 长度为 2。

我们可以丢弃右端。因为 R = \varnothing，以及贪心算法的划分原则，这会使得最后一个段失效，而前面的也不会受影响，所以 G(A', x) \le L - 2。

综上，必要性成立。

小 z 回合

这时有 |A| = 2L - 1，且操作完后 L 不变。

因为小 z 希望值最大，所以我们有：

那么只需证：

充分性（\Rightarrow）：有 G(A, x) \ge L，证存在操作使 G(A', x) \ge L。

因为 |A| = 2L - 1 > L，所以由鹊巢原理，存在一个段有至少 2 个数（最后剩的一点归到最后一段），由引理 3，如此操作段数不变，故存在 G(A', x) = G(A, x) \ge L。

必要性（\Leftarrow）：设 G(A, x) \le L - 1，证任意操作后 G(A', x) \le L - 1。

由引理 1 直接得到。

综上，我们完成了归纳证明。命题得证。

那么可以二分答案 x，从而解决这一问。

CODE

#include <bits/stdc++.h>

const int N = 1e5 + 5;
int n, K, a[N];

int solve0() {
    int len = n / 2 + 1, sum = 0, ans = 1e9;
    for (int i = 1; i < len; ++i) sum += a[i];
    for (int i = len; i <= n; ++i) {
        sum += a[i] - a[i - len];
        ans = std::min(ans, sum);
    }
    return ans;
}

bool check(int x) {
    int sum = 0, cnt = 0;
    for (int i = 1; i <= n; ++i) {
        sum += a[i];
        if (sum >= x) { ++cnt; sum = 0; }
        if (cnt >= n / 2 + 1) return true;
    }
    return false;
}

int solve1() {
    int l = 1, r = 1e9, ans = 0, mid;
    while (l <= r) {
        mid = l + (r - l) / 2;
        if (check(mid)) { ans = mid; l = mid + 1; }
        else r = mid - 1;
    }
    return ans;
}

int main() {
#ifdef PANGUN
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
#endif

    scanf("%d%d", &n, &K);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    if (n % 2 != K) printf("%d\n", solve0());
    else printf("%d\n", solve1());
    return 0;
}

该说不说，这题出的还是不错的，如果它没出在模拟赛。