题解：P16544 [EGOI 2026] 蛋糕 / Cakes

__liujy · 2026-08-05 15:07:49 · 题解

给一个老哥的做法。

在下文 \max\{a_{i} \} 与 n 同阶。

可以想到枚举众数次数 i。我们知道能在划分后让众数次数都为 i 的 k 是连续的，即一定在一个区间 [l, r] 内。考虑怎么求出 l 和 r。

首先来判一下无解。当 \max\{a_{j} \} 小于 i 时显然无解，当只有一个 a_{j} \ge i 且 a_{j} \bmod i 不为 0 也无解，因为 a_{j} \bmod i 哪里都放不了。

接下来考虑怎么求 l。对于 a_{j} \ge i，如果 a_{j} \bmod i 不为 0 会产生一个长为 a_{j} \bmod i 的序列，这个序列不能与前面分解的 \lfloor \frac{a_{j}}{i} \rfloor 的放在一起，如果存在另一个 a_{k} \ge i，可以把这个长为 a_{j} \bmod i 的序列放在从 a_{k} 分解出来的若干个长为 i 序列里面，所以 l = \max_{j = 1}^{n} \lceil \frac{a_{j}}{i} \rceil。直接做是 O(n ^ 2) 的。我们可以用类似于调和级数的方式优化，具体的，枚举 k 使得 k \bmod i = 0，如果存在 a_{j} = k，那么 l = \max(l, k)，如果存在 a_{j} \in [k + 1, k + i - 1]，那么 l = \max(l, k + 1)。没有修改操作，所以这个是可以前缀和做的，我赛时比较糖，写了个树状数组上去。

接下来考虑怎么求 r。显然要将 a_{j} \ge i 所会产生的 \lfloor \frac{a_{j}}{i} \rfloor 尽量排开，剩下会产生的长为 a_{j} \bmod i 的序列放在别的 a_{k} \ge i 所会产生的 \lfloor \frac{a_{k}}{i} \rfloor 个序列下面就行了，所以 r = \sum^{n}_{j = 1} \lfloor \frac{a_{j}}{i} \rfloor，类似的，也能用调和级数优化。

考虑怎么查询一个 k 是否满足条件。将询问离线下来，将 k 与每一个 [l, r] 和 r + 1 一起离散化，然后差分做一下就做完了。