自动搬运

查看原文

来自洛谷，原作者为

	无钩七不改名 自食恶果||qq:2186241402

搬运于2025-08-24 22:48:21，当前版本为作者最后更新于2023-04-07 21:13:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Upd 2024.11.2 改了一点 markdown 错误。

出题人题解

首先，$3$ 只有一种拼凑方案就是 $\{0,1,2\}$，所以每个集合一定都包含这 $3$ 个数。

而这 $3$ 个数中选 $2\sim3$ 个数，最多能凑成 $3$，最少能凑成 $1$，选至少三个数只能凑成 $3$，所以集合中第 $4$ 个数选择 $0+1+2=3$，就可以拼凑出 $4\sim6$。同理可得第 $5$ 个数是 $0+1+2+3=6$，因此可以总结出一个递推式：

又因为：

所以：

其中 $f_1=0,f_2=1,f_3=2$。

特殊的，还需要处理出 $f_4=3$。

而每个集合（设有 $n$ 个数）最大能凑成的数就是 $f_1+f_2+...+f_n$，即 $f_{n+1}$。

由于数据范围过大，我选择先预处理出数据范围内的所有 $f$ 数组。输入 $w$ 时，只需二分查找 $f$ 数组中第一个 $\geq w$ 的数，答案便是这个数在 $f$ 数组中的下标 $-1$。

更新于 $2023.7.2$：

有人问我为什么 $\log n\div 3+3$ 是对的。这里解释一下，问题简化一下就是求使得 $3\times 2^{k-3}\ge n$ 成立的最小的 $k$。而很容易看出上面的式子除了前三项其实就是 $f_i=3\times 2^{k-4}$。故结论成立。