CF1783E Game of the Year

Alex_Wei · 2023-01-10 10:20:35 · 题解

A 和 B 分别在第 \lceil \frac {a_i} k\rceil 和第 \lceil \frac {b_i} k\rceil 次攻击时杀死第 i 个怪物，所以题目相当于找到所有 1\leq k\leq n 使得 \lceil \frac {a_i} k\rceil\leq \lceil \frac {b_i} k\rceil。

我们直接对 \lceil \frac {a_i} k\rceil 进行整除分块，对每个整除值 d 算出使得 \lceil \frac {b_i} k\rceil\geq d 的合法区间，时间复杂度 \mathcal{O}(n\sqrt n)，然而 无法通过。

换种角度考虑。对 a_i\leq b_i 显然所有 k 均合法。当 a_i > b_i 时，考虑 k 不合法的充要条件：在 [b_i, a_i - 1] 之间存在 k 的倍数。这样就简单了：区间覆盖 [b_i, a_i - 1]，则一个 k 合法当且仅当它的所有倍数均没有被覆盖，枚举即可。时间复杂度 \mathcal{O}(n\log n)。代码。