*1200~1500 狂做

· · 个人记录

CF2126E *1400 29min

实际就是判每一个点能否都构造出来。

### CF2123E *1400 28min 切入点很好找，就是 $i \le \text{mex}$ 时都能对操作次数的一段产生 $1$ 的贡献。 $i$ 产生贡献的下限为把 $i$ 全删了，上限为 $0 \sim i - 1$ 各取一个，即删 $n - i$ 个。 设数 $i$ 出现了 $t_i$ 次，则数 $i$ 的贡献区间为 $[t_i , n - i]$。离线一下前缀和求答案即可。 ### CF2124C *1300 11min 不难想到从后往前贪心，$a_i = \gcd(b_i , a_{i+1})$，$\displaystyle ans = \operatorname{lcm}\limits_{i = 1}^n \frac{b_i}{a_i}$。 ### CF2126D *1200 6min 这题还真值得研究。 首先若当前的 $k \ge real_i$，则不会走向 $real_i$。因为如果想走向一个更右的位置，那个线段如果覆盖这个小的 $real_i$，也一定会覆盖 $k$ 的。而覆盖 $k$ 不一定覆盖这个小的 $real_i$。 所以题意转化为了一个个 $[L_i,real_i]$ 的区间，若在这个区间内可以传到 $real_i$。此时最直观的做法就是按 $real_i$ 排序贪心取。 按 $L_i$ 排序贪心取也可，不过原理不同。