CF2110F Faculty

NoirCube1 · 2025-05-27 19:44:47 · 题解

Preface

这是 Div. 2，不是 Div. 3？？

看到 rk1 八分钟秒了就感觉不对劲。

*1400 / 数学 / 暴力

Solution

不妨记答案序列为 \{b\}。

我们对 f(x,y) 进行一个大致的感知：

• Observation 1：不妨使 x\le y，函数取值一定落在 [x,y] 之间。特别的，y<2x 的时候我们可以取到上界。

下界显然，同时 f(x,y)=x+y\bmod x \leq x+y-x=y，于是上界显然。

由这个性质回到原问题。发现：

• Observation 2：b_i\not= b_{i-1} 有个必要条件：\bm {a_i} 是前缀最大值。

显然可以证明。因为对于 b_{i-1} 一定不超过 a_1,a_2,a_3,\dots.a_{i-1} 前缀最大值 a_p，然后 a_i\ge a_p，所以构造 f(a_i,a_p) 就一定会产生一个大于 b_{i-1} 的结果。

请注意：我们构造的 f(a_i,a_p) 不一定是最大值，可能存在更大值，但显然必须使用 a_i。

但是 a_i\leq 2a_p 的时候还有救，因为我们无需枚举 b_i 直接就是 a_i。

于是就做完了。因为 a_i> 2a_p 这件事情最多发生 \log V 次（其中 V 是值域），于是我们最多只会暴力枚举 \log V 次，我们就在 \mathcal O(n\log V) 时间解决该问题。