AtCoder Beginner Contest 424 题解

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

AtCoder Beginner Contest 424 题解

项目	内容
比赛时间	2025-09-20
比赛链接	https://atcoder.jp/contests/abc424
题目数量	A–G 共 7 题

比赛概览

本场 ABC424 整体难度中等偏基础：A、B 是纯签到，C 是把技能依赖关系建模成图后做可达性计数，D 是经典的逐行状态压缩 DP，E 是"二分答案 + 分段计数"（操作次数高达 $10^9$ ，直接模拟不可行），F 是把"不相交弦"转化成合法括号序列后用线段树维护，G 是把偶像-歌曲的匹配可行性刻画成前缀和约束后再做 DP。较有区分度的是 E、F、G 三题：E 的关键是观察贪心过程对"长度 $\ge L$ 的木棍数量"的影响呈三段式；F 的关键是"圆周剪开变区间、不相交弦对应合法括号序列"；G 的关键是 Gale-Ryser 型的可行性条件。建议重点关注这三题背后的思想。

A - Isosceles

题目链接：https://atcoder.jp/contests/abc424/tasks/abc424_a

题目大意

已知一个面积为正的三角形，三条边长为 $a,b,c$ ，判断它是否为等腰三角形。输入一行三个整数，输出 Yes 或 No。数据保证三角形存在（无需自己检查三角不等式）。

思路

等腰三角形定义为"至少有两条边相等"，因此判断三个等号 $a=b$ 、 $b=c$ 、 $c=a$ 中是否至少一个成立即可。

需要注意的唯一细节是：等边三角形（三边都相等）也是等腰三角形，所以三个条件用"或"连接即可，样例 3 正是这种情况。由于题目保证这样的三角形一定存在，不需要检查"两边之和大于第三边"等条件。

复杂度上没有任何顾虑，直接判断即可。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    if (a == b || b == c || c == a) cout << "Yes\n";
    else cout << "No\n";
    return 0;
}

官方题解同时给出了 Python 实现：

a, b, c = map(int, input().split())
print("Yes" if a == b or b == c or c == a else "No")

复杂度分析

时间复杂度： $O(1)$
空间复杂度： $O(1)$

B - Perfect

题目链接：https://atcoder.jp/contests/abc424/tasks/abc424_b

题目大意

有 $N$ （ $\le 10$ ）个人和 $M$ （ $\le 10$ ）道题。按时间顺序发生 $K$ 个事件，第 $i$ 个事件表示"人 $A_i$ 解出了题 $B_i$ "，同一事件不会出现两次。求所有解出全部 $M$ 道题的人，并按他们完成全部题目的先后顺序输出编号；若无人完成全部题目则什么都不输出。

思路

事件本身已经按时间顺序给出，因此只要顺次处理每个事件，就能自然地得到"完成全部题目"的时间顺序。

维护数组 $cnt[i]$ 表示第 $i$ 个人目前解出的题目数量。处理事件 $(a,b)$ 时：

令 $cnt[a] \gets cnt[a] + 1$ ；
若此时恰好 $cnt[a] == M$ ，说明人 $a$ 在此刻刚完成全部题目，把他的编号追加到答案序列末尾。

由于一个人一旦完成全部题目，之后就不会"再次完成"，且每个事件只被处理一次，所以每个人至多被追加一次；答案序列的顺序正是各人完成全部题目的时间顺序。

正确性由以下两点保证：

没有任何事件之外的人/题被解出，因此 $cnt[a]$ 只在对应事件时增加；
"完成全部题目"只可能发生在某人解出第 $M$ 道题的瞬间，而这一瞬间必然对应某个事件的处理过程。

官方题解还讨论了一个朴素做法（每步扫描所有人的 $cnt$ ），复杂度 $O(KNM)$ ，在本数据范围下也可通过；但 $O(K)$ 的做法更简洁，下面给出。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, M, K;
    cin >> N >> M >> K;
    vector<int> cnt(N, 0);
    vector<int> ans;
    for (int i = 0; i < K; i++) {
        int a, b;
        cin >> a >> b;
        --a;
        if (++cnt[a] == M) ans.push_back(a + 1);
    }
    for (int i = 0; i < (int)ans.size(); i++) {
        if (i) cout << ' ';
        cout << ans[i];
    }
    cout << '\n';
    return 0;
}

Python 实现（ $O(K)$ 版本）：

n, m, k = map(int, input().split())
cnt = [0] * n
ans = []
for _ in range(k):
    a, b = map(int, input().split())
    a -= 1
    cnt[a] += 1
    if cnt[a] == m:
        ans.append(a + 1)
print(*ans)

复杂度分析

时间复杂度： $O(K)$
空间复杂度： $O(N)$

C - New Skill Acquired

题目链接：https://atcoder.jp/contests/abc424/tasks/abc424_c

题目大意

有 $N$ （ $\le 2\times 10^5$ ）个技能。给定 $N$ 对整数 $(A_i,B_i)$ ：若 $(A_i,B_i)=(0,0)$ ，表示技能 $i$ 一开始已经掌握；否则技能 $i$ 在技能 $A_i$ 或技能 $B_i$ 中至少一个已掌握时才能被学会。求最终能掌握的技能总数（含一开始就掌握的）。

思路

关键转化：把技能之间的依赖关系建成有向图。

对每个非初始掌握的技能 $i$ ，加两条边：

$A_i \to i$ （含义：一旦学会了 $A_i$ ，技能 $i$ 就可以被学会）；
$B_i \to i$ （同理）。

再引入一个虚拟技能 $0$ 作为"初始已掌握"的源点：对所有 $(A_i,B_i)=(0,0)$ 的初始技能 $i$ ，加边 $0 \to i$ 。

在这个图中，"技能 $i$ 最终可学会"当且仅当"从 $0$ 出发可以到达 $i$ "。这是因为：

可学会的技能集合是封闭的：若某技能 $i$ 的前提之一（ $A_i$ 或 $B_i$ ）已被学会，则 $i$ 也会被学会，这正对应图中沿出边传播；
从 $0$ 出发可达的顶点集合恰好是"包含所有初始技能的最小封闭集"，也就是最终能掌握的技能全体。

因此从 $0$ 做一遍 BFS/DFS 即可。实现时注意：

自环是允许的（例如 $(A_i,B_i)=(i,i)$ ），用 visited 数组防止重复入队即可；
$N$ 可达 $2\times 10^5$ ，递归 DFS 可能爆栈，用 BFS（或显式栈）更稳妥。

答案即从 $0$ 可达的 $1..N$ 中顶点数（要减去虚拟顶点 $0$ 本身）。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<vector<int>> G(N + 1);
    for (int i = 1; i <= N; i++) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(i);
        G[b].push_back(i);  // (0,0) 时两次都连到 0，等价于 0 -> i
    }

    vector<char> ok(N + 1, 0);
    queue<int> q;
    q.push(0);
    ok[0] = 1;
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (int nv : G[v]) {
            if (!ok[nv]) {
                ok[nv] = 1;
                q.push(nv);
            }
        }
    }
    cout << accumulate(ok.begin(), ok.end(), 0) - 1 << '\n';  // 减去虚拟技能 0
    return 0;
}

官方题解的 Python 实现（DFS 版本）：

import sys
sys.setrecursionlimit(10**9)

N = int(input())
G = [[] for _ in range(N + 1)]
for i in range(1, N + 1):
    a, b = map(int, input().split())
    G[a].append(i)
    G[b].append(i)

ok = [0] * (N + 1)
ok[0] = 1

def dfs(v):
    for vv in G[v]:
        if not ok[vv]:
            ok[vv] = 1
            dfs(vv)

dfs(0)
print(sum(ok) - 1)

复杂度分析

时间复杂度： $O(N)$ （边数不超过 $2N$ ）
空间复杂度： $O(N)$

D - 2x2 Erasing 2

题目链接：https://atcoder.jp/contests/abc424/tasks/abc424_d

题目大意

有一个 $H$ 行 $W$ 列（ $2 \le H,W \le 7$ ）的网格，. 为白格、# 为黑格。每次可以把一个黑格涂成白格，问最少涂白多少个黑格，才能使网格中不存在全由黑格组成的 $2\times 2$ 子方块（即任意 $2\times 2$ 内至少有一个白格）。共有 $T$ （ $\le 100$ ）组测试数据。

思路

$W \le 7$ 是关键：一行只有 $2^W \le 128$ 种状态，可以逐行做状态压缩 DP。

用 $W$ 位二进制数表示一行的最终状态：第 $j$ 位为 $1$ 表示该行第 $j$ 列最终是黑格。

先做预处理：对任意两行的状态 $x,y$ ，判断"上一行状态 $x$ 、当前行状态 $y$ "是否会在某相邻两列上形成全黑 $2\times2$ 。即是否存在列 $c$ 使得两行在第 $c$ 、 $c+1$ 列上同时为黑：

((x \mathbin{>>} c) \,\&\, 3) = 3 \quad \text{且} \quad ((y \mathbin{>>} c) \,\&\, 3) = 3

只要存在这样的 $c$ ， $(x,y)$ 这个"状态对"就不合法，记为不可转移。

接下来处理每一行。设第 $i$ 行初始的黑格集合为 $\text{mask}_i$ 。由于只能把黑格涂成白格，最终第 $i$ 行的状态 $y$ 必须是 $\text{mask}_i$ 的子集（ $y\ \&\ \sim \text{mask}_i = 0$ ），把 $\text{mask}_i$ 变成 $y$ 需要涂白 $y \oplus \text{mask}_i$ 中为 $1$ 的位数，即

\text{cost}(i, y) = \operatorname{popcount}(y \oplus \text{mask}_i).

定义 $dp[y]$ 为：处理完当前这一行后，当前行的最终状态为 $y$ ，且到目前为止处理过的所有行都不含全黑 $2\times2$ 时的最小总涂白数。转移时枚举上一行状态 $x$ 与当前行状态 $y$ ，要求 $(x,y)$ 合法：

dp'[y] = \min_{x:\ (x,y)\ \text{合法}} \big(dp[x] + \operatorname{popcount}(y \oplus \text{mask}_i)\big).

为统一处理第一行，可以在最上方虚拟一行全白（状态 $0$ ，代价 $0$ ），即初始 $dp[0]=0$ 、其余为 $+\infty$ 。因为全白行不可能与任何行构成全黑 $2\times2$ ，第一行的转移就自动正确了。

最终答案是处理完所有 $H$ 行后 $\min_y dp[y]$ 。

为什么正确：任意一组合法涂白方案都唯一对应一行行状态序列 $y_1,\dots,y_H$ （ $y_i$ 为 $\text{mask}_i$ 的子集），相邻两行不构成全黑 $2\times2$ 恰好等价于全局没有全黑 $2\times2$ ；DP 枚举了所有可能的状态序列并取总代价最小者，所以得到的就是最小涂白数。另外，涂白操作互不影响，不同行的决策可以独立枚举，这正是能逐行 DP 的原因。

复杂度：每行枚举"上一行状态 $\times$ 当前行状态"共 $O(2^W \cdot 2^W) = O(4^W)$ ，故每组测试 $O(H\cdot 4^W)$ ，总复杂度 $O(T\cdot H \cdot 4^W) \le 100 \times 7 \times 2^{14} \approx 1.15\times 10^7$ ，完全可行。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int T;
    cin >> T;
    const int INF = 1e9;
    while (T--) {
        int H, W;
        cin >> H >> W;
        vector<string> s(H);
        for (int i = 0; i < H; i++) cin >> s[i];

        int K = 1 << W;
        // allow[x][y]: 上一行状态 x、当前行状态 y 不构成全黑 2x2
        vector<vector<char>> allow(K, vector<char>(K, 1));
        for (int x = 0; x < K; x++)
            for (int y = 0; y < K; y++)
                for (int c = 0; c < W - 1; c++)
                    if (((x >> c) & 3) == 3 && ((y >> c) & 3) == 3) {
                        allow[x][y] = 0;
                        break;
                    }

        vector<int> dp(K, INF);
        dp[0] = 0;  // 虚拟的全白行
        for (int i = 0; i < H; i++) {
            int mask = 0;
            for (int j = 0; j < W; j++)
                if (s[i][j] == '#') mask |= (1 << j);

            vector<int> ndp(K, INF);
            for (int cur = 0; cur < K; cur++) {
                if ((cur | mask) != mask) continue;  // 只能把黑涂白
                int cost = __builtin_popcount((unsigned)(cur ^ mask));
                for (int pre = 0; pre < K; pre++)
                    if (allow[pre][cur] && dp[pre] != INF)
                        ndp[cur] = min(ndp[cur], dp[pre] + cost);
            }
            dp.swap(ndp);
        }
        cout << *min_element(dp.begin(), dp.end()) << '\n';
    }
    return 0;
}

复杂度分析

时间复杂度： $O(T \cdot H \cdot 4^W)$ ，其中 $4^W \le 2^{14}$
空间复杂度： $O(2^W)$

E - Cut in Half

题目链接：https://atcoder.jp/contests/abc424/tasks/abc424_e

题目大意

袋中有 $N$ 根木棍，长度分别为 $A_1,\dots,A_N$ 。重复 $K$ 次操作：取出当前最长的一根木棍，切成相等的两半放回袋中。操作 $K$ 次后袋中共有 $N+K$ 根木棍，求其中第 $X$ 长的木棍长度。共有 $T$ （ $\le 10^5$ ）组测试数据， $\sum N \le 10^5$ ， $K,X \le 10^9$ ，答案允许 $10^{-9}$ 的相对误差。

思路

$K$ 最大 $10^9$ ，直接模拟不可行，需要用二分答案把问题转化成可高效计算的判定。

观察 1（贪心是确定的）：每一步都切当前最长的一根，而同长度的木棍之间可以互换，因此最终的多重集（每种长度各有多少根）与"具体切哪根"无关，是完全确定的。

观察 2（考虑"长度 $\ge L$ 的木棍数量"）：设 $f(L)$ 为操作 $K$ 次后长度 $\ge L$ 的木棍总数。 $f(L)$ 关于 $L$ 单调不增，且 $X$ -th 最长正是"最大的 $L$ 使得 $f(L) \ge X$ "，因此可以二分 $L$ 。问题转化为：给定 $L$ ，快速求出 $f(L)$ 。

如何计算 $f(L)$ ：先看单根长度为 $a$ 的木棍。若把它一直切下去，直到所有碎段的长度都落在 $[L, 2L)$ ，则它贡献

c(a) = 2^{\lfloor \log_2(a/L) \rfloor}

段长度 $\ge L$ 的木棍，所需操作数为 $c(a)-1$ 。（因为切一刀段数加一，从 $1$ 段变到 $2^k$ 段共 $2^k-1$ 刀。）

再分析贪心全程对 $f(L)$ 的影响，整个过程可以分成三段：

第一阶段（切长度 $\ge 2L$ 的木棍）：只要存在长度 $\ge 2L$ 的木棍，贪心就一定会切它，因为它是全局最长。把一根长度 $\ge 2L$ 的木棍切成两段后，两段都仍 $\ge L$ ，于是 $f(L)$ 增加 1。把所有木棍都切到 $< 2L$ 恰好需要
$M = \sum_{i:\ A_i \ge L} \big(c(A_i) - 1\big)$
刀。
第二阶段（切长度在 $[L,2L)$ 的木棍）：若 $M < K$ ，剩余的操作只能切 $[L,2L)$ 的木棍，每刀消灭一段长度 $\ge L$ 的木棍， $f(L)$ 减少 1。
第三阶段（切长度 $< L$ 的木棍）：不再影响 $f(L)$ 。

因此：

f(L) = \begin{cases} \operatorname{cnt}_0 + K, & K \le M,\\[2mm] \max\big(\Sigma C - (K - M),\ 0\big), & K > M, \end{cases}

其中 $\operatorname{cnt}_0 = \#\{i : A_i \ge L\}$ ， $\Sigma C = \sum_{i:\ A_i\ge L} c(A_i)$ 。第一种情况： $K$ 刀全在第一阶段，每刀使 $f$ 加一，故 $f = \operatorname{cnt}_0 + K$ 。第二种情况：第一阶段结束后 $f = \operatorname{cnt}_0 + M = \Sigma C$ ，之后每刀减一。

为什么正确：第一阶段内"每刀切的一定是长度 $\ge 2L$ 的木棍"是由贪心"切全局最长"保证的，因此 $K \le M$ 时必然全部处于第一阶段；而 $f(L)$ 随 $L$ 单调不增，二分单调性成立。

实现细节：

$k = \lfloor \log_2(a/L) \rfloor$ 用 log2l 计算并对浮点误差做小幅修正； $L$ 很小时 $k$ 可能很大，用 $60$ 封顶——因为此时单个 $c(a)$ 就远超 $X$ ，必然落在第一种情况，封顶不影响结果。
所有长度都是 $a_i / 2^k$ 形式，在 64 位浮点中精确可表示；计数用 __int128 防止溢出。
二分范围取 $(0, \max A]$ ，迭代约 100 次即可达到远超 $10^{-9}$ 的精度。

参考代码

#include <bits/stdc++.h>
using namespace std;

bool ok(long double L, long long K, long long X, const vector<long long>& A) {
    __int128 sumC = 0, M = 0;  // M: 把所有碎段都切到 < 2L 所需的操作数
    long long cnt0 = 0;        // 初始长度 >= L 的木棍数
    for (long long a : A) {
        if ((long double)a >= L) {
            cnt0++;
            long long k = (long long)floorl(log2l((long double)a / L));
            k = max(0LL, min(k, 60LL));
            // 修正浮点误差：保证 a / 2^k >= L 且 a / 2^(k+1) < L
            while (k > 0 && (long double)a / (long double)(1ULL << k) < L) k--;
            while (k < 60 && (long double)a / (long double)(1ULL << (k + 1)) >= L) k++;
            __int128 c = (__int128)1 << k;
            sumC += c;
            M += c - 1;
        }
    }
    if (K <= M) return cnt0 + K >= X;  // 全部处于第一阶段
    return sumC - (K - M) >= X;        // 进入第二阶段
}

int main() {
    int T;
    cin >> T;
    cout << setprecision(20);
    while (T--) {
        long long N, K, X;
        cin >> N >> K >> X;
        vector<long long> A(N);
        long long mx = 0;
        for (int i = 0; i < N; i++) {
            cin >> A[i];
            mx = max(mx, A[i]);
        }
        long double lo = 0, hi = (long double)mx;
        for (int it = 0; it < 100; it++) {
            long double mid = (lo + hi) / 2;
            if (ok(mid, K, X, A)) lo = mid;
            else hi = mid;
        }
        cout << (double)lo << '\n';
    }
    return 0;
}

复杂度分析

时间复杂度：每组测试 $O(N \log A_{\max})$ （二分约 100 次），总计 $O\big((\sum N) \cdot \log A_{\max}\big)$
空间复杂度： $O(N)$

F - Adding Chords

题目链接：https://atcoder.jp/contests/abc424/tasks/abc424_f

题目大意

圆周上有 $N$ （ $\le 10^6$ ）个点，按顺时针编号 $1,\dots,N$ 。有 $Q$ （ $\le 3\times 10^5$ ）个查询，按顺序处理：连接点 $A_i$ 和 $B_i$ （保证 $A_i<B_i$ ），若该弦与任何已画出的弦相交则不画。数据保证 $2Q$ 个端点两两不同。对每个查询输出这次是否真的画出了弦（Yes/No）。

思路

第一步：剪开圆周变区间。 在点 $1$ 与点 $N$ 之间把圆周剪开并展成直线，于是每条弦对应一个区间 $[A_i,B_i]$ （ $A_i<B_i$ ）。两条弦在圆周上相交，当且仅当对应的两个区间"交叉"（部分重叠）：设已画区间为 $[L,R]$ ，则 $[A,B]$ 与它交叉当且仅当

A < L < B < R \quad \text{或} \quad L < A < R < B .

第二步：用括号序列刻画"不相交"。 对每条已画弦 $[L,R]$ ，在 $L$ 处放 (（记 $+1$ ）、在 $R$ 处放 )（记 $-1$ ）。由于已画弦之间互不相交，整个序列上的括号结构是"良匹配"的。

关键结论：新弦 $[A,B]$ 不与任何已画弦相交，当且仅当内部区间 $(A+1,\,B-1)$ 上的括号子串是一个合法的括号序列，即

区间内所有括号值之和为 $0$ ；
区间内任意前缀和不小于 $0$ （最小前缀和 $\ge 0$ ，其中"空前缀"算 $0$ ）。

直观解释：若内部是合法括号序列，说明 $A$ 与 $B$ 之间恰好由若干完整嵌套的已画弦填满，新弦可以直接包住它们，不会与任何弦交叉；反之，若内部出现"多出的 ("或"多余的 )"，则该弦一定与某个已画弦交叉。例如已画 $[1,4]$ 后查询 $[2,5]$ ，内部 $(2,5)$ 中含有位置 $4$ 上的 )，区间和为 $-1 \ne 0$ ，因此不能画——确实 $[1,4]$ 与 $[2,5]$ 相交。

第三步：线段树维护。 需要支持单点加（在 $A$ 处 $+1$ 、 $B$ 处 $-1$ ）以及区间查询"区间和"与"区间最小前缀和"。用线段树，每个节点维护两个值：

\begin{aligned} \text{sum} &= \text{sum}_L + \text{sum}_R,\\ \text{minpref} &= \min(\text{minpref}_L,\ \text{sum}_L + \text{minpref}_R). \end{aligned}

叶子节点的值为 $v$ 时， $\text{sum}=v$ 、 $\text{minpref}=\min(0,v)$ （包含空前缀）。

对查询 $[A,B]$ ，取内部区间 $[A+1, B-1]$ 查询 $(S,\text{mn})$ ：若 $S=0$ 且 $\text{mn}\ge 0$ 则画出（并更新两端点），否则不画。

关于"剪开"的正确性：所有弦都满足 $A_i<B_i$ ，即弦的区间不跨过点 $1/N$ 之间的剪口，因此圆周上的相交关系与直线区间上的交叉关系完全一致。

官方题解还提到一个随机化（哈希）做法，作为参考：弦 $I$ 与弦 $J$ 相交当且仅当 $I$ 恰好包含 $J$ 的奇数个端点。给每条弦的两个端点赋相同的随机值，则区间 $[A,B]$ 内所有端点值的异或为 $0$ 当且仅当它不与任何已画弦相交（每根已画弦贡献 $0$ 或 $2$ 个端点则异或为 $0$ ）。出错概率至多 $Q/2^B$ ，可忽略不计。但线段树解法是确定性的，下面给出。

参考代码

#include <bits/stdc++.h>
using namespace std;

// 支持单点加、区间查询(区间和, 区间最小前缀和)的线段树
struct SegTree {
    int n;
    vector<long long> sum, pref;  // pref 包含空前缀（恒 <= 0）
    SegTree(int N) : n(N), sum(2 * N, 0), pref(2 * N, 0) {}
    void add(int pos, long long d) {  // 0-indexed
        int i = pos + n;
        sum[i] += d;
        pref[i] = min(0LL, sum[i]);
        for (i >>= 1; i; i >>= 1) {
            sum[i] = sum[i << 1] + sum[i << 1 | 1];
            pref[i] = min(pref[i << 1], sum[i << 1] + pref[i << 1 | 1]);
        }
    }
    pair<long long, long long> query(int l, int r) {  // 闭区间 [l,r], 0-indexed
        if (l > r) return {0, 0};
        long long ls = 0, lp = 0, rs = 0, rp = 0;
        l += n; r += n;
        while (l <= r) {
            if (l & 1) { lp = min(lp, ls + pref[l]); ls += sum[l]; l++; }
            if (!(r & 1)) { rp = min(pref[r], sum[r] + rp); rs = sum[r] + rs; r--; }
            l >>= 1; r >>= 1;
        }
        return {ls + rs, min(lp, ls + rp)};
    }
};

int main() {
    int N, Q;
    cin >> N >> Q;
    int sz = 1;
    while (sz < N) sz <<= 1;
    SegTree seg(sz);
    while (Q--) {
        int A, B;
        cin >> A >> B;  // 1-indexed，且 A < B
        // 内部区间 (A+1, B-1)，0-indexed 即 [A, B-2]
        auto [tot, mn] = seg.query(A, B - 2);
        if (tot == 0 && mn >= 0) {  // 内部是合法括号序列
            seg.add(A - 1, +1);
            seg.add(B - 1, -1);
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }
    return 0;
}

复杂度分析

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

G - Set list

题目链接：https://atcoder.jp/contests/abc424/tasks/abc424_g

题目大意

有 $N$ （ $\le 100$ ）位偶像，偶像 $i$ 最多能跳 $A_i$ 首歌。有 $M$ （ $\le 100$ ）首候选歌曲，第 $j$ 首需要 $B_j$ 位偶像上台跳舞（每首歌每名偶像至多跳一次），无论谁跳都能获得兴奋度 $C_j$ 。Takahashi 要选择若干首歌（每首至多选一次）并安排偶像上台，在不超过每位偶像上限的前提下，最大化所选歌曲的兴奋度之和。

思路

这是一个二部图上的 $b$ -匹配问题：左边是"歌曲"（需要恰好 $B_j$ 位不同的偶像），右边是"偶像"（容量 $A_i$ ），任意歌曲与任意偶像之间都有边。直接求解匹配不现实，好在图是完全二部图，可行性可以化简成很漂亮的条件。

第一步：可行性刻画（Gale-Ryser 型条件）。

假设选中的歌曲已按所需偶像数从大到小排好序： $b_1 \ge b_2 \ge \cdots \ge b_k$ 。可以证明：安排存在当且仅当对任意 $1 \le k' \le k$ 都有

\sum_{j=1}^{k'} b_j \;\le\; \sum_{i=1}^{N} \min(A_i, k').

记右侧为 $R_{k'} = \sum_i \min(A_i, k')$ 。

必要性：前 $k'$ 首（所需偶像数最多的 $k'$ 首）歌曲合计需要 $\sum_{j=1}^{k'} b_j$ 个"偶像—歌曲"槽位；而在 $k'$ 首歌中，偶像 $i$ 至多参与 $\min(A_i, k')$ 首，因此所有偶像提供的槽位总数恰好是 $R_{k'}$ 。槽位不够则不可能安排。
充分性：对 $k$ 归纳。 $k=1$ 显然成立。取 $b_1$ 最大的那首歌，从剩余容量最大的 $b_1$ 位偶像中各"扣掉"一次参与次数，然后对剩下的 $k-1$ 首歌归纳。用容量最大的偶像去满足需求最大的歌，剩余容量 $A'_i$ 仍然满足归纳前提（这需要一点细致推导，但可以验证：扣掉之后 $\sum_i \min(A'_i, k'-1) \ge \sum_{j'=2}^{k} b_{j'}$ ），从而可以继续分配。

第二步：DP 求最大兴奋度。

关键观察： $R_{k'} = \sum_i \min(A_i, k')$ 只依赖于 $k'$ ，与选了哪些歌无关，可以预先算好。

把所有歌曲按 $B$ 从大到小排序（ $B_1 \ge B_2 \ge \cdots \ge B_M$ ）。定义

dp[k][s] = \text{已处理到某前缀时，选出 } k \text{ 首歌、} B \text{ 值之和恰为 } s \text{，且所有前缀约束都满足的最大兴奋度}，

其中"所有前缀约束"指：把这 $k$ 首歌按 $B$ 降序排列后，任意 $k' \le k$ 的前缀和不超过 $R_{k'}$ 。

转移（对每首歌 $(b,c)$ ，倒序枚举 $k$ 与 $s$ 以复用数组）：

dp[k][s] = \max\big(dp[k][s],\ dp[k-1][s-b] + c\big),

前提是 $dp[k-1][s-b]$ 合法且 $s \le R_k$ 。为什么只需检查 $s \le R_k$ 这一条新约束？因为按 $B$ 降序处理时，新加入的这首歌是当前选中集合里 $B$ 最小的一首，它只会引入"第 $k$ 个前缀和 $\le R_k$ "这一条新约束，其余更短的前缀约束已由 $dp[k-1][s-b]$ 的合法性保证。

答案： $\displaystyle \max_{0\le k\le M}\ \max_{0\le s \le NM} dp[k][s]$ 。

为什么正确：可行性刻画把"能否安排"转化成了只依赖于所选歌曲 $B$ 值降序前缀和的约束，于是选歌问题变成了纯组合优化；DP 状态 $(k,s)$ 恰好枚举了所有满足前缀约束的（ $B$ 值多重集），兴奋度则取转移中的最大值，因此不会遗漏最优解。

复杂度：状态数 $O(M \cdot NM)$ （ $NM \le 10^4$ ），每个状态由前一首歌转移，总复杂度 $O(M^2 \cdot NM) = O(NM^3) \le 100^2 \times 10^4 = 10^8$ ，常数很小，足以通过。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    vector<pair<int, long long>> song(M);  // (B_j, C_j)
    for (int i = 0; i < M; i++) cin >> song[i].first >> song[i].second;

    // 按所需偶像数降序排序
    sort(song.begin(), song.end(),
         [](const auto& x, const auto& y) { return x.first > y.first; });

    // R[k] = sum_i min(A_i, k)：k 首歌时偶像能提供的总槽位上限
    vector<long long> R(M + 1, 0);
    for (int k = 1; k <= M; k++)
        for (int a : A) R[k] += min(a, k);

    int NM = N * M;
    const long long NEG = -(1LL << 60);
    vector<vector<long long>> dp(M + 1, vector<long long>(NM + 1, NEG));
    dp[0][0] = 0;

    for (auto [b, c] : song) {
        for (int k = M; k >= 1; k--) {
            for (int s = NM; s >= b; s--) {
                if (dp[k - 1][s - b] == NEG || s > R[k]) continue;
                dp[k][s] = max(dp[k][s], dp[k - 1][s - b] + c);
            }
        }
    }

    long long ans = 0;
    for (int k = 0; k <= M; k++)
        for (int s = 0; s <= NM; s++)
            ans = max(ans, dp[k][s]);
    cout << ans << '\n';
    return 0;
}

复杂度分析

时间复杂度： $O(NM^3)$ （ $N,M \le 100$ ，约 $10^8$ 次简单运算）
空间复杂度： $O(M \cdot NM)$