AtCoder Beginner Contest 458 题解

for-each2026年8月18日大约 21 分钟

AtCoder Beginner Contest 458 题解

项目	内容
比赛时间	2026-05-16
比赛链接	https://atcoder.jp/contests/abc458
题目数量	A–G 共 7 题

比赛概览

本场难度由浅入深、梯度均匀：A、B 是纯基础题（字符串切片、网格相邻格计数），C 是简单的按字符计数，D 是经典的「两个堆维护中位数」。从 E 开始有明显区分度：E 需要组合数学（插空法与隔板法），F 需要 Aho–Corasick 自动机配合矩阵快速幂处理超大长度，G 则是利用斜率优化（Slope Trick）配合二分答案的压轴题。其中 F、G 两题值得重点掌握：前者是"小模式集 + 巨大长度"的通用处理范式，后者是单调性二分与凸函数 DP 优化的经典组合。

A - Chompers

题目链接：https://atcoder.jp/contests/abc458/tasks/abc458_a

题目大意

给定一个小写字母组成的字符串 $S$ 和一个正整数 $N$ （满足 $2N+1 \le |S| \le 30$ ）。去掉 $S$ 开头的 $N$ 个字符和末尾的 $N$ 个字符，输出剩下的字符串。

思路

这是最直白的字符串切片题。若用 $0$ -下标编号，则剩余部分是 $S$ 中下标从 $N$ 到 $|S|-N-1$ 的这一段，长度为

|S| - 2N.

直接调用语言自带的子串函数即可：

C++ 中用 s.substr(N, s.size() - 2*N)（第一个参数是起始下标，第二个参数是长度）；
Python 中用 s[n : len(s)-n]。

约束保证 $|S| \ge 2N+1$ ，所以剩余长度至少为 $1$ ，无需担心边界。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    int n;
    cin >> s >> n;
    cout << s.substr(n, (int)s.size() - 2 * n) << '\n';
    return 0;
}

官方题解亦给出了 Python 实现：

s = input()
n = int(input())
print(s[n:len(s) - n])

复杂度分析

时间复杂度： $O(|S|)$ （子串拷贝）。
空间复杂度： $O(|S|)$ 。

B - Count Adjacent Cells

题目链接：https://atcoder.jp/contests/abc458/tasks/abc458_b

题目大意

有一个 $H$ 行 $W$ 列的网格，记 $(i,j)$ 为第 $i$ 行第 $j$ 列的格子。两个格子 $(x_1,y_1)$ 、 $(x_2,y_2)$ 称为边相邻，当且仅当 $|x_1-x_2|+|y_1-y_2|=1$ 。请对每个格子输出与它边相邻的格子数，按 $H$ 行输出。

思路

一个格子至多有 $4$ 个候选邻居，即上、下、左、右四个方向：

(i-1,j),\quad (i+1,j),\quad (i,j-1),\quad (i,j+1).

对每个格子逐一检查这四个候选是否在网格内（下标不越界）即可。

另一种做法是分类讨论：角上的格子答案为 $2$ ，边上（非角）的格子答案为 $3$ ，内部的格子答案为 $4$ ； $1 \times 1$ 时答案为 $0$ ，单行或单列时边界答案为 $1$ 。但直接枚举四个方向更简单，也不容易漏掉边界情况（尤其 $H=1$ 或 $W=1$ 时）。注意 $H$ 、 $W$ 最大只有 $50$ ，枚举完全可行。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int H, W;
    cin >> H >> W;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            int cnt = 0;
            if (i - 1 >= 0) cnt++;
            if (i + 1 < H) cnt++;
            if (j - 1 >= 0) cnt++;
            if (j + 1 < W) cnt++;
            if (j) cout << ' ';
            cout << cnt;
        }
        cout << '\n';
    }
    return 0;
}

复杂度分析

时间复杂度： $O(HW)$ 。
空间复杂度： $O(1)$ （除输出外）。

C - C Stands for Center

题目链接：https://atcoder.jp/contests/abc458/tasks/abc458_c

题目大意

给定一个大写字母组成的字符串 $S$ （ $|S| \le 5 \times 10^5$ ）。统计满足以下条件的子串（连续子序列）个数：

长度为奇数；
它的正中间那个字符是 C。

从不同位置取出的相同子串也要分开计数。

思路

关键观察：固定子串的中间字符。若 $S$ 的第 $i$ 个字符（ $0$ -下标）是 C，那么以它为中心、长度为奇数的子串，左右两侧的字符数必须相等。

设子串左右各取 $t$ 个字符，则：

左边最多能取 $i$ 个字符（即 $S[0..i-1]$ 全取），右边最多能取 $|S|-1-i$ 个字符；
因此 $t$ 的取值范围是 $0 \le t \le \min(i,\ |S|-1-i)$ 。

于是以 $S[i]$ 为中心的子串个数为

\min(i,\ |S|-1-i)+1 = \min(i+1,\ |S|-i).

对 $S$ 中每一个字符 C 累加上式即得答案：

\text{ans} = \sum_{i:\, S[i]=\texttt{C}} \min(i+1,\ |S|-i).

为什么正确：每个满足条件的子串都有唯一的中间位置，而同一位置为中心的子串由 $t$ 唯一确定（向左右各扩展 $t$ 个字符），所以按位置分类计数既不重也不漏。

注意： $|S| \le 5\times 10^5$ 且全为 C 时，答案约为 $\sum_i \min(i+1,|S|-i) \approx \frac{|S|^2}{4} \approx 6.25\times 10^{10}$ ，超出了 int 范围，务必使用 64 位整数。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    ll n = (ll)s.size();
    ll ans = 0;
    for (ll i = 0; i < n; i++) {
        if (s[i] == 'C') {
            ans += min(i + 1, n - i);
        }
    }
    cout << ans << '\n';
    return 0;
}

复杂度分析

时间复杂度： $O(|S|)$ 。
空间复杂度： $O(1)$ （不含字符串本身）。

D - Chalkboard Median

题目链接：https://atcoder.jp/contests/abc458/tasks/abc458_d

题目大意

黑板上初始写着一个整数 $X$ 。依次处理 $Q$ 个询问，第 $i$ 个询问给出两个整数 $A_i, B_i$ ：先把 $A_i$ 和 $B_i$ 写到黑板上，然后输出当前黑板上全部 $2i+1$ 个数的中位数。

思路

共有 $Q$ 次插入，每次插入两个数，集合大小始终为奇数 $2i+1$ ，因此中位数唯一。需要支持动态插入并快速查询中位数，经典做法是双堆法：

用最大堆 $L$ 维护较小的一半（中位数含在其中），用最小堆 $R$ 维护较大的一半；
保持不变式： $L$ 中所有元素 $\le$ $R$ 中所有元素，且 $|L|=|R|$ 或 $|L|=|R|+1$ 。

由于总元素个数始终为奇数，插入一对后必有 $|L|=|R|+1$ ，此时中位数就是 $L$ 的堆顶 $\max L$ 。

插入一个数 $x$ 的过程：

若 $x \le L.\text{top()}$ ，插入 $L$ ；否则插入 $R$ 。此时" $L$ 中元素都 $\le$ $R$ 中元素"依然成立，但大小关系可能失衡。
重新平衡：
- 若 $|L| > |R|+1$ ：把 $L$ 的堆顶（ $\max L$ ）移到 $R$ ；
- 若 $|L| < |R|+1$ （即 $|L| \le |R|$ ）：把 $R$ 的堆顶（ $\min R$ ）移到 $L$ 。

注意两个 if 必须依次都执行而不是二选一：因为一次移动会同时改变两堆大小，先移动一次之后可能正好平衡、也可能仍不平衡，顺序检查两个条件即可保证最后回到 $|L|=|R|$ 或 $|L|=|R|+1$ 之一。

为什么正确：移动堆顶不破坏" $L$ 中元素 $\le R$ 中元素"的性质。例如把 $\max L$ 移入 $R$ 时，它仍 $\le$ $R$ 中所有元素；把 $\min R$ 移入 $L$ 时，它仍 $\ge$ $L$ 中所有元素。因此两个不变式始终成立， $L.\text{top()}$ 即中位数。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int X, Q;
    cin >> X >> Q;
    priority_queue<int> L;                          // 较小的一半（大根堆）
    priority_queue<int, vector<int>, greater<int>> R; // 较大的一半（小根堆）
    L.push(X);
    auto add = [&](int v) {
        if (v <= L.top()) L.push(v);
        else R.push(v);
        if ((int)L.size() < (int)R.size() + 1) { L.push(R.top()); R.pop(); }
        if ((int)L.size() > (int)R.size() + 1) { R.push(L.top()); L.pop(); }
    };
    while (Q--) {
        int a, b;
        cin >> a >> b;
        add(a);
        add(b);
        cout << L.top() << '\n';
    }
    return 0;
}

官方题解还提供了 Python 版本（内部用负数把最小堆当最大堆用）：

import sys

input = sys.stdin.readline
from heapq import heappush, heappop

L = [-int(input())]  # 较小的一半，用负数存储于最小堆
R = []


def add(x):
    if x <= -L[0]:
        heappush(L, -x)
    else:
        heappush(R, x)

    if len(L) < len(R) + 1:
        heappush(L, -heappop(R))
    if len(L) > len(R) + 1:
        heappush(R, -heappop(L))


for _ in range(int(input())):
    a, b = map(int, input().split())
    add(a), add(b)
    print(-L[0])

复杂度分析

时间复杂度： $O(Q \log Q)$ 。
空间复杂度： $O(Q)$ 。

E - Count 123

题目链接：https://atcoder.jp/contests/abc458/tasks/abc458_e

题目大意

求长度为 $X_1+X_2+X_3$ 的序列 $A=(a_1,\dots,a_{X_1+X_2+X_3})$ 的个数，满足：

恰好含 $X_1$ 个 1、 $X_2$ 个 2、 $X_3$ 个 3；
任意相邻两项之差的绝对值 $\le 1$ ，即 $|a_{i+1}-a_i|\le 1$ 。

答案对 $998244353$ 取模。其中 $1 \le X_1,X_2,X_3 \le 10^6$ 。

思路

关键观察

条件 $|a_{i+1}-a_i|\le 1$ 等价于：1 与 3 不能相邻。因为所有相邻对中只有 $(1,3)$ 与 $(3,1)$ 的差为 $2$ ，其余（ $1$ - $1$ 、 $1$ - $2$ 、 $2$ - $2$ 、 $2$ - $3$ 、 $3$ - $3$ ）的差都不超过 $1$ 。

因此序列的结构是：1 段与 3 段交替出现，任意两个相邻的不同段之间必须至少夹一个 2；而 2 可以出现在任意位置（包括首尾和连续出现）。

抽出子序列 $B$

把序列 $A$ 中所有 1 和 3 按原顺序抽出来，得到子序列 $B$ 。 $B$ 中连续相同的字符会连成段，而 1 段与 3 段必然交替。 $B$ 一共有四种开头/结尾的形态，分别计数后相加。

下面记 $\mathrm{part}(n,k)=\binom{n-1}{k-1}$ ：把 $n$ 个相同物品分成 $k$ 个非空连续段的方式数（隔板法）。

情形 1： $B$ 以 1 开头且以 1 结尾。

设 $B$ 有 $i$ 段连续的 1，则它有 $i-1$ 段连续的 3（如 $1^{a_1}3^{b_1}1^{a_2}3^{b_2}\cdots 3^{b_{i-1}}1^{a_i}$ ）。 $B$ 的形态数为

\mathrm{part}(X_1,i)\cdot \mathrm{part}(X_3,i-1).

$B$ 内部 1 与 3 相邻的位置共有 $2i-2$ 处。为了在 $A$ 中保证 1 与 3 不相邻，这 $2i-2$ 个位置必须各夹一个 2（强制放置）。之后还剩余 $X_2-(2i-2)$ 个 2 可以任意插入到 $B$ 形成的空隙中。换一种等价的说法：先强制安放这 $2i-2$ 个 2，得到一个长度为 $X_1+X_2+X_3-(2i-2)$ 的"骨架"，再在其中选出 $X_1+X_3$ 个位置放 $B$ 的元素，其余放多余的 2，方式数为

\binom{X_1+X_2+X_3-(2i-2)}{X_1+X_3}.

故情形 1 的贡献为

\sum_{i}\ \mathrm{part}(X_1,i)\,\mathrm{part}(X_3,i-1)\, \binom{X_1+X_2+X_3-2i+2}{X_1+X_3}.

因为 $X_3\ge 1$ ， $B$ 必含 3，所以 $i$ 从 $2$ 取到 $X_1$ 。

情形 2： $B$ 以 3 开头且以 3 结尾。

与情形 1 完全对称，交换 $X_1$ 与 $X_3$ ：

\sum_{i=2}^{X_3}\ \mathrm{part}(X_3,i)\,\mathrm{part}(X_1,i-1)\, \binom{X_1+X_2+X_3-2i+2}{X_1+X_3}.

情形 3： $B$ 以 1 开头、3 结尾。

设 $B$ 有 $i$ 段连续的 1，则它有 $i$ 段连续的 3，1 与 3 相邻的位置共有 $2i-1$ 处。 $B$ 的形态数为 $\mathrm{part}(X_1,i)\cdot\mathrm{part}(X_3,i)$ ，贡献为

\sum_{i=1}^{\min(X_1,X_3)}\ \mathrm{part}(X_1,i)\,\mathrm{part}(X_3,i)\, \binom{X_1+X_2+X_3-2i+1}{X_1+X_3}.

情形 4： $B$ 以 3 开头、1 结尾。

与情形 3 计数完全相同，只需在总和中乘 $2$ 。

最终答案把四种情形加起来即可。

组合数的计算

令 $N=X_1+X_2+X_3$ 。预处理 $0!\sim N!$ 及其模逆元，则每个 $\binom{n}{r}$ 可在 $O(1)$ 内求出（当 $n<0$ 或 $n<r$ 时返回 $0$ ，可自动滤掉不合法的 $i$ ）。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 998244353;

ll modpow(ll a, ll e) {
    ll r = 1;
    while (e) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll x1, x2, x3;
    cin >> x1 >> x2 >> x3;
    ll N = x1 + x2 + x3;
    vector<ll> fact(N + 1), invf(N + 1);
    fact[0] = 1;
    for (ll i = 1; i <= N; i++) fact[i] = fact[i - 1] * i % MOD;
    invf[N] = modpow(fact[N], MOD - 2);
    for (ll i = N; i >= 1; i--) invf[i - 1] = invf[i] * i % MOD;

    auto ncr = [&](ll n, ll r) -> ll {
        if (n < 0 || r < 0 || n < r) return 0;
        return fact[n] * invf[r] % MOD * invf[n - r] % MOD;
    };
    auto part = [&](ll x, ll p) -> ll {   // 把 x 个物品分成 p 个非空段
        if (p < 1 || x < p) return 0;
        return ncr(x - 1, p - 1);
    };

    ll ans = 0;
    // 情形 1：B 以 1 开头和结尾
    for (ll i = 2; i <= x1; i++) {
        ll add = part(x1, i) * part(x3, i - 1) % MOD
               * ncr(N - (2 * i - 2), x1 + x3) % MOD;
        ans = (ans + add) % MOD;
    }
    // 情形 2：B 以 3 开头和结尾
    for (ll i = 2; i <= x3; i++) {
        ll add = part(x3, i) * part(x1, i - 1) % MOD
               * ncr(N - (2 * i - 2), x1 + x3) % MOD;
        ans = (ans + add) % MOD;
    }
    // 情形 3 与 4：B 以 1 开头 3 结尾 / 3 开头 1 结尾（合并，乘 2）
    for (ll i = 1; i <= min(x1, x3); i++) {
        ll add = 2 * part(x1, i) % MOD * part(x3, i) % MOD
               * ncr(N - (2 * i - 1), x1 + x3) % MOD;
        ans = (ans + add) % MOD;
    }
    cout << ans << '\n';
    return 0;
}

复杂度分析

时间复杂度： $O(N)$ ，其中 $N=X_1+X_2+X_3 \le 3\times 10^6$ （阶乘预计算 $O(N)$ ，每种情形累加 $O(X_1+X_3)$ ）。
空间复杂度： $O(N)$ 。

F - Critical Misread

题目链接：https://atcoder.jp/contests/abc458/tasks/abc458_f

题目大意

给定 $K$ 个由小写字母组成的字符串 $S_1,\dots,S_K$ （ $K\le 10$ ， $1\le |S_i|\le 10$ ）。求长度为 $N$ （ $1\le N\le 10^9$ ）的、由小写字母组成的、且不以其中任何一个 $S_i$ 作为子串的字符串个数，对 $998244353$ 取模。

思路

朴素的 DP 为什么不成立

最朴素的想法是设 $dp[k][\text{长度为 }k\text{ 的后缀}]$ 表示合法字符串个数，但后缀种类数为 $26^k$ ，即使 $k\le 10$ 也完全不可行，更不必说 $N$ 高达 $10^9$ 。

压缩状态：Aho–Corasick 自动机

记 $T$ 为所有 $S_i$ 的前缀组成的集合（含空串）。例如 $S=\{\texttt{abc},\texttt{abde},\texttt{bcd}\}$ 时， $T=\{\texttt{},\texttt{a},\texttt{ab},\texttt{abc},\texttt{abd},\texttt{abde},\texttt{b},\texttt{bc},\texttt{bcd}\}$ 。 $|T|\le \sum |S_i|\le 100$ 。

关键观察：判断"新追加一个字符后是否出现禁用子串"，只需记住当前串在 $T$ 中的最长后缀。例如当前串是 xyzab，只需记住后缀 ab 而非 b，因为再追加 c 会形成 abc，而仅仅记住 b 会漏掉这一信息。这正是 Aho–Corasick 自动机（含 fail 转移）做的事。

据此定义自动机状态为 $T$ 中的每个字符串，转移为：从状态 $p$ 读入字符 $c$ ，进入状态" $p+c$ 的最长后缀中属于 $T$ 的那个"。对 $T$ 中每个前缀暴力求最长后缀即可完成建表（ $|T|\le 101$ ，完全可以 $O(|T|^2)$ 处理）。

转移矩阵与矩阵快速幂

把"当前自动机状态"作为 DP 的维度，于是"追加 $k$ 个字符的转移"就是一个矩阵幂：

构造矩阵 $M$ ，其中 $M[i][j]$ 表示从状态 $i$ 出发、读入一个字符后落到状态 $j$ 的字符个数。
从某个状态出发，若目标状态对应的字符串包含某个 $S_i$ 作为子串（称其为"坏状态"），则这条转移非法，不计入 $M$ ；从坏状态出发的转移也全部不计。
初始向量 $\vec v$ 只在空串状态为 $1$ 。做 $N$ 次转移即 $\vec v \cdot M^N$ ，用二进制快速幂计算，最终答案为 $\sum_j v_j$ 。

为什么这样能排除所有含禁用子串的字符串：若一个字符串包含 $S_i$ ，那么在逐字符读入的过程中，读到 $S_i$ 最后一个字符的那一刻，自动机状态是"当前前缀的最长 $T$ 后缀"，而 $S_i$ 本身是 $T$ 的元素且是该前缀的后缀，所以该状态必然包含 $S_i$ 作为后缀，即必定是坏状态，对应的转移会被排除。

正确性依据：自动机状态（当前串在 $T$ 中的最长后缀）决定了后续所有可能的发展，是 DP 的充分状态；而矩阵快速幂正确处理了 $N\le 10^9$ 的步数。

题外话：官方题解提到本题源自 NDPC-C（Automaton DP），本题是其"误读"变体，只是更显式地做自动机上的 DP。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 998244353;

bool isSuffix(const string &a, const string &b) {  // b 是否为 a 的后缀
    if (a.size() < b.size()) return false;
    return a.compare(a.size() - b.size(), b.size(), b) == 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll N;
    int K;
    cin >> N >> K;
    vector<string> S(K);
    map<string, int> mp;
    mp[""] = 0;  // 空串为状态 0
    for (int i = 0; i < K; i++) {
        cin >> S[i];
        string pref;
        for (char c : S[i]) {
            pref.push_back(c);
            mp[pref] = 0;
        }
    }

    int V = 0;
    vector<string> vs;
    vs.reserve(mp.size());
    for (auto &p : mp) {
        vs.push_back(p.first);
        p.second = V++;
    }

    // 标记坏状态：字符串中含任一禁用子串
    vector<int> ban(V, 0);
    for (int i = 0; i < V; i++) {
        for (auto &p : S) {
            if (vs[i].find(p) != string::npos) { ban[i] = 1; break; }
        }
    }

    // 转移矩阵 M[i][j] = 从 i 出发读一个字符进入 j 的字符个数
    vector<vector<ll>> mat(V, vector<ll>(V, 0));
    for (int i = 0; i < V; i++) {
        if (ban[i]) continue;
        for (char c = 'a'; c <= 'z'; c++) {
            string ss = vs[i] + c;
            int tg = 0;  // 取 ss 的最长 T 后缀
            for (int j = 0; j < V; j++) {
                if (isSuffix(ss, vs[j]) && vs[tg].size() < vs[j].size()) tg = j;
            }
            if (ban[tg] == 0) mat[i][tg]++;
        }
    }

    auto mmul = [&](const vector<vector<ll>> &A, const vector<vector<ll>> &B) {
        vector<vector<ll>> C(V, vector<ll>(V, 0));
        for (int i = 0; i < V; i++)
            for (int k = 0; k < V; k++) if (A[i][k])
                for (int j = 0; j < V; j++)
                    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
        return C;
    };

    vector<ll> vec(V, 0);
    vec[0] = 1;  // 初始在空串状态
    ll n = N;
    while (n > 0) {
        if (n & 1) {
            vector<ll> nvec(V, 0);
            for (int i = 0; i < V; i++)
                for (int j = 0; j < V; j++)
                    nvec[j] = (nvec[j] + vec[i] * mat[i][j]) % MOD;
            vec = nvec;
        }
        mat = mmul(mat, mat);
        n >>= 1;
    }
    ll ans = 0;
    for (ll v : vec) ans = (ans + v) % MOD;
    cout << ans << '\n';
    return 0;
}

复杂度分析

设自动机状态数 $V \le \sum |S_i| + 1 \le 101$ 。
时间复杂度：建表 $O(26\cdot V^2)$ ，矩阵快速幂 $O(V^3 \log N)$ 。
空间复杂度： $O(V^2)$ 。

G - Children Yearn for the Evil Kindergarten

题目链接：https://atcoder.jp/contests/abc458/tasks/abc458_g

题目大意

游戏场内有 $10^{100}$ 个小孩，初始没有任何奖牌。一个小孩退出（drop out）或逃出（escape）时便离开场地。游戏共 $N$ 天，第 $i$ 天依次执行：

收集在场小孩持有的全部奖牌，记总数为 $s$ ；
在场小孩中自由分配 $s + A_i$ 枚奖牌（若场地无人则无事发生）；
在场小孩中，奖牌少于 $B_i$ 的退出；奖牌不少于 $B_i$ 的每人失去 $B_i$ 枚；
在场小孩中，奖牌不少于 $C_i$ 的可以自主选择此刻逃出或留下。

第 $N$ 天结束仍留在场地的小孩将退出。求最多能让多少个小孩最终逃出。给定 $T$ 组测试数据（ $\sum N \le 3\times 10^5$ ）。

思路

单调性与二分答案

首先注意到：若 $m$ 个小孩能全部逃出，那么任意 $m'\le m$ 个小孩也能——只需忽略其中 $m-m'$ 个（不给它们奖牌、不指望它们逃出），其余按原方案执行。因此答案具有单调性，可以二分答案 $m$ ，问题转化为：能否让恰 $m$ 个小孩全部逃出？

此外我们只把奖牌分配给这 $m$ 个小孩，其余 $10^{100}-m$ 个小孩永远拿 $0$ 枚奖牌（给他们奖牌只会浪费）。于是每一天收集的奖牌 $s$ 就是这 $m$ 个小孩当前持有的奖牌总数。

二分上界：第 1 天分发前所有小孩奖牌都为 $0$ ，场上的 $A_1$ 枚奖牌是唯一来源；而幸存过第 1 天的小孩在"退出检查"时刻必须持有至少 $B_1 \ge 1$ 枚奖牌，所以最多 $A_1$ 个小孩能活过第 1 天。任何一个逃出的小孩都必须活过第 1 天（退出即永久离开），故答案 $\le A_1$ 。二分区间取 $[0, A_1]$ 。

可行性 DP

固定 $m$ 后，设 $dp[i][x]$ 表示第 $i$ 天结束时场地内还剩 $x$ 个小孩（尚未逃出的那部分）时，这些小孩持有奖牌总数的最大值；若该状态不可行记为 $-\infty$ 。初始 $dp[0][m]=0$ ， $dp[0][x< m]=-\infty$ 。

转移一（无人逃出，仅可能有人退出）：第 $i$ 天先收集 $dp[i-1][x]$ 枚奖牌，再分发 $dp[i-1][x]+A_i$ 枚。若想让 $x$ 个小孩全部通过退出检查（每人至少 $B_i$ 枚），需要总数不少于 $B_i x$ ，即

dp[i][x] = dp[i-1][x] + A_i - B_i x \ge 0.

若该值为负，说明无论如何分配都无法让 $x$ 人全部存活，置为 $-\infty$ 。

转移二（有人逃出）：若第 $i$ 天"失去 $B_i$ 枚"之后有 $x+1$ 人，其中奖牌数 $\ge C_i$ 的一人逃出，则剩 $x$ 人。为使剩下 $x$ 人持有的奖牌总数最大，让逃出者恰好带走 $C_i$ 枚：

dp[i][x] = \max\bigl(dp[i][x],\ dp[i][x+1] - C_i\bigr),

同样若为负则置为 $-\infty$ （说明此时没有人的奖牌数能达到 $C_i$ ，不可能逃出）。

判定条件：若某一天之后 $x$ 能降到 $0$ ，即 $dp[i][0] \ne -\infty$ ，那么 $m$ 个小孩已全部逃出；此后场地无人，后续每天的所有操作都是空操作，状态不变。因此"某一天（含第 $N$ 天）达到 $x=0$ "即可判定成功。

直接枚举 $x$ 的复杂度为 $O(Nm)$ ，不可行。但可以证明：对任意 $i$ ， $dp[i][x]$ 的可行区间是一个连续段 $[x_l,x_r]$ ，且 $dp[i][x]$ 关于 $x$ 是凹函数（相邻差分不增）。于是用 Slope Trick 维护该分段线性函数，把两种转移都变成 $O(1)$ 均摊操作。

斜率优化（Slope Trick）

用 deque 存储分段线性函数的折点 $(x, y)$ （按 $x$ 递增），并维护一个整体线性掩码 $y' = s_a x + s_b$ ，使得折点 $p$ 处的真实函数值为

\operatorname{eval}(p) = s_a \cdot p.x + s_b + p.y.

相邻折点 $p,q$ 之间的真实斜率为 $s_a + \dfrac{q.y-p.y}{q.x-p.x}$ 。函数在两端之外按首尾段的斜率线性延伸。

转移一（整体加 $A_i - B_i x$ ）：只需更新掩码 $s_b \mathrel{+}= A_i,\ s_a \mathrel{-}= B_i$ 。由于 $dp[i]$ 是凹的（"山峰"形状），值为负的区域只可能出现在左右两端：从后端和前端依次弹出真实值为负的折点；若某一段恰好跨过 $y=0$ ，则求出它与零线的交点并保留该点为新的端点。若折点全部被弹出，说明没有任何可行的剩余人数，判定失败。
转移二（从 $x$ 小的左端削去斜率 $\ge C_i$ 的段，并接一段斜率为 $C_i$ 的段）：max 式转移在凸/凹函数上的作用就是把左端斜率不小于 $C_i$ 的部分整体"压平"成一段斜率为 $C_i$ 的线段。做法：从左端开始，若首段的斜率 $\ge C_i$ 就弹出其端点；然后计算

x_{\text{add}} = \left\lfloor \frac{\operatorname{eval}(\text{左端折点})}{C_i} \right\rfloor,

它表示这段斜率为 $C_i$ 的线可以向左延伸多远而不使值降为负（整数向下取整）。若 $x_{\text{add}} \ge$ 左端折点的 $x$ ，则线段能延伸到 $x=0$ ，即全部逃出，判定成功；否则把新折点 $(x_0-x_{\text{add}},\ \dots)$ 压入队首。

由于每天至多新增一个折点、每个折点至多被弹出一次，单次可行性判定为 $O(N)$ 。外层二分 $\log A_1 \approx 20$ 次，总复杂度 $O(N \log A_1)$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

ll N;
vector<ll> A, B, C;

// 判断是否能让 m 个小孩全部逃出
bool func(ll m) {
    if (m <= 0) return true;
    ll sa = 0, sb = 0;        // 整体线性掩码：真实值 = sa*x + sb + dot.y
    deque<pll> dots;          // 折点 (x, y)，按 x 递增
    dots.push_back({m, 0});   // 初始：只有 x = m 一个点，值 0

    auto evaldot = [&](const pll &p) -> ll {
        return sa * p.first + sb + p.second;
    };
    auto slope = [&](const pll &l, const pll &r) -> ll {
        ll dy = r.second - l.second;
        ll dx = r.first - l.first;
        assert(dx > 0 && dy % dx == 0);
        return dy / dx;
    };

    for (ll di = 0; di < N; di++) {
        // 转移一：整体加上 A_i - B_i * x
        sb += A[di];
        sa -= B[di];

        // 从后端（x 较大一侧）裁掉真实值为负的段
        while (true) {
            if (dots.empty()) break;
            pll p1 = dots.back();
            if (evaldot(p1) >= 0) break;
            dots.pop_back();
            if (dots.empty()) break;
            pll p2 = dots.back();
            if (evaldot(p2) < 0) continue;
            ll ta = slope(p2, p1);
            assert(sa + ta != 0);
            ll xadd = evaldot(p2) / (-(sa + ta));  // 与 y=0 的交点（向下取整）
            if (xadd > 0) dots.push_back({p2.first + xadd, p2.second + ta * xadd});
            break;
        }
        // 从前端（x 较小一侧）裁掉真实值为负的段
        while (true) {
            if (dots.empty()) break;
            pll p1 = dots.front();
            if (evaldot(p1) >= 0) break;
            dots.pop_front();
            if (dots.empty()) break;
            pll p2 = dots.front();
            if (evaldot(p2) < 0) continue;
            ll ta = slope(p1, p2);
            assert(sa + ta != 0);
            ll xadd = evaldot(p2) / (sa + ta);
            if (xadd > 0) dots.push_front({p2.first - xadd, p2.second - ta * xadd});
            break;
        }
        if (dots.empty()) return false;  // 没有任何可行的剩余人数

        // 转移二：削去左端斜率 >= C_i 的段
        while (dots.size() > 1) {
            ll s = sa + slope(dots[0], dots[1]);
            if (s >= C[di]) dots.pop_front();
            else break;
        }
        // 左端接一段斜率为 C_i 的段，直到值降为 0（整数向下取整）
        ll xcadd = evaldot(dots[0]) / C[di];
        if (xcadd >= dots[0].first) return true;  // 能延伸到 x=0，即全部逃出
        if (xcadd > 0) {
            dots.push_front({dots[0].first - xcadd,
                             dots[0].second - (C[di] - sa) * xcadd});
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        cin >> N;
        A.resize(N); B.resize(N); C.resize(N);
        for (ll i = 0; i < N; i++) cin >> A[i] >> B[i] >> C[i];
        ll ok = 0, ng = A[0] + 1;   // 上界：活过第 1 天的小孩最多 A[0] 个
        while (ok + 1 < ng) {
            ll mid = (ok + ng) / 2;
            if (func(mid)) ok = mid;
            else ng = mid;
        }
        cout << ok << '\n';
    }
    return 0;
}

复杂度分析

单次可行性判定： $O(N)$ （每天至多新增一个折点，每个折点至多被删除一次）。
总体：二分 $O(\log A_1)$ 轮，每轮 $O(N)$ ，故单个测试用例 $O(N\log A_1)$ ；所有测试用例 $\sum N \le 3\times 10^5$ ，完全可行。
空间复杂度： $O(N)$ （折点数量）。