20260401 刷题记录 2

20. 小苯的区间删除

题目描述 小苯有一个长度为 $n$ 的数组 $a$。他希望通过删除其中一段连续区间，使得剩下的元素按原顺序拼接后，数组变得有序（单调不降）。

具体操作： 选择一段区间 $[l, r] \quad (1 \le l \le r \le n)$，将其从数组中移除。如果剩余部分不为空，则按原相对顺序拼接在一起。

问题 请问有多少种不同的区间选择方案 $[l, r]$，能够使删除后的数组满足单调不降？

注意事项

• 空数组判定： 小苯认为空数组也满足有序（即你可以选择 $[1, n]$ 这一区间）。
• 目标： 统计所有满足条件的 $(l, r)$ 对的数量。

21. 小苯的比赛上分

题目背景 有一款大型多人电子竞技游戏网站“喜爱福”，选手通常拥有多个账号。小苯有 $n$ 个账号，每个账号当前的分数为 $a_i$。

题目描述 小苯遵循一条准则：“只要永远使用分数最低的账号参赛，那么所有账号中的最高分（$\max \text{Rating}$）将单调不降。”

已知小苯将参加 $m$ 场比赛，每场比赛的规则如下：

1. 参赛选择： 每次都选择当前 $n$ 个账号中分数最低的那个账号参赛。
2. 分数变动： 假设第 $j$ 场比赛后，该参赛账号的分数会增加 $b_j$。

问题 请你计算在每场比赛结束后，小苯所有账号中的最大值 $\max \text{Rating}$ 分别是多少。

输入要求

• 初始分数组 $a$。
• 每场比赛的分数增量序列 $b$。

输出要求

• 输出 $m$ 个整数，分别代表每场比赛后的 $\max \text{Rating}$。

22. 小苯的魔法染色

题目描述 小红面前有一堵长度为 $n$ 的墙，初始状态由一个仅包含 W（白色）和 R（红色）的字符串 $a_1 a_2 \dots a_n$ 表示。小红的目标是将整面墙全部染成红色。

为此，魔法师小苯可以进行施法，单次施法流程如下：

• 选择一个闭区间 $[l, r] \quad (1 \le l \le r \le n)$；
• 将该区间内的所有格子立即染成红色。

约束条件

• 施法次数： 小苯至多施法 $m$ 次。
• 区间限制： 每次施法的区间长度 $(r - l + 1)$ 不得超过 $k$。

问题 请问：要确保能将整堵墙全部染成红色，所需的 $k$ 最小是多少？请输出这个 $k$ 的最小可能值。