数字钱包 题解

思路

把最终取到的元素按列计数。前 $i$ 列中被取元素的数量记为 $j$。存在合法操作顺序，当且仅当处理完第 $i$ 列后

这是区间匹配的 Hall 条件：前缀不能选得过多，否则没有足够的早期操作；也不能选得过少，否则后面的操作窗口无法再覆盖足够元素。

做法

子任务 1 直接枚举每次操作选择的矩阵元素，用位掩码记录已取元素，复杂度为指数级。

子任务 2 进行零一背包。按列处理每个元素，令 $dp_j$ 为当前选取 $j$ 个元素的最大总和；每列结束后删去不满足上述范围的状态。复杂度为 $O(NM^2)$。

满分做法利用 $dp$ 关于 $j$ 的离散凹性。维护相邻状态差分

组成的多重集合。加入一个值为 $w$ 的元素，对应把 $w$ 插入差分集合。每列处理完后：

• 为满足右端上界，只保留最大的若干差分，删除最小值；
• 当左端下界增加一时，必须多选一个元素，把当前最大差分加入答案并删除。

集合大小始终不超过 $K$，因此每个元素只需一次 $O(\log K)$ 的插入或删除。

独立答案程序使用另一条路径：把所有元素按权值从大到小尝试加入区间匹配的独立集，并用 Hall 条件与两棵线段树判断本次加入是否仍可匹配。这是转移结构独立的拟阵贪心验证。

复杂度

• 子任务 1：指数时间，空间 $O(NM)$；
• 子任务 2：时间 $O(NM^2)$，空间 $O(M)$；
• 满分算法：时间 $O(NM\log K)$，空间 $O(K)$（读入矩阵需要 $O(NM)$ 或按列存储）。