『XYGOI round1』三个数

· · 题解

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_i=f_1+f_2+...+f_{i-1},\forall i\ge 4

又因为：

f_1+f_2+...+f_{i-2}=f_{i-1},\forall i\ge 5

所以：

f_i=2\times f_{i-1},\forall i\ge 5

其中 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}。故结论成立。