CF1995C

· · 题解

题意转换

给定序列 \{a_n\}，要求序列 \{b_n\} 满足 \{c_n\} 单调不降，其中 c_i = a_i^{2^{b_i}}，求出最小的 \sum b_i。

朴素做法：i 从 2 扫到 n。若 a_i < a_{i-1} 则一直让 a_i 做平方运算，记录次数。

做法缺陷：

  1. 爆 ll。

  2. 平方次数太多复杂度爆了。

猜结论

若 a_{i - 1} \leq a_i < a_{i - 1}^2，则 b_i 最小取 b_{i-1}。

证明

c_{i-1} = a_{i-1}^{2^{b_{i - 1}}} c_i = a_i^{2^{b_i}}

两边同时取 \log。

\log c_{i-1} = 2^{b_{i - 1}}\log(a_{i-1}) \log c_{i} = 2^{b_{i}}\log(a_{i}) \therefore 2^{b_{i - 1}}\log(a_{i-1}) \leq 2^{b_{i}}\log(a_{i}) \therefore 2^{b_{i-1}-b_i}\leq \frac{\log(a_i)}{\log(a_{i-1})} \because 1 \leq \frac{\log(a_i)}{\log(a_{i-1})} < 2 \therefore b_{i-1} - b_i < 1 b_i > b_{i-1} - 1

又 b_i 均为整数，所以 b_i 最小取 b_{i-1}。

实现

设 f_i 代表第 i 位满足 c_i \geq c_{i-1} 最小的 b_i。

先把原序列中的 a_i 调整到大于等于 a_{i-1} 且小于其两倍的位置。

再拿调整次数（往小调为负号）+ f_{i-1} 即可得到 f_i。

Ending

作者数学水平有限，若上面有瑕疵请及时与作者联系。

提交记录。

视频讲解。