Codeforces Round 894 (Div. 3)全部题目题解

· · 个人记录

错失了千载难逢的 AK 良机，死亡过程如下：

A 读错题，10min 进去了，然后多测清空写挂，吃一发罚时。

C 题没搞懂题意，10min 进去了。

D 题题意搞错，20min 进去了。

E 题读错题，40min 进去了（真的是 40min）

时间不多，想 F,以为是个 1e6 复杂度做法，想了会，没思路。

然后开始摆，到最后 10min 决定冲一发 bitset 优化 dp，复杂度 1e8 / w。

然后，因为把 sum 打成 n，没调出来，赛后 AC，跑得飞快。

G 题最后也没看。

第二天在学校，20min 在草稿纸上把 G 做了出来。

题解

A

贪心匹配子序列就行了。

B

依次枚举，如果 当前数小于上一个数，那就在中间插入 1（因为 1 是最小数）

C

显然如果竖着的最高高度不是 n，无解。
剩余匹配就行了。

D

二分就行。

E

显然可以枚举最后一个电影，贪心算就行了。

F

枚举分给火系技能的怪物实力总和，bitset 优化可行性 dp 就可以搞定。

然后直接算就行了。

G

一次操作的本质是让相邻两数的差距减一。
所以一次操作前，如果一个数比前一个数大 1，那么操作后它一定会被干掉。
梳理一下。

第一次先排序，并去重。

显然，之后每一次操作结束后，所有数字相对顺序不会变，因为操作前没有重复数字。

所以我们只需要预先排序去重，然后忽略掉操作中的排序，之后所有内容都默认预先执行了操作。

每次操作都是把所有相邻数差距减少 1，然后所有与前一个数差距为 0 的数都会在下一轮前被干掉。

由于每次操作后相对顺序不变，我们只需要关心第一个元素每次加上多少。

我们把操作前相邻数的差值都算出来，现在考虑每个差值的贡献。

显然，第 i 次操作之前，所有初始状态下比前一个数大至少 i 的数（包括最小的数，这里指第一个数）得以保留，第一个数的值将加上它们的数量总和。

显然可得，一个数对答案的贡献是这个数减去前一个数，最后贡献总和还要加上第一个数初始值，以及相邻两数最大的差值（显然这个是操作次数）。

现在，我们得出了快速计算一个序列答案的方法。

有修改修改操作也很简单，算一下减少的差值和新出现的差值的贡献，搞定。

link