[CodeForces] CF520 题解

Eliauk-FP / 2025-02-18 / 原文

A. Pangram

Link-CF
Link-Luogu

【题目大意】

给定一个字符串，询问是否所有英文字符（a 到 z）都在这个字符串中出现过，不区分大小写。

【解题思路】

开个桶记录字符是否出现过，最后遍历桶，如果发现有一个没出现就输出 NO，否则就输出 YES。注意不区分大小写！

B. Two Buttons

Link-CF
Link-Luogu

【题目大意】

给定两个正整数 $n$ 和 $m$，每次操作可以把 $n$ 乘二或减一，求将 $n$ 变成 $m$ 的最小操作次数。

【解题思路】

正难则反，考虑将 $m$ 进行操作变成 $n$，每次可以除二或加一。

考虑贪心。显然除法比加法更优。所以能进行除法就进行除法。

因此，只有在 $m < n$ 或者 $m$ 为奇数的时候不进行除法。

操作的时候统计答案即可。

C. DNA Alignment

Link-CF
Link-Luogu

【题目大意】

给定一个长度为 $n$ 字符串，只包含A，T，G，C四种字符。

定义 $shift$ 值，指两个字符串分别移位之后的相同位的个数。

你需要求出满足与原字符串 $shift$ 值最大的字符串的个数。

【解题思路】

考虑贪心构造。

我们对于构造的字符串，每个字符都选取原字符串出现次数最多的字符，这样可以使 $shift$ 值最大。

可以这么理解，选字符串出现次数更多的字符会让移位时相同位出现的“概率”更大，这样的话，选出现次数越多的字符那也就比选其他的 $shift$ 值越大。

也就是说，构造的字符串中，每个位置都选择原字符串里出现次数最多的字符即可。

注意这题的问法，我们需要求的是这样的字符串的个数。我们每个位置都要 $k$ 种选法，其中 $k$ 为在字符串中出现次数最多次的字符的个数。这样，答案就是 $k ^ n$。

D. Cubes

Link-CF
Link-Luogu

【题目大意】

$m$ 个方块（每个方块边长为 $1$），每个方块的左下角坐标为 $(x_i, y_i)$。这些方块构成了一个图形。

称这个图形是稳定的，如果对于任何一个左下角坐标为 $(x_0, y_0)(y_0 \neq 0)$ 的方块，它在图形里，且存在一个左下角坐标为 $(x_0 - 1, y_0 - 1)$ 或 $(x_0, y_0 - 1)$ 或 $(x_0 + 1, y_0 - 1)$ 的在图形里的方块。

现在，两个人甲和乙来拆除这个图形。每次操作可以移除一个方块，然后按拆除的顺序排列好。他们需要保证每次拆除后图形是稳定的。最开始，图形是稳定的。

最后，这些方块的编号组成了一个 $m$ 进制数（因为是按拆除的顺序排列的，越先拆就在越高位），甲希望这个数尽可能大，乙希望这个数尽可能小。甲先操作，然后两个人交替操作。求在两人按照最优策略操作时，最终的 $m$ 进制数的十进制是多少。

方块的编号是 $0$ 到 $m - 1$。

【解题思路】

考虑贪心。

由于越先拆的放在越高位，所以说，甲的最优策略是每次拆除可以拆的方块中编号最大的，乙每次拆除可以拆的方块中编号最小的。这可以用一个大根堆和一个小根堆来维护。

如何判断一个方块可不可以拆？这只需要考虑它的上方和斜上方的方块即可。

删除操作可以用 $map$ 来维护。每次删除后需要更新它的下发和斜下方的方块，判断能否加入堆。

注意编号是从 $0$ 开始的。

E. Pluses everywhere

Link-CF
Link-Luogu

【题目大意】

给定 $n$ 个数 $a_i$，每次操作可以在这些数中间添加 $k$ 个 $+$ 号，得到若干个不同的表达式，求这些表达式的和。

【解题思路】

考虑对每个 $a_i$ 单独计算它的贡献。

若在 $a_{i + j}$ 的后面放加号，$a_i$ 在表达式中的实际值为 $a_i \times 10 ^ j$。剩下 $k - 1$ 个加号，有 $n - j - 2$ 个位置可以放加号，这样，这个表达式的出现次数为 $C_{n - j - 2}^{k - 1}$，$a_i$ 这时的贡献为 $a_i \times 10 ^ j \times C_{n - j - 2}^{k - 1}$。特别地，当 $a_i$ 后面没有加号时，它的贡献为 $a_i \times 10 ^ {n - i} \times C_{i - 1}^k$（所有的加号都放在 $i$ 的前 $i - 1$ 个位置里）。