Educational Codeforces Round 91 (Rated for Div. 2)

作者: ffacs 分类: Codeforces 发布时间: 2020-07-24 16:00

C

题意

$n \le 1e5$ 个元素,将元素分组,每个元素仅属于一个组,但不要求每个元素都属某于一个组,要求每个组元素的最小值乘元素的个数大于等于 $x$,求最多的分组数。

题解

贪心,肯定是先把大的安排了再去管小的更好。

D

解法

先找出要删除的区间再进行分类讨论。如果区间最大值大于左右端点的最大值,那么显然至少用一次区间攻击,如果不足 $k$ 个则显然不行,否则显然行(用最大值可以一直减小区间长度),那么可以一开始就直接完成这个步骤。如果区间长度不是 $k$ 的整数倍我们显然只能用单点攻击删去一些。接下来讨论的都是 $k$ 的整数倍。 $ykk$。

E

解法

即求数组中数字块的个数减一。对于每个相邻且不同的数字对,我们只要求出他们是在第几次合并后变成同一个数字的即可。这个合并的过程又可以看成树的合并。所以我们要求的即树上两个叶子的 $\text{LCA}$ 。

发表评论

电子邮件地址不会被公开。 必填项已用*标注