做题记录 25.10.2

· · 个人记录

\textcolor{black}\odot P9339 [JOIST 2023] 曲奇 / Cookies

得知 \sum c_i 后，分配方案是容易的，只要每次取数量最多的一种即可（同一组内不可重复），因此考虑如何求出 c_{1\sim x}

假定 c 不降，则 c_{1\sim x} 合法当且仅当 \forall i\le x,\sum_{j\le i}c_j\le \sum_j \min(a_j,i)

O(n\log n)$（容易优化到线性，但不是瓶颈）预处理 $\sup_i=\sum_j \min(a_j,i)

将 b 从大到小排序，令 f_{i,j,k} 表示 b_{1\sim i} 中选择了 j 次，总和能否为 k，则

f_{i,j,k}\to f_{i+1,j,k}\\ f_{i,j,k}\to f_{i,j+1,k+b_i}

显然 j\le \frac{s}b_i（其中 s=\sum a），总和不超过 O(s\ln n)

每个 f_{i,j,\ast} 压为一个 bitset，则时间复杂度 O(\frac{s^2\ln n}\omega)

构造方案是容易的

代码

参考