Codeforces Round #808 (Div. 2)总结

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16487847.html

比赛地址

比赛情况

排名：1844 / 18910
AC：3 / 6

题目分析

A

假如 $a_2$ 能拆成很多个 $a_1$，$a_3$ 能拆成很多个 $a_2$ 和 $a_1$，则 $a_3$ 必然可以拆成很多个 $a_1$，所以只需要判断 $a_2$ 到 $a_n$ 是否能整除 $a_1$ 即可

B

显然，我们要使所有 $\gcd(a_i,i)=i$，那么我们就找大于等于 $l$ 的第一个 $i$ 的倍数 $\left\lfloor\dfrac{l}{i}\right\rfloor\times i$，如果大于 $r$ 则无解

C

我的思路

首先，假如你在不符合要求（即 $a_i>q$）里面的选，必然是越后越好，因为这样对结果的影响最小

那么我们从后往前考虑，如果这个位置不符合要求，我们现在不选它，那在前面我们也不必选了

基于此，我们可以二分这个位置，复杂度 $O(n\log n)$

答案思路

假如最后她IQ $Q=0$，我们从后往前考虑每个选不选

• 假如 $a_i\leqslant Q$，显然要选，因为对智商没影响
• 假如 $a_i>Q$ 且 $Q<q$，可以选，可以不选，但如果选 $Q++$，那么对结果显然更优，所以必须选
• 假如 $a_i>Q$ 且 $Q=q$，想选也不行，所以不选

赛后总结

A、C题一时没想到思路，B一开始想错了，惨

A开题没想到思路，很慌，推了近20min才想到，19min时过

B一开始判是否可行打错了，26min时wa了一发，28min时过

C真得，真得没想到答案思路那么巧妙，当时纸上画了很久，75min时交了一发，wa了，后来这个贪心被证伪了，最后再112min时才想到一种二分做法，在距离比赛结束8分钟

D没时间看来

---

呜呜，下大分啊（其实不算大，如果最后C没做出才算大）