题解：CF356D Bags and Coins

ran_qwq · 2026-04-22 19:01:48 · 题解

一看到 n\le 70000 就想到 bitset 鉴定为做追忆做的。

对于一个没被嵌套的袋子里面装的一堆袋子，肯定是按大小从大到小排序放，大的放在外面，这样一定合法。所以题目等价于你要选 a 一个总和为 s 的子集，并且强制选 a 的最大值。

这是经典的 01 背包输出方案问题，用 bitset 优化可做到 O(\frac{n^2}w)。输出方案把每个位置的 bitset 存下来，这样空间会爆。可以每隔 \sqrt n 个位置记录一次。在块内找前驱的时候再 dp 一次。把当前块值域的下界和上界算出来之后，所有块值域长度总和是 O(n) 的，所以复杂度是对的。

这是代码。