AtCoder Beginner Contest 442 题解

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

AtCoder Beginner Contest 442 题解

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

比赛概览

本场整体难度中等偏易。A、B 是纯粹的入门签到题；C 是结合度数的组合计数；D 考察"相邻交换对前缀和影响的局部性"，是一个值得掌握的经典技巧；E 是极角排序的练习，难点在于把同方向的怪物并块，以及顺时针扫过环时的"绕回"处理；F 的关键是把"行、列都满足前缀白"的染色条件转化为一个非递增序列，再跑 $O(N^2)$ 的序列 DP；G 则是大数量下的贪心与分组合并，利用 6、3、2 件同类物品分别恰好凑成重量 6 的倍数关系，把三类物品统一打包成重量 6 后再贪心，需要一点数论直觉。其中 D、F、G 较有区分度，值得重点掌握。

A - Count .

题目链接：https://atcoder.jp/contests/abc442/tasks/abc442_a

题目大意

给定一个由小写英文字母组成的字符串 $S$ （长度 $1\le |S|\le 10$ ）。定义每个字符的"点"数为：i 或 j 贡献 $1$ 点，其余字母贡献 $0$ 点。求 $S$ 中所有字符点数之和。

思路

题目把"点"的定义包装了一下，本质就是统计 i 和 j 出现的次数。因为只有这两种字符各贡献 $1$ ，答案就是

\text{ans}=\text{cnt}(S,\text{`i`})+\text{cnt}(S,\text{`j`}).

实现时用一层循环遍历即可，也可以直接用 std::count。注意长度上限只有 $10$ ，没有任何复杂情况；把 i、j 记成 $1$ 点，其余记成 $0$ 点，累加即可。

参考代码

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

int main() {
    string s;
    cin >> s;
    int ans = 0;
    for (char c : s) {
        if (c == 'i' || c == 'j') ans++;
    }
    cout << ans << '\n';
}

复杂度分析

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

B - Music Player

题目链接：https://atcoder.jp/contests/abc442/tasks/abc442_b

题目大意

Takahashi 的音乐播放器初始音量为 $0$ 、处于停止状态。依次执行 $Q$ 个操作（ $1\le Q\le 2\times 10^5$ ），第 $i$ 个操作为：

$A_i=1$ ：音量加 $1$ ；
$A_i=2$ ：若当前音量 $\ge 1$ 则音量减 $1$ ，否则不变；
$A_i=3$ ：若停止则播放，若播放则停止。

每次操作结束后，判断"正在播放且音量 $\ge 3$ "，是则输出 Yes，否则输出 No。

思路

直接模拟。用两个变量维护状态：

$x$ ：当前音量；
$y$ ： $0$ 表示停止， $1$ 表示播放。

三种操作的转移为：

A_i=1:\ x\leftarrow x+1;

A_i=2:\ x\leftarrow \max(x-1,\ 0);

A_i=3:\ y\leftarrow 1-y.

注意操作 $2$ 在音量 $0$ 时是"什么都不做"，不会把音量减成负数。每次操作后输出 Yes 当且仅当 $x\ge 3$ 且 $y=1$ 。

由于 $Q\le 2\times 10^5$ ，音量 $x$ 至多增长到 $Q$ ，不会溢出，无需额外处理。逐行模拟、逐行输出即可。

参考代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int x = 0, y = 0;  // x: volume, y: 0=stopped, 1=playing
    int q;
    cin >> q;
    while (q--) {
        int a;
        cin >> a;
        if (a == 1) {
            x++;
        } else if (a == 2) {
            if (x > 0) x--;
        } else {  // a == 3
            y = 1 - y;
        }
        cout << (x >= 3 && y == 1 ? "Yes" : "No") << '\n';
    }
}

复杂度分析

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

C - Peer Review

题目链接：https://atcoder.jp/contests/abc442/tasks/abc442_c

题目大意

有 $N$ 位研究者（编号 $1\sim N$ ）和 $M$ 对利益冲突（无向边）。一篇论文的审稿人必须是三位互不相同的研究者：他们都不能是作者本人，且每位审稿人都与作者没有利益冲突。（审稿人之间是否冲突没有要求。）

对每位作者 $i$ （ $1\le i\le N$ ），求可行的审稿人三元组个数。 $N\le 2\times 10^5$ ， $M\le 2\times 10^5$ 。

思路

关键观察：条件只约束"每个审稿人与作者无冲突"，审稿人之间没有任何约束，因此作者 $i$ 的所有可行审稿人构成一个集合，答案就是这个集合的大小为 $3$ 的组合数。

记 $\deg_i$ 为与研究者 $i$ 有冲突的人数（即度数），则与 $i$ 无冲突、且不是 $i$ 本人的研究者数量为

C_i=(N-1)-\deg_i.

于是答案为

\binom{C_i}{3}=\frac{C_i(C_i-1)(C_i-2)}{6}.

当 $C_i<3$ 时上式自然为 $0$ （分子含 $0$ ），无需特判。

实现：初始化 $C_i=N-1$ ，读入每条边 $(a,b)$ 时令 $C_a,C_b$ 各减 $1$ ，然后 $O(1)$ 计算每个 $\binom{C_i}{3}$ 。

易错点：

$N$ 最大 $2\times 10^5$ ， $\binom{N}{3}\approx 1.33\times 10^{15}$ 超出 int，必须用 long long。
输出顺序是 $i=1,\dots,N$ ，之间用空格分隔。

参考代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<ll> c(n, n - 1);  // c[i] = number of researchers with no conflict with i
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        c[a - 1]--;
        c[b - 1]--;
    }
    for (int i = 0; i < n; i++) {
        ll ans = c[i] * (c[i] - 1) * (c[i] - 2) / 6;
        cout << ans << " \n"[i == n - 1];
    }
}

复杂度分析

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

D - Swap and Range Sum

题目链接：https://atcoder.jp/contests/abc442/tasks/abc442_d

题目大意

给定长度为 $N$ 的序列 $A$ ，依次处理 $Q$ 个操作（ $Q\le 5\times 10^5$ ）：

1 x：交换 $A_x$ 与 $A_{x+1}$ ；
2 l r：输出 $\sum_{i=l}^{r}A_i$ 。

思路

直接每次查询都扫一遍显然不可行，标准做法是维护前缀和。令

S_i=A_1+A_2+\cdots+A_i\quad (S_0=0),

则区间查询就是 $S_r-S_{l-1}$ ， $O(1)$ 得到。难点在于交换操作如何高效维护 $S$ 。

关键观察：交换 $A_x$ 与 $A_{x+1}$ 时，前缀和数组只有一个位置会变化：

对 $i<x$ ： $S_i$ 只包含前 $x-1$ 个元素，与被交换的两个位置无关，不变；
对 $i\ge x+1$ ： $S_i$ 同时包含 $A_x$ 和 $A_{x+1}$ ，而 $A_x+A_{x+1}$ 在交换前后不变，因此 $S_i$ 也不变；
只有 $S_x=A_1+\cdots+A_x$ 会变，交换后 $A_x$ 变成原来的 $A_{x+1}$ ，故

S_x^{\text{new}}=S_{x-1}+A_x^{\text{new}}.

所以在交换操作中，只需把数组 $A$ 中这两个元素交换，再更新一个前缀和位置 $S_x$ 即可。这样每个操作都是 $O(1)$ 。

易错点：

很多人误以为交换会影响 $S_{x+1}$ 及之后的一整段前缀和，从而 $O(N)$ 更新。事实上由于两元素之和不变，之后全部不受影响，只有 $S_x$ 一处变化。
输入中的下标从 $1$ 开始，代码里先 --x、--l 转成 $0$ 下标。

参考代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    vector<int> a(n), s(n + 1);  // s[i] = A_1 + ... + A_i
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        s[i + 1] = s[i] + a[i];
    }
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int x;
            cin >> x;
            --x;
            swap(a[x], a[x + 1]);
            s[x + 1] = s[x] + a[x];  // only one prefix sum changes
        } else {
            int l, r;
            cin >> l >> r;
            --l;
            cout << s[r] - s[l] << '\n';
        }
    }
}

复杂度分析

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

E - Laser Takahashi

题目链接：https://atcoder.jp/contests/abc442/tasks/abc442_e

题目大意

平面上有 $N$ 个怪物，第 $i$ 个位于 $(X_i,Y_i)\ne(0,0)$ （允许重合、允许与原点共线）。Takahashi 站在原点，从眼睛里持续发射激光，面朝方向上的所有怪物会被瞬间摧毁。

Aoki 做 $Q$ 个互相独立的思想实验：初始面朝怪物 $A_j$ 的方向，然后顺时针旋转，在面朝怪物 $B_j$ 的方向时停下。问总共摧毁了多少个怪物（含 $A_j,B_j$ 方向上的全部怪物）。若 $A_j$ 与 $B_j$ 同方向，则不旋转。 $N,Q\le 2\times 10^5$ ， $|X_i|,|Y_i|\le 10^9$ 。

思路

第一步：极角排序

从原点看一个点 $(x,y)$ 的方向即其极角（自正 $x$ 轴逆时针量取，范围 $[0,360^\circ)$ ）。本题要处理的是"顺时针扫过哪些方向"，因此把怪物按极角降序排列：极角大的在前。这样顺时针旋转（极角递减）就等价于在这个降序排列中下标递增地往前走，走到底后绕回开头。

对两点极角比较，为避免浮点误差，采用"半平面分类 + 叉积"：

半平面分类：上半平面（ $y>0$ 或 $y=0$ 且 $x>0$ ）对应极角 $[0,180^\circ)$ ，排在前面；下半平面（其余）对应 $[180^\circ,360^\circ)$ ，排在后面。
同半平面内比较：对两点 $A=(x_1,y_1)$ 、 $B=(x_2,y_2)$ ，叉积

A\times B=x_1y_2-y_1x_2=|A||B|\sin(\theta_B-\theta_A).

同一半平面内极角差小于 $180^\circ$ ，因此 $\sin$ 的符号决定了 $\theta_B-\theta_A$ 的符号：叉积 $>0$ 说明 $A$ 的极角更小。

注意坐标可达 $\pm 10^9$ ，叉积最大约 $(10^9)^2=10^{18}$ ，必须用 long long 保存。

第二步：同方向并块

若多个怪物与原点共线且同向，它们的极角完全相同，会同时被摧毁。在排序后它们紧挨在一起，需要预处理每个位置所在"块"的左右端点：

$L_i$ ：与位置 $i$ 极角相同的最小下标；
$R_i$ ：与位置 $i$ 极角相同的最大下标。

$L_i,R_i$ 可以分别从左到右、从右到左各扫一遍求出：相邻两个点极角不同则新开一块。

第三步：回答查询

记 $a$ 所在块为 $[L_a,R_a]$ ， $b$ 所在块为 $[L_b,R_b]$ （均指降序排列中的下标）。顺时针从 $a$ 的方向扫到 $b$ 的方向，即从 $L_a$ 出发在降序排列中向前（下标增大）走，直到 $R_b$ ：

若 $L_a\le R_b$ ：路径不绕回，覆盖区间 $[L_a,R_b]$ ，摧毁怪物数为

R_b-L_a+1;

若 $L_a>R_b$ ：路径绕回一圈，覆盖 $[L_a,N-1]\cup[0,R_b]$ ，摧毁怪物数为

(N-L_a)+(R_b+1).

因为区间的两端恰好都是块边界，而每个块整体都在区间内，所以"怪物个数"就等于"位置个数"，无需再按方向去重。

正确性：降序排列下"向前走"恰好对应顺时针，且块内的怪物极角相同必然同时被摧毁； $L_a$ 是 $a$ 所在块的最前位置， $R_b$ 是 $b$ 所在块的最后位置，所以摧毁的方向集正是这两个块之间（含）的全部方向。

边界情况：

$A_j,B_j$ 同方向：此时 $L_a\le R_b$ 恒成立，答案为块大小，恰好对应"不旋转"。
两个点在相反方向（极角差 $180^\circ$ ）：它们分属两个半平面，不会误入同一块。
完全相同的坐标、共线同向的点：比较器双向都返回 false（叉积为 $0$ 且同半平面），会被并进同一块。

参考代码

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

struct Point {
    ll x, y;
};

ll cross(const Point& a, const Point& b) {
    return a.x * b.y - a.y * b.x;
}

// 半平面：0 为上半平面（极角 [0,180°)），1 为下半平面（[180°,360°)）
int half(const Point& p) {
    return (p.y < 0 || (p.y == 0 && p.x < 0)) ? 1 : 0;
}

// 比较极角：a 的极角是否严格小于 b 的极角
bool cmpAngle(const Point& a, const Point& b) {
    int ha = half(a), hb = half(b);
    if (ha != hb) return ha < hb;
    return cross(a, b) > 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    vector<Point> p(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i].x >> p[i].y;
    }

    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j) { return cmpAngle(p[i], p[j]); });
    reverse(ord.begin(), ord.end());  // 变为极角降序

    vector<int> pos(n);
    for (int i = 0; i < n; i++) pos[ord[i]] = i;

    // L[i], R[i]：位置 i 所在同方向块的下标区间 [L[i], R[i]]
    vector<int> L(n), R(n);
    L[0] = 0;
    for (int i = 1; i < n; i++) {
        L[i] = cmpAngle(p[ord[i]], p[ord[i - 1]]) ? i : L[i - 1];
    }
    R[n - 1] = n - 1;
    for (int i = n - 2; i >= 0; i--) {
        R[i] = cmpAngle(p[ord[i + 1]], p[ord[i]]) ? i : R[i + 1];
    }

    while (q--) {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        int la = L[pos[a]];
        int rb = R[pos[b]];
        if (la <= rb) {
            cout << rb - la + 1 << '\n';
        } else {
            cout << (n - la) + (rb + 1) << '\n';
        }
    }
}

复杂度分析

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

F - Diagonal Separation 2

题目链接：https://atcoder.jp/contests/abc442/tasks/abc442_f

题目大意

$N\times N$ 的网格，第 $i$ 行第 $j$ 列格子为白（.）或黑（#）。要求重涂若干格子，使得：

每一行存在 $k$ （ $0\le k\le N$ ），该行最左 $k$ 格为白、其余为黑；
每一列存在 $k$ （ $0\le k\le N$ ），该列最上 $k$ 格为白、其余为黑。

求满足条件所需的最小重涂格数。 $N\le 5000$ 。

思路

关键转化：把两个条件压成一个非递增序列

设第 $i$ 行白格数为 $A_i$ （ $0\le A_i\le N$ ）。行条件自动满足。第 $j$ 列的白格是哪些行？恰好是满足 $A_i\ge j$ 的行。列条件要求这些行必须是从上到下的连续前缀 $\{1,2,\dots,B_j\}$ 。对所有 $j$ 同时成立，这等价于

A_1\ge A_2\ge\cdots\ge A_N.

直观地说，所有白格必须构成一个"左上角台阶形"：行越往下，白格数不增加。

于是问题转化为：选一个非递增的整数序列 $(A_1,\dots,A_N)$ ， $0\le A_i\le N$ ，最小化每行重涂代价之和。

代价与 DP

对第 $i$ 行选 $A_i=j$ 时，要涂白前 $j$ 格里的 #，并把后 $N-j$ 格里的 . 涂黑。设 $pre_{i,j}$ 为第 $i$ 行前 $j$ 个字符中 # 的个数，则

D_{i,j}=pre_{i,j}+\bigl((N-j)-(pre_{i,N}-pre_{i,j})\bigr)=2\,pre_{i,j}+N-j-pre_{i,N}.

令 $dp_{i,j}$ 为处理完前 $i$ 行、第 $i$ 行取 $A_i=j$ 时的最小代价。由非递增性，第 $i-1$ 行的取值 $k$ 必须满足 $k\ge j$ ，因此

dp_{i,j}=D_{i,j}+\min_{j\le k\le N} dp_{i-1,k}.

对每一行预处理后缀最小值

mn_j=\min_{j\le k\le N}dp_{i-1,k},

则转移就是 $dp_{i,j}=D_{i,j}+mn_j$ ，一行 $O(N)$ ，总 $O(N^2)$ 。答案取 $\min_j dp_{N,j}$ 。实现时用滚动数组只保留上一行与当前行即可。

正确性：非递增序列与满足条件的染色方案一一对应；代价按行分解求和；DP 以"第 $i$ 行末尾值 $A_i$ "为状态、强制非递增约束并保留最优，最优子结构显然成立。

易错点：

$A_i$ 可以取 $0$ （整行黑）和 $N$ （整行白）， $j$ 要遍历 $[0,N]$ 。
$D_{i,j}$ 中"后 $N-j$ 格的 . 涂黑"容易漏算。

参考代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<string> s(n);
    for (auto& row : s) cin >> row;

    // dp[j]：上一行取 A = j 的最小代价
    vector<int> dp(n + 1, 0);

    for (int i = 0; i < n; i++) {
        // pre[j]：第 i 行前 j 个字符中 '#' 的个数
        vector<int> pre(n + 1, 0);
        for (int j = 0; j < n; j++) {
            pre[j + 1] = pre[j] + (s[i][j] == '#');
        }

        // mn[j] = min(dp[k]) for k >= j
        vector<int> mn(n + 1);
        mn[n] = dp[n];
        for (int j = n - 1; j >= 0; j--) {
            mn[j] = min(dp[j], mn[j + 1]);
        }

        vector<int> ndp(n + 1);
        for (int j = 0; j <= n; j++) {
            int cost = 2 * pre[j] + (n - j) - pre[n];  // D_{i,j}
            ndp[j] = cost + mn[j];
        }
        dp.swap(ndp);
    }

    cout << *min_element(dp.begin(), dp.end()) << '\n';
}

复杂度分析

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

G - Lightweight Knapsack

题目链接：https://atcoder.jp/contests/abc442/tasks/abc442_g

题目大意

有 $N$ 类物品，第 $i$ 类的重量 $W_i\in\{1,2,3\}$ 、价值 $V_i$ 、数量 $K_i$ （ $K_i\le 10^9$ ）。从全部 $K_1+\cdots+K_N$ 件中选取若干件，使总重量不超过 $C$ （ $C\le 2\times 10^9$ ），求最大总价值。 $N\le 2\times 10^5$ 。

思路

本题的规模决定不能把物品逐个展开（总件数可达 $2\times 10^{14}$ ），需要用"合并"技巧把物品压缩。

关键观察 1：同重量内按价值降序取

对重量相同的物品，最优解一定取其中价值最高的若干件。因此把每个重量类的物品按价值降序排序后，一个方案可以由三个数 $(c_1,c_2,c_3)$ 描述：分别取多少件重量 $1,2,3$ 的物品，总重量 $c_1+2c_2+3c_3\le C$ 。

关键观察 2：按 $\dfrac{6}{i}$ 取余并合并

注意重量之间的"公倍数"关系：

6 件重量 1 的物品可合并成 1 件重量 6、价值等于六者之和的物品；
3 件重量 2 的物品可合并成 1 件重量 6 的物品；
2 件重量 3 的物品可合并成 1 件重量 6 的物品。

也就是说，若取件数 $c_i$ 是 $\frac{6}{i}$ 的倍数，就可以把"每 $\frac{6}{i}$ 件"打包成一件重量 6 的物品，问题立刻被统一成"选重量 6 的物品"。因此只需枚举余数：

r_1=c_1\bmod 6,\quad r_2=c_2\bmod 3,\quad r_3=c_3\bmod 2,

其中 $r_1\in[0,6)$ ， $r_2\in[0,3)$ ， $r_3\in[0,2)$ ，共 $6\times 3\times 2=36$ 种组合。

对一组固定的 $(r_1,r_2,r_3)$ ：

重量 $i$ 类中价值最高的 $r_i$ 件必然被取（它们一定落在"取前 $c_i$ 件"中），消耗重量 $r_1+2r_2+3r_3$ ，贡献价值记为 $T_i$ ；
剩余的件数必为 $\frac{6}{i}$ 的倍数，从大到小每 $\frac{6}{i}$ 件打包成一件"重量 6、价值 $=$ 包内价值和"的物品（不足一包的丢弃，因为多出来的是 $6/i$ 的余数，与 $c_i$ 的余数设定矛盾，不会去取）；
把三类打出的包合并，按包价值降序贪心取，最多取

\left\lfloor\frac{C-r_1-2r_2-3r_3}{6}\right\rfloor

个包（若剩余容量为负则此组合非法）。

对 36 种组合取最大值即可。

正确性：任取一个最优解，设其取件数为 $(c_1,c_2,c_3)$ ，则它恰好被组合 $(c_1\bmod 6,\ c_2\bmod 3,\ c_3\bmod 2)$ 覆盖：最优解中"前 $r_i$ 件 + 若干完整包"，其中完整包总数 $m_1+m_2+m_3$ 满足

r_1+2r_2+3r_3+6(m_1+m_2+m_3)\le C,

因此在该组合下，按包价值降序贪心取不超过 $\lfloor \text{剩余}/6\rfloor$ 个包，所得价值不少于最优解的价值，且本身是一个合法方案（总重 $\le C$ ）。所以该组合的最优值恰好是全局最优，取 max 即得答案。

实现要点：

用 (value, count) 压缩表示，避免展开巨量物品；打包过程对每个重量类只需 $O(N)$ 。
全部用 long long：单件价值可达 $10^9$ 、数量可达 $10^9$ ，但答案上界为 $C\cdot 10^9\le 2\times 10^{18}$ ，在 long long 范围内。
一个便于理解的小例子：重量 2 类剩余价值序列（降序）为 $5,5,4,3,2,1,1$ 时，每 3 件打包得到包价值 $5+5+4=14$ 与 $3+2+1=6$ ，最后剩的 1 件丢弃。

参考代码

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

// ls：按价值升序排列的 (value, count) 列表。
// 摘出价值最高的 ofs 件（计价值 top），其余每 g 件打包成一袋。
// 返回 {top, 袋子列表 (袋价值, 袋数)}。
pair<ll, vector<pair<ll, ll>>> pack(vector<pair<ll, ll>> ls, ll ofs, ll g) {
    ll top = 0;
    while (ofs > 0 && !ls.empty()) {
        auto& [v, k] = ls.back();
        ll use = min(k, ofs);
        top += v * use;
        k -= use;
        ofs -= use;
        if (k == 0) ls.pop_back();
    }

    vector<pair<ll, ll>> res;
    ll cur = 0, curSum = 0;  // 当前攒着的半个袋子
    while (!ls.empty()) {
        auto [v, k] = ls.back();
        ls.pop_back();

        if (cur > 0) {          // 先补满当前袋子
            ll need = g - cur;
            ll use = min(k, need);
            cur += use;
            curSum += v * use;
            k -= use;
            if (k == 0) {
                if (cur == g) {         // 恰好补满一袋
                    res.push_back({curSum, 1});
                    cur = curSum = 0;
                }
                continue;
            }
            res.push_back({curSum, 1});  // 补满后 k 还有剩余
            cur = curSum = 0;
        }

        if (k / g) res.push_back({v * g, k / g});  // 整袋
        cur = k % g;                               // 剩余的零头攒着
        curSum = v * cur;
    }
    return {top, res};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    ll c;
    cin >> n >> c;
    vector<vector<pair<ll, ll>>> ls(4);
    for (int i = 0; i < n; i++) {
        ll w, v, k;
        cin >> w >> v >> k;
        ls[w].push_back({v, k});
    }
    for (int w = 1; w <= 3; w++) {
        sort(ls[w].begin(), ls[w].end());  // 按价值升序，方便从尾部取最大
    }

    ll ans = 0;
    for (int r1 = 0; r1 < 6; r1++) {
        auto [t1, g1] = pack(ls[1], r1, 6);
        for (int r2 = 0; r2 < 3; r2++) {
            auto [t2, g2] = pack(ls[2], r2, 3);
            for (int r3 = 0; r3 < 2; r3++) {
                auto [t3, g3] = pack(ls[3], r3, 2);

                ll rem = c - r1 - 2 * r2 - 3 * r3;
                if (rem < 0) continue;
                ll cnt = rem / 6;  // 最多能取几个重量 6 的袋子

                vector<pair<ll, ll>> g;
                g.reserve(g1.size() + g2.size() + g3.size());
                g.insert(g.end(), g1.begin(), g1.end());
                g.insert(g.end(), g2.begin(), g2.end());
                g.insert(g.end(), g3.begin(), g3.end());
                sort(g.begin(), g.end());  // 升序，从尾部取价值最大

                ll now = t1 + t2 + t3;
                while (cnt > 0 && !g.empty()) {
                    auto [v, k] = g.back();
                    if (k >= cnt) {
                        now += v * cnt;
                        break;
                    }
                    now += v * k;
                    cnt -= k;
                    g.pop_back();
                }
                ans = max(ans, now);
            }
        }
    }
    cout << ans << '\n';
}

复杂度分析

时间复杂度： $O(N\log N)$ （三组排序 + 36 组枚举，每组对 $O(N)$ 个袋子排序）
空间复杂度： $O(N)$