Codeforces Round 894 (Div. 3)

A. Gift Carpet

大致题意

从字符串矩阵中依次找出四列，满足依次包含 “vika” 四个字符

思路

简单题，不过多赘述

AC code

B. Sequence Game

大致题意

有一个原始的序列，将其中的 $a_0$ 以及 $a_{i - 1} \leq a_i$ 的 $a_i$ 都提取出来给你，问可能的原始序列是什么

思路

简单题，如果提取后的某个值不满足上述条件的，在其前面加个 $1$ 就行了

AC code

C. Flower City Fence

大致题意

判定将木板排序后，横着和竖着放是否完全相同

思路

简答题，第 $i$ 块木板的长度，是否恰好都等于 $\leq i$ 的模板数量

AC code

D. Ice Cream Balls

大致题意

制作出恰好 $n$ 个不同的包含两个冰球的冰淇淋，需要多少个冰球（同时制作，两个冰淇淋之间不共用冰球）

思路

本题要求的恰好制作出，从最优方案上，肯定是不同的冰球更好，可以得到 $\frac{n \times (n - 1)}{2}$ 种冰淇淋，但是这样难以凑到恰好

通过上面的方案逼近答案后，再加一些重复的冰球，由于需要不同的冰淇淋，所以每种冰球的数量不能超过 $2$ 个，否则是溢出无意义的，不会带来更多方案

而每增加一个额外的重复冰球，仅能带来一种方案，即类似 ${1, 1}$ 这种重复冰球的方案。所以只需要一个简单的减法就行了

AC code

E. Kolya and Movie Theatre

大致题意

在 $n$ 天内选出 $m$ 天，其中每一天能够拿到一定的分数，还需要扣除任意两个选出的天之间的分数差（默认选出第 0 天），分数差仅取决于天数差，问最大能拿到多少分

思路

这道题第一眼以为是需要 dp

但是仔细读题，会发现其实扣除的分数差就是最后选出的那一天的 $index$，因为恰好把所有区间加上了

那么就变得很简单了，只需要计算到达每天的位置，最大的 $m$ 个分数的值是哪些，用个堆就行了

AC code

F. Magic Will Save the World

大致题意

有两种魔法，火魔法和水魔法，每种魔法每秒钟都会积攒对应的法力值，使用 $x$ 点法力值可以打败体力低于等于 $x$ 的怪，怪必须一次打死，问最多需要多少时间才能打死所有的怪

思路

题意中很容易看出是一个背包问题，类似均分为两堆，但是这里不是均分，而是有比例分，所以可以分别计算一次，避免出错

AC code

G. The Great Equalizer

大致题意

每次，将数组排序后，为一个数组中的每个值加上 $n, n - 1, n - 2 \dots, 1$，然后去重，重复，直到只剩下一个值，问最后这个值是什么。

不直接需要原数组的答案，是依次回答的，每次会修改数组中的值，然后询问，修改操作是继承的

思路

观察可以得到，最终结果实际上是 $max(a_i) - min(a_i) + max(a_i - a_{i-1}) + min(a_i)$，化简得到 $max(a_i) + max(a_i - a_{i-1})$。只需要维护好这两值即可

AC code

Generated by RSStT. The copyright belongs to the original author.

Source