专栏文章

CF2110F Faculty

NNoirCube1
CF2110F题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip6wvva
此快照首次捕获于
2025/12/03 07:09
3 个月前
此快照最后确认于
2025/12/03 07:09
3 个月前
查看原文

Preface

这是 Div. 2，不是 Div. 3？？
看到 rk1 八分钟秒了就感觉不对劲。
*1400 / 数学 / 暴力

Solution

不妨记答案序列为 {b}\{b\}。
我们对 f(x,y)f(x,y) 进行一个大致的感知：
  • Observation 1：不妨使 x≤yx\le y，函数取值一定落在 [x,y][x,y] 之间。特别的，y<2xy<2x 的时候我们可以取到上界。
下界显然，同时 f(x,y)=x+y mod x≤x+y−x=yf(x,y)=x+y\bmod x \leq x+y-x=y，于是上界显然。
由这个性质回到原问题。发现：
  • Observation 2：bi≠bi−1b_i\not= b_{i-1} 有个必要条件：ai\bm {a_i} 是前缀最大值。
显然可以证明。因为对于 bi−1b_{i-1} 一定不超过 a1,a2,a3,… .ai−1a_1,a_2,a_3,\dots.a_{i-1} 前缀最大值 apa_p，然后 ai≥apa_i\ge a_p，所以构造 f(ai,ap)f(a_i,a_p) 就一定会产生一个大于 bi−1b_{i-1} 的结果。
请注意：我们构造的 f(ai,ap)f(a_i,a_p) 不一定是最大值，可能存在更大值，但显然必须使用 aia_i。
但是 ai≤2apa_i\leq 2a_p 的时候还有救，因为我们无需枚举 bib_i 直接就是 aia_i。
于是就做完了。因为 ai>2apa_i> 2a_p 这件事情最多发生 log⁡V\log V 次（其中 VV 是值域），于是我们最多只会暴力枚举 log⁡V\log V 次，我们就在 O(nlog⁡V)\mathcal O(n\log V) 时间解决该问题。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...