526互联

Educational Codeforces Round 147 (Rated for Div. 2) A~E 题解

发布时间 2023-05-02 18:24:27作者: hcywoi

A

Link。

模拟，代码。

B

Link。

模拟，代码。

C

Link。

我们设 \(c\) 为最后相同的字符。

性质：我们一定不会删除字符 \(c\)。

因此以 \(c\) 为最后字符的操作次数就是不包含字符 \(c\) 的极大段的最小操作次数的最大值。

对于一个长度为 \(l(l\ge 1)\) 的段，它的最小操作次数为 \(\lfloor\log_2l\rfloor+1\)。

时间复杂度：\(\mathcal O(n)\)。

代码。

D

Link。

  • 枚举最后一个选的线段是哪一条。
  • 选一条线段的代价是 \(2\)，一次是『激活』一次是『不激活』。
  • 前面一定是长度最小的几条线段不选，因此我们可以用优先队列维护。

时间复杂度：\(\mathcal O(n\log n)\)。

代码。

E

Link。

前言：这 \(k\) 有误导性。

对于右括号 \(i\)，我们设其对应的左括号为 \(l_i\)。

则这个右括号对答案的贡献为 \(\dfrac{i-l_i-1}{2}\)，就是 \(i\sim l_i\) 中括号的个数。

我们修改可以修改一个左括号，使得其对应的右括号的贡献值变为 \(0\)。

那么我们就将最大的 \(k\) 个贡献值修改。

时间复杂度：\(\mathcal O(n\log n)\)，瓶颈在于排序。

代码。