AtCoder Beginner Contest 447 题解

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

AtCoder Beginner Contest 447 题解

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

比赛概览

本场整体难度中等。A、B 是签到级的模拟题；C 的关键是把字符串按非 A 字符分解，将问题化为"分段 A 的个数差绝对值求和"；D 是一道经典的"在串中取尽量多互不相交的 ABC 子序列"贪心；E 利用 $2$ 的幂边权特有的"最大编号边决定权值大小"性质，配合并查集从大到小贪心；F 是带度数约束的最长路径树形 DP，容易在细节上出错；G 是全场最难的一题，综合了前后缀 top- $k$ 、变更表和线段树。区分度主要体现在 E、F、G，这三题值得重点掌握。

A - Seats 2

题目链接：https://atcoder.jp/contests/abc447/tasks/abc447_a

题目大意

$N$ 个座位排成一排，每个座位最多坐一人，且相邻的两个座位不能同时有人。判断能否坐下 $M$ 个人。 $1 \le N, M \le 100$ 。

思路

关键观察：为了避免相邻冲突，最优的坐法必然是"隔一个坐一个"，即坐在第 $1, 3, 5, \dots$ 号座位上。因此最多能坐下的人数就是 $\lceil N/2 \rceil$ 。

更形式化地，把座位两两分组 $(1,2), (3,4), \dots$ ，每一组至多坐一个人；当 $N$ 为奇数时，最后一个座位单独成组，也可以坐一个人。所以座位总数 $N$ 最多支持 $\left\lceil \dfrac{N}{2} \right\rceil$ 个人。

若 $M \le \lceil N/2 \rceil$ ，则把第 $1, 3, \dots, 2M-1$ 个座位全部坐人即可，它们两两不相邻，可行，输出 Yes；
否则无论怎么安排都会出现相邻两人，输出 No。

判定条件 $M \le \lceil N/2 \rceil$ 可以写成不带除法的整数比较： $2M - 1 \le N$ 。

易错点：注意 $N$ 为偶数时 $\lceil N/2 \rceil = N/2$ ，为奇数时是 $(N+1)/2$ ；用 $2M-1 \le N$ 可以直接覆盖两种情况，避免浮点误差。

参考代码

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

int main() {
    int n, m;
    cin >> n >> m;
    cout << (2 * m - 1 <= n ? "Yes" : "No") << '\n';
}

n, m = map(int, input().split())
print("Yes" if 2 * m - 1 <= n else "No")

复杂度分析

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

B - mpp

题目链接：https://atcoder.jp/contests/abc447/tasks/abc447_b

题目大意

给定只含小写字母的字符串 $S$ ，删除 $S$ 中所有"出现次数最多的字符"（若并列最多则全部删除），按原顺序输出剩余字符。

思路

直接按题意模拟即可：

用大小为 $26$ 的频率数组统计每个字母在 $S$ 中出现的次数；
求出最大出现次数 $mx$ ；
再扫描一遍 $S$ ，把出现次数不等于 $mx$ 的字符按原顺序拼接输出。

易错点：一定要把所有达到最大次数的字符全部删除（如样例 mississippi 中 i 与 s 各出现 4 次，两个都要删），而不是只删其中一个；同时，若最大次数就是唯一值，可能所有字符都被删除，此时应输出空串（如样例 atcoder）。

参考代码

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

int main() {
    string s;
    cin >> s;
    int cnt[26] = {};
    for (char c : s) cnt[c - 'a']++;
    int mx = 0;
    for (int i = 0; i < 26; i++) mx = max(mx, cnt[i]);
    string t;
    for (char c : s)
        if (cnt[c - 'a'] != mx) t += c;
    cout << t << '\n';
}

s = input()
cnt = {c: s.count(c) for c in s}
mx = max(cnt.values())
print("".join(c for c in s if cnt[c] != mx))

复杂度分析

时间复杂度： $O(|S| + 26)$
空间复杂度： $O(26)$

C - Insert and Erase A

题目链接：https://atcoder.jp/contests/abc447/tasks/abc447_c

题目大意

给定两个由大写字母组成的字符串 $S$ 和 $T$ （长度均不超过 $3 \times 10^5$ ）。可以对 $S$ 进行任意多次（按任意顺序）以下两种操作：

在 $S$ 的任意位置插入一个字符 A；
删除 $S$ 中的一个字符 A。

判断能否把 $S$ 变成 $T$ ，若能则输出所需的最小总操作次数，否则输出 $-1$ 。

思路

关键观察 1：非 A 字符的相对顺序是"不变式"。 无论插入还是删除，都只增删字符 A，其他字符只是被拼接回原顺序，所以它们之间的相对顺序永远不变。设 $S'$ 为 $S$ 去掉所有 A 后得到的子序列， $T'$ 同理。若 $S' \ne T'$ ，则永远不可能把 $S$ 变成 $T$ ，答案直接为 $-1$ 。

关键观察 2：每个"夹在非 A 字符之间的 A 块"是独立可调的。 把 $S$ 按非 A 字符切开，统计每一段里 A 的个数，得到一个序列 $A_S$ 。例如 $S = \texttt{ABAAACAA}$ ，则 $S' = \texttt{BC}$ ， $A_S = (1, 3, 2)$ 。对 $T$ 同样定义 $A_T$ （两者长度均为 $|S'| + 1$ ；若 $S'$ 为空串，则 $A_S = (|S|)$ ）。

一次操作的效果恰好是：

插入一个 A：某个 $A_S(i)$ 加 $1$ ；
删除一个 A：某个 $A_S(i)$ 减 $1$ 。

并且反过来，对任意 $i$ ，都可以在一步内让 $A_S(i)$ 增/减 $1$ ，同时不改变 $S'$ 、也不影响其他块。

结论：若 $S' = T'$ ，最小操作次数为

\sum_{i=1}^{|S'|+1} \left| A_S(i) - A_T(i) \right| .

因为每个块互不影响，把第 $i$ 块的 A 数量从 $A_S(i)$ 调到 $A_T(i)$ 恰好需要 $\left|A_S(i) - A_T(i)\right|$ 次操作；调整完成后 $S$ 与 $T$ 的非 A 子序列相同、各块 A 数也相同，故 $S = T$ 。

边界与易错点：两字符串可能全是 A（此时 $S'$ 、 $T'$ 为空，仍需比较 $A_S(1)$ 与 $A_T(1)$ ）；差值总和最大不超过 $|S| + |T|$ ，需要用 long long 存储。

参考代码

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

// 返回 (去掉所有 A 后的子序列, 每段 A 的个数)
pair<string, vector<long long>> decompose(const string& s) {
    string t;
    vector<long long> v;
    long long cnt = 0;
    for (char c : s) {
        if (c == 'A') {
            cnt++;
        } else {
            t += c;
            v.push_back(cnt);
            cnt = 0;
        }
    }
    v.push_back(cnt);
    return {t, v};
}

int main() {
    string s, t;
    cin >> s >> t;
    auto [ss, sv] = decompose(s);
    auto [ts, tv] = decompose(t);
    if (ss != ts) {
        cout << -1 << '\n';
        return 0;
    }
    long long ans = 0;
    for (size_t i = 0; i < sv.size(); i++) ans += llabs(sv[i] - tv[i]);
    cout << ans << '\n';
}

复杂度分析

时间复杂度： $O(|S| + |T|)$
空间复杂度： $O(|S| + |T|)$

D - Take ABC 2

题目链接：https://atcoder.jp/contests/abc447/tasks/abc447_d

题目大意

给定由 A、B、C 组成的字符串 $S$ （ $|S| \le 10^6$ ）。每次操作选取三个下标 $i < j < k$ ，满足 $S_i = \texttt A$ 、 $S_j = \texttt B$ 、 $S_k = \texttt C$ ，删除这三个字符，剩余字符按原顺序左移拼接。求最多能进行的操作次数。

思路

问题转化：删除操作不改变剩余字符的相对顺序，因此任意一系列操作都等价于在原串 $S$ 中选出若干组互不相交的下标组，每组按顺序构成子序列 ABC。反过来，任意一组互不相交的 ABC 子序列也可以一组一组地删掉（删掉别的字符不影响本组三个字符的相对顺序）。所以题目等价于：求 $S$ 中互不相交的 ABC 子序列的最大数量。

贪心算法：从左到右扫描 $S$ ，维护三个计数器 $a, b, c$ ，分别表示"当前可用的 A 的个数""已配好、等待 C 来配对的 AB 的个数""已经配成的 ABC 的个数"。对每个字符：

若是 A： $a \leftarrow a + 1$ （新增一个可用的 A）；
若是 B： $b \leftarrow \min(a,\ b+1)$ （尽量把新的 B 与一个空闲 A 配对，但配对总数不能超过可用 A 数）；
若是 C： $c \leftarrow \min(b,\ c+1)$ （尽量完成一组 ABC，但不能超过已配好的 AB 数）。

最终答案就是 $c$ 。

为什么贪心是对的：设扫描完前 $i$ 个字符后贪心计数为 $A_i, B_i, C_i$ 。任取一个可行解，设它在前 $i$ 个字符中作为 A/B/C 被使用的个数分别为 $a_i, b_i, c_i$ 。因为每个被使用的 B 之前必须有一个被使用的 A，每个被使用的 C 之前必须有一个被使用的 B，所以恒有 $a_i \ge b_i \ge c_i$ 。下面归纳证明对任意 $i$ 都有

A_i \ge a_i,\qquad B_i \ge b_i,\qquad C_i \ge c_i .

若 $S_i = \texttt A$ ：贪心必取， $A_i = A_{i-1}+1 \ge a_{i-1}+1 \ge a_i$ ，其余两个量不变且 $b_i = b_{i-1}$ 、 $c_i = c_{i-1}$ ；
若 $S_i = \texttt B$ ：若贪心没增加 $b$ ，说明此时 $B_{i-1} = A_{i-1}$ ，于是 $B_i = A_{i-1} \ge a_{i-1} \ge b_i$ ；若贪心增加了 $b$ ，则 $B_i = B_{i-1}+1 \ge b_{i-1}+1 \ge b_i$ ；
若 $S_i = \texttt C$ ：同理， $C_i = \min(B_{i-1}, C_{i-1}+1)$ ，若被卡住则 $C_i = B_{i-1} \ge b_{i-1} \ge c_i$ ，否则 $C_i = C_{i-1}+1 \ge c_{i-1}+1 \ge c_i$ 。

因此 $C_N \ge c_N$ ，即贪心得到的 ABC 数不少于任意可行解；同时贪心过程本身可以按"每个 B 配最早的空闲 A、每个 C 配一个待配 AB"构造出一组真实的互不相交子序列，所以它也是可行的。两者结合，贪心恰好等于最大值。

边界情况：字符串很短、甚至不含某个字符时， $a, b, c$ 始终被 $\min$ 限制，不会出现"计数器超过实际可用数量"的情况，程序自然输出 $0$ 。

参考代码

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

int main() {
    string s;
    cin >> s;
    int a = 0, b = 0, c = 0;
    for (char ch : s) {
        if (ch == 'A') {
            a++;
        } else if (ch == 'B') {
            b = min(a, b + 1);
        } else { // 'C'
            c = min(b, c + 1);
        }
    }
    cout << c << '\n';
}

s = input()
a = b = c = 0
for i in s:
    if i == "A":
        a += 1
    elif i == "B":
        b = min(a, b + 1)
    else:
        c = min(b, c + 1)
print(c)

复杂度分析

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

E - Divide Graph

题目链接：https://atcoder.jp/contests/abc447/tasks/abc447_e

题目大意

给定简单连通无向图 $G$ ，有 $N$ 个顶点、 $M$ 条边（ $2 \le N \le 2 \times 10^5$ ）。第 $i$ 条边的代价为 $2^i$ 。选择一些边删除，使得 $G$ 恰好变成 $2$ 个连通块，求删除边总代价的最小值（对 $998244353$ 取模输出；注意是"最小化真实值后再取模"，而不是最小化模数）。

思路

第一步：把"恰好 2 个连通块"放宽成"不连通"。 所有边权都是正数，多删边只会让代价变大。若一个方案产生了 $\ge 3$ 个连通块，那么保留部分被删掉的边把其中一些连通块合并回去（仍保持不连通，比如只留 2 个块），删除代价会更小。因此最优解必然恰好有 2 个连通块。于是问题等价于：

选择尽量多（权值和最大）的边保留，使得保留的子图不连通；答案 $=$ 总权值 $-$ 保留边权值和。

第二步：利用 $2$ 的幂边权的特殊性质。 设两个不同的边集 $X, Y$ ，令 $x$ 为它们对称差中的最大编号。若 $x \in Y$ ，则

\sum_{i \in X} 2^i \le \sum_{i=1}^{x-1} 2^i = 2^x - 2 < 2^x \le \sum_{i \in Y} 2^i .

也就是说，两个方案权值的大小关系完全由"对称差中的最大编号边"决定：谁拥有这条边，谁的权值和就更大。这立刻启发我们从大到小贪心：

从 $i = M$ 到 $1$ 依次考虑边 $i$ 。若把它加入当前保留边集不会使图变连通（即加入后仍然不连通），就保留它；否则就删除它（把代价 $2^i$ 累加进答案）。

第三步：用并查集实现。 处理到边 $i$ 时：

若两端点已经在同一个并查集分量里：这条边是"回路边"，加入它不会改变连通性，永远可以保留；
否则它连接两个不同的分量：若当前分量数 $> 2$ ，合并这两个分量并保留（合并后仍不连通）；若当前分量数恰为 $2$ ，则这条边会把两个分量连成整个图，必须删除，累加代价。

这样保留下来的子图恰好有 $2$ 个连通块，删除边代价之和即为答案（取模输出）。

贪心正确性（交换论证）：设 $A$ 为最优保留边集， $B$ 为贪心得到的保留边集，取对称差中最大编号 $x$ 。

若 $x \in A \setminus B$ ：贪心在第 $x$ 步拒绝边 $x$ ，说明此时贪心已有的高编号边 $B_{>x}$ 加上边 $x$ 已经连通。由于 $x$ 是对称差中最大编号， $B_{>x} \subseteq A$ ，故 $B_{>x} \cup \{x\} \subseteq A$ 是连通的，与 $A$ 不连通矛盾；
若 $x \in B \setminus A$ ：则 $B$ 在 $\le x$ 部分至少含 $2^x$ ，而 $A$ 在 $\le x$ 部分至多含 $2^x - 2$ ，且二者在 $> x$ 的部分完全相同，于是 $B$ 的权值和严格大于 $A$ ，与 $A$ 的最优性矛盾。

所以 $A = B$ ，贪心最优。

实现要点： $2^i$ 可能很大，用递推维护模数下的幂： $\text{cost}[0] = 2$ ， $\text{cost}[i] = \text{cost}[i-1] \cdot 2 \bmod 998244353$ 。

参考代码

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

const long long MOD = 998244353;

struct DSU {
    vector<int> p;
    DSU(int n) : p(n) { iota(p.begin(), p.end(), 0); }
    int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
    bool same(int a, int b) { return find(a) == find(b); }
    void unite(int a, int b) { p[find(a)] = find(b); }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> u(m), v(m);
    vector<long long> cost(m);
    for (int i = 0; i < m; i++) {
        cin >> u[i] >> v[i];
        --u[i]; --v[i];
        cost[i] = (i == 0 ? 2 : cost[i - 1] * 2 % MOD);  // 2^(i+1) mod MOD
    }
    DSU dsu(n);
    long long ans = 0;
    int cnt = n;  // 当前并查集分量数
    for (int i = m - 1; i >= 0; i--) {
        if (!dsu.same(u[i], v[i])) {  // 连接两个不同分量
            if (cnt > 2) {            // 合并后仍不连通，保留
                dsu.unite(u[i], v[i]);
                --cnt;
            } else {                  // 这条边会把两个分量连起来，必须删除
                ans = (ans + cost[i]) % MOD;
            }
        }
        // 端点在同一分量：回路边，保留（不产生任何代价）
    }
    cout << ans << '\n';
}

复杂度分析

时间复杂度： $O(M \alpha(N))$ （ $\alpha$ 为反阿克曼函数，可视为常数）
空间复杂度： $O(N + M)$

F - Centipede Graph

题目链接：https://atcoder.jp/contests/abc447/tasks/abc447_f

题目大意

定义"长度为 $k$ 的蜈蚣图"：先取一条含 $k$ 个顶点的路径，再给路径上每个顶点各挂两个新的叶子，共 $3k$ 个顶点。给定一棵 $N$ 个顶点的树 $T$ （ $3 \le N \le 2 \times 10^5$ ，多组询问， $\sum N \le 2 \times 10^5$ ），求最大的 $x$ ，使得长度为 $x$ 的蜈蚣图是 $T$ 的子图。

思路

问题转化：蜈蚣图的"主干"（spine）是一条 $x$ 个顶点的路径；主干端点内部度数为 $3$ （一条主干边 $+$ 两片叶子），主干内部顶点度数为 $4$ （两条主干边 $+$ 两片叶子）。由于子图不要求诱导，只要树中对应顶点有足够多的邻居即可。因此题目等价于：

在树 $T$ 中找一条最长的路径，使得该路径的两个端点度数 $\ge 3$ ，其余顶点度数 $\ge 4$ ； $x$ 就是这条路径的顶点数。

先处理 $x = 1$ ：长度为 $1$ 的蜈蚣图只是一个度数为 $2$ 的顶点挂两片叶子，即一条 3 顶点路径。任何 $N \ge 3$ 的树都含有一个度数 $\ge 2$ 的顶点，所以答案至少为 $1$ 。

树形 DP：任取一个根（如顶点 $1$ ），对每个顶点 $v$ 计算

D[v] = \text{从 } v \text{ 出发、沿子树方向向下的最长"主干链"长度}.

其中"主干链"定义为：以 $v$ 为链头，向一个儿子方向逐层下行，最后终止于某个端点；除链头 $v$ 和链尾（端点）外，链上每个顶点都要求度数 $\ge 4$ ，链尾要求度数 $\ge 3$ 。链头 $v$ 本身不预设约束—— $v$ 到底是整条路径的端点还是内部顶点，由组合时决定。

自底向上计算。设 $\text{deg}(v)$ 为 $v$ 在树中的度数。对 $v$ 的每个儿子 $u$ ，把 $v$ 接到 $u$ 的链头之前，得到"贡献"：

\text{contrib}(u) = \begin{cases} 1 + D[u], & \text{deg}(u) \ge 4 \ (\text{链继续下延，}u\text{ 作为内部顶点}),\\[2mm] 2, & \text{deg}(u) = 3 \ (\text{链在 }u\text{ 处终止，}u\text{ 作为端点}),\\[2mm] 0, & \text{deg}(u) \le 2. \end{cases}

于是

D[v] = \max\left(\ \text{deg}(v) \ge 3\ ?\ 1 : 0,\quad \max_{u \in \text{ch}(v)} \text{contrib}(u)\ \right).

（当 $\text{deg}(u) \ge 4$ 时 $1 + D[u] \ge 2$ ，自动覆盖了" $u$ 作端点"的选项；只有当 $\text{deg}(u) = 3$ 时才需要单独给出 $2$ 。）

统计答案：任意一条路径总有一个"最高点"（两个端点在其子树中的 LCA），我们以它为合并中心。对每个顶点 $v$ ，考虑两种角色：

$v$ 是整条路径的端点：需要 $\text{deg}(v) \ge 3$ ，候选值就是 $D[v]$ ；
$v$ 是整条路径的内部顶点（两条分支都向下）：需要 $\text{deg}(v) \ge 4$ ，在儿子中取最大的两个贡献 $\text{top}_1 \ge \text{top}_2$ ，候选值为 $\text{top}_1 + \text{top}_2 - 1$ （ $v$ 被数了两次，减 $1$ ）。

最终答案为 $\max(1,\ \text{所有候选值})$ 。

注意的易错点：端点只要有度数 $\ge 3$ 就可以继续把主干往下延（端点除一条主干边外只需两片叶子，多余的邻居不影响），所以 $D[v]$ 的延伸条件是对儿子要求度数 $\ge 4$ ，而不是对 $v$ 自己要求度数 $\ge 4$ ； $v$ 自己的度数限制在组合成整条路径时才起作用（作端点需 $\ge 3$ ，作内部顶点需 $\ge 4$ ）。写 DP 时最容易在这个细节上出错。

官方题解还给出另一种视角（方法 2）：称一棵树为"好树"，若其叶子度数 $\ge 3$ 、非叶子度数 $\ge 4$ ，则答案等于所有极大好子树的直径；两种方法都是 $O(N)$ 。下面给出方法 1 的完整实现。

参考代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> q;
    while (q--) {
        int n;
        cin >> n;
        vector<vector<int>> g(n);
        for (int i = 0; i < n - 1; i++) {
            int a, b;
            cin >> a >> b;
            --a; --b;
            g[a].push_back(b);
            g[b].push_back(a);
        }
        vector<int> deg(n);
        for (int i = 0; i < n; i++) deg[i] = (int)g[i].size();

        // 以 0 为根，BFS 得到拓扑顺序（保证子节点排在父节点之后）
        vector<int> par(n, -1), order;
        order.reserve(n);
        par[0] = 0;
        vector<int> st{0};
        for (size_t idx = 0; idx < st.size(); idx++) {
            int v = st[idx];
            order.push_back(v);
            for (int u : g[v])
                if (par[u] == -1) {
                    par[u] = v;
                    st.push_back(u);
                }
        }

        vector<int> D(n, 0);  // 从 v 出发向下的最长主干链
        int best = 0;
        for (int idx = n - 1; idx >= 0; idx--) {  // 自底向上
            int v = order[idx];
            int dval = (deg[v] >= 3 ? 1 : 0);     // v 单独作端点
            int top1 = 0, top2 = 0;               // 儿子贡献的前两大
            for (int u : g[v]) {
                if (u == par[v]) continue;
                int contrib = (deg[u] >= 4 ? 1 + D[u] : (deg[u] >= 3 ? 2 : 0));
                if (contrib > top1) {
                    top2 = top1;
                    top1 = contrib;
                } else if (contrib > top2) {
                    top2 = contrib;
                }
                dval = max(dval, contrib);
            }
            D[v] = dval;
            // v 作端点：需要度数 >= 3
            if (deg[v] >= 3) best = max(best, D[v]);
            // v 作内部顶点（两条分支）：需要度数 >= 4
            if (deg[v] >= 4 && top2 >= 2) best = max(best, top1 + top2 - 1);
        }
        cout << max(1, best) << '\n';  // x = 1 永远可行
    }
}

复杂度分析

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

G - Div. 1 & Div. 2

题目链接：https://atcoder.jp/contests/abc447/tasks/abc447_g

题目大意

有 $N$ 道题，第 $i$ 道题的难度为 $i$ 、类别为 $K_i$ 、趣味度为 $A_i$ （ $6 \le N \le 10^5$ ）。选择 6 道题，编号从小到大记为 $i_1 < i_2 < \cdots < i_6$ ，要求：

$i_1, i_2, i_3, i_4$ 用作 Div.2，类别两两不同；
$i_3, i_4, i_5, i_6$ 用作 Div.1，类别两两不同。

求 6 道题趣味度之和的最大值；若无合法选择，输出 $-1$ 。

思路

这是本场最难的一题。核心结构是：6 个位置分成"前两个、中间两个（两边共用）、后两个"。类别约束等价于：中间两个 $i_3, i_4$ 类别不同，前两个与后两个的类别都彼此不同、且都不等于 $i_3, i_4$ 的类别。

第 1 步：维护前后缀的"top-4 不同类别"集合。 对一个问题集合，定义其"趣味度最高的 4 个不同类别题目"：从趣味度最高的题开始，依次贪心选取，只要该类别未被选取就加入，直到凑满 4 道（若不足 4 个类别，用趣味度 $-\infty$ 的虚拟题补齐）。记

$L_i$ ：问题 $1..i$ 的 top-4 不同类别集合；
$R_i$ ：问题 $i..N$ 的 top-4 不同类别集合。

它们可以 $O(N)$ 递推：每加入一道题 $(k, a)$ ，若类别 $k$ 已在集合中则把该类别对应的趣味度取 $\max$ ，否则把 $(a, k)$ 插入并重新挑出 top-4。注意比较时按趣味度从大到小、同趣味度按类别编号从大到小排序，这样合并操作是良定义且结合的。

第 2 步：枚举中间分隔点。 枚举 $i_4$ 的类别 $c$ 。固定 $c$ 后，定义 $M(x)$ 为" $i_3 = x$ 时， $i_1, i_2$ 的最佳趣味度之和"，其中 $i_1, i_2 < x$ ，且 $K_{i_1}, K_{i_2}, K_x, c$ 两两不同（若不存在取 $-\infty$ ）。

当 $c$ 不限定时的基准值： $\text{ori}[x] = A_x + (L_{x-1}$ 去掉类别 $K_x$ 后最大的两个 $)$ ；
只有当 $c$ 恰好等于"去掉 $K_x$ 后前两名"的某个类别时， $M(x)$ 才需要替换成次优组合。对每个 $x$ ，这样的 $c$ 至多 2 个，因此可以把所有"变更点"预存到 change[c] 表中，全表总大小为 $O(N)$ 。

第 3 步：后缀部分。 对固定的 $i_4$ ， $i_5, i_6$ 从 $R_{i_4+1}$ 中选取：先去掉类别 $K_{i_4}$ ，再根据 $i_3$ 的类别 $K_x$ 去掉对应类别，取剩下的前两名。记 $f(i_4, d)$ 为"已知 $i_3$ 类别为 $d$ 时， $i_4, i_5, i_6$ 的最佳趣味度之和"。

第 4 步：线段树合并。 用一棵线段树维护所有 $x$ 的 $(M(x), K_x)$ ，每个节点存其区间内 top-4 不同类别的最大 $M$ 值（合并就是两个 top-4 集合的并再取 top-4）。对每个类别 $c$ ：

把 change[c] 中所有位置 $x$ 的 $M(x)$ 更新到线段树；
对每个满足 $K_{i_4} = c$ 的 $i_4$ ：查询线段树上区间 $[0, i_4)$ 的 top-4 作为 $i_3$ 候选（跳过类别等于 $c$ 的）；对每个候选 $p$ ，从 $R_{i_4+1}$ 去掉类别 $K_{i_4}$ 与 $p$ 的类别后取前两名作为 $i_5, i_6$ ，累加更新答案；
撤销本轮的变更。

为什么只需要 top-4（Fact 1）：固定 $i_4$ 后， $f(i_4, d)$ 只取 3 种值，由 $d$ 是否是后缀（去掉 $K_{i_4}$ 后）前两名的类别决定—— $d$ 等于第一名类别、等于第二名类别、或其他。把候选 $i_3$ 按这三类分组，每类只需最优的 $x$ ；而线段树的 top-4 不同类别中必然包含每一类的代表（第三类"其他"在 top-4 中至少有两个位置）。所以枚举 top-4 不会漏掉最优解。

为什么总复杂度是 $O(N \log N)$ （Fact 2）：每个位置 $x$ 的 $M(x)$ 随 $c$ 变化至多 2 次（只发生在 $c$ 等于前两名类别时），所以全部变更的个数是 $O(N)$ ，线段树点更新总次数 $O(N)$ 。总复杂度 $O(N \log N)$ 。

实现注意： $A_i$ 最多 $10^9$ 、共 6 道，最大总和约 $6 \times 10^9$ ；虚拟题的趣味度取一个远大于该上界的负数（如 $-10^{18}$ ），避免累加时溢出；线段树节点用定长数组而非 vector，以减小常数。

参考代码

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

using ll = long long;
const ll INF = (ll)1e18;  // 虚拟题的趣味度（远小于真实值）
const int SZ = 4;

// 一个 top-4 集合：按趣味度降序（同值按类别降序）存放，至多 SZ 个不同类别
struct Node {
    pair<ll, int> p[SZ];
};

Node e() {
    Node r;
    for (int i = 0; i < SZ; i++) r.p[i] = {-INF, -i - 1};
    return r;
}

Node op(const Node& a, const Node& b) {
    pair<ll, int> tmp[2 * SZ];
    for (int i = 0; i < SZ; i++) tmp[i] = a.p[i];
    for (int i = 0; i < SZ; i++) tmp[SZ + i] = b.p[i];
    sort(tmp, tmp + 2 * SZ, greater<pair<ll, int>>());
    Node r;
    int used = 0;
    for (int i = 0; i < 2 * SZ && used < SZ; i++) {
        bool dup = false;
        for (int j = 0; j < used; j++)
            if (r.p[j].second == tmp[i].second) dup = true;
        if (!dup) r.p[used++] = tmp[i];
    }
    for (; used < SZ; used++) r.p[used] = {-INF, -used - 1};
    return r;
}

Node add(const Node& s, int k, ll a) {  // 向集合中插入 (a, k)
    pair<ll, int> tmp[SZ + 1];
    for (int i = 0; i < SZ; i++) tmp[i] = s.p[i];
    tmp[SZ] = {a, k};
    sort(tmp, tmp + SZ + 1, greater<pair<ll, int>>());
    Node r;
    int used = 0;
    for (int i = 0; i < SZ + 1 && used < SZ; i++) {
        bool dup = false;
        for (int j = 0; j < used; j++)
            if (r.p[j].second == tmp[i].second) dup = true;
        if (!dup) r.p[used++] = tmp[i];
    }
    for (; used < SZ; used++) r.p[used] = {-INF, -used - 1};
    return r;
}

Node single(int k, ll a) {
    Node r = e();
    r.p[0] = {a, k};
    return r;
}

struct SegTree {
    int size;
    vector<Node> data;
    SegTree(const vector<Node>& init) {
        int n = (int)init.size();
        size = 1;
        while (size < n) size <<= 1;
        data.assign(2 * size, e());
        for (int i = 0; i < n; i++) data[size + i] = init[i];
        for (int i = size - 1; i >= 1; i--) data[i] = op(data[2 * i], data[2 * i + 1]);
    }
    void set(int pos, Node val) {
        pos += size;
        data[pos] = val;
        for (pos >>= 1; pos; pos >>= 1) data[pos] = op(data[2 * pos], data[2 * pos + 1]);
    }
    Node prod(int l, int r) {  // 查询 [l, r) 的 top-4
        Node resL = e(), resR = e();
        l += size;
        r += size;
        while (l < r) {
            if (l & 1) resL = op(resL, data[l++]);
            if (r & 1) resR = op(data[--r], resR);
            l >>= 1;
            r >>= 1;
        }
        return op(resL, resR);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> k(n);
    vector<ll> a(n);
    vector<vector<int>> ls(n);  // 每个类别对应的所有下标
    for (int i = 0; i < n; i++) {
        cin >> k[i] >> a[i];
        --k[i];
        ls[k[i]].push_back(i);
    }

    vector<Node> pre(n + 1), suf(n + 1);
    pre[0] = e();
    suf[n] = e();
    for (int i = 0; i < n; i++) pre[i + 1] = add(pre[i], k[i], a[i]);
    for (int i = n - 1; i >= 0; i--) suf[i] = add(suf[i + 1], k[i], a[i]);

    vector<ll> ori(n);                 // 基准 M(x)
    vector<Node> init(n);
    vector<vector<pair<int, ll>>> change(n);  // change[c]: c 变化时 M(x) 的更新
    for (int i = 0; i < n; i++) {
        pair<ll, int> cand[3];         // pre[i] 去掉类别 k[i] 后的前三名
        int used = 0;
        for (int t = 0; t < SZ && used < 3; t++)
            if (pre[i].p[t].second != k[i]) cand[used++] = pre[i].p[t];
        ori[i] = a[i] + cand[0].first + cand[1].first;
        init[i] = single(k[i], ori[i]);
        for (int j = 0; j < 2; j++) {          // c 恰等于前两名之一时
            if (cand[j].second < 0) continue;  // 虚拟题，跳过
            ll now = ori[i] - cand[j].first + cand[2].first;
            change[cand[j].second].push_back({i, now});
        }
    }

    SegTree st(init);
    ll ans = -1;
    for (int c = 0; c < n; c++) {
        for (auto [x, v] : change[c]) st.set(x, single(k[x], v));  // 应用变更
        for (int i4 : ls[c]) {
            pair<ll, int> cand[3];        // suf[i4+1] 去掉类别 k[i4] 后的前三名
            int used = 0;
            for (int t = 0; t < SZ && used < 3; t++)
                if (suf[i4 + 1].p[t].second != k[i4]) cand[used++] = suf[i4 + 1].p[t];
            Node best = st.prod(0, i4);   // 候选 i3 的 top-4
            for (int t = 0; t < SZ; t++) {
                auto p = best.p[t];
                if (p.second == k[i4]) continue;  // 类别与 i4 相同，非法
                ll now = p.first + a[i4];          // M(x) + A[i4]
                if (cand[0].second == p.second)
                    now += cand[1].first + cand[2].first;
                else if (cand[1].second == p.second)
                    now += cand[0].first + cand[2].first;
                else
                    now += cand[0].first + cand[1].first;
                ans = max(ans, now);
            }
        }
        for (auto [x, v] : change[c]) st.set(x, single(k[x], ori[x]));  // 撤销
    }
    cout << ans << '\n';
}

复杂度分析

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