# 5 道英文编程题中文翻译 ## 题目 1 这是题目 F 的第二个子任务。与第一个子任务相比，唯一的区别是 \(m\) 的取值范围和时间限制不同。 若要对本子任务进行 Hack，只需要解决本子任务；但若要 Hack 第一个子任务，则必须同时解决两个子任务。 ### 题目描述 brkghioghieognjlxbnvidnbidnblejborjmo 世界上共有 \(n+1\) 种不同的颜色，编号为 \(0\) 到 \(n\)。 有一条长为 \(m\) 厘米的纸带，最初整条纸带都被涂成颜色 \(0\)。 Alice 拿起一把刷子，按照以下过程给纸带上色： 对于 \(i=1,2,\ldots,n\)，依次进行以下操作： - 选择两个整数 \(a_i,b_i\)，满足 \[ 0\le a_i<b_i\le m； \] - 此时区间 \([a_i,b_i]\) 必须全部被涂成同一种颜色； - Alice 将整个区间 \([a_i,b_i]\) 重新涂成颜色 \(i\)。 Alice 选择这些区间，使得最终纸带上的每一厘米都不再是颜色 \(0\)。 具体来说，最终单位区间 \([i-1,i]\) 的颜色为 \(c_i\)，并且 \(c_i\ne 0\)。 此外，除颜色 \(0\) 外的每一种颜色都能在最终的纸带上看到。 请计算有多少对不同的序列 \[ \{a_i\}_{i=1}^{n},\qquad \{b_i\}_{i=1}^{n} \] 能够产生给定的最终颜色配置。 由于答案可能很大，请输出答案对 \(998244353\) 取模后的结果。 ### 输入格式 第一行包含两个整数 \(n,m\)： \[ 1\le n\le 500,\qquad n\le m\le 10^6， \] 分别表示除颜色 \(0\) 外的颜色数量，以及纸带的长度。 第二行包含 \(m\) 个以空格分隔的整数 \[ c_1,c_2,\ldots,c_m， \] 其中 \[ 1\le c_i\le n。 \] \(c_i\) 表示所有操作结束后，单位区间 \([i-1,i]\) 上可见的颜色。 保证对于每个 \(1\le j\le n\)，都至少存在一个位置 \(k\)，使得 \(c_k=j\)。 ### 输出格式 输出一个整数，表示 Alice 完成这次涂色过程的方案数，对 \(998244353\) 取模。 ### 样例 1 输入： ```text 3 3 1 2 3 ``` 输出： ```text 5 ``` ### 样例 2 输入： ```text 2 3 1 2 1 ``` 输出： ```text 1 ``` ### 样例 3 输入： ```text 2 3 2 1 2 ``` 输出： ```text 0 ``` ### 样例 4 输入： ```text 7 7 4 5 1 6 2 3 7 ``` 输出： ```text 165 ``` ### 样例 5 输入： ```text 8 17 1 3 2 2 7 8 2 5 5 4 4 4 1 1 6 1 1 ``` 输出： ```text 20 ``` --- ## 题目 2 ### 题目描述 熊 Limak 正在为一场程序设计竞赛准备题目。当然，在题面中直接提及赞助商的名字会显得不够专业。因此，Limak 打算修改其中的一些单词。 为了让修改后的内容仍然容易阅读，他希望对每个单词所做的改动尽可能少。 Limak 有一个仅由大写英文字母组成的字符串 \(s\)。 一次操作中，他可以交换字符串中两个相邻的字母。例如，通过一次操作，可以将字符串 `"ABBC"` 变成 `"BABC"` 或 `"ABCB"`。 Limak 希望得到一个不包含子串 `"VK"` 的字符串。也就是说，字符串中不能出现字母 `'V'` 后面紧接着字母 `'K'` 的情况。 可以很容易证明，对于任意初始字符串 \(s\)，都能够通过若干次操作满足要求。 请计算 Limak 最少需要执行多少次操作。 ### 输入格式 第一行包含一个整数 \(n\)： \[ 1\le n\le 75， \] 表示字符串的长度。 第二行包含一个仅由大写英文字母组成的字符串 \(s\)，其长度为 \(n\)。 ### 输出格式 输出一个整数，表示为了得到一个不包含子串 `"VK"` 的字符串，Limak 最少需要执行的操作次数。 ### 样例 1 输入： ```text 4 VKVK ``` 输出： ```text 3 ``` ### 样例 2 输入： ```text 5 BVVKV ``` 输出： ```text 2 ``` ### 样例 3 输入： ```text 7 VVKEVKK ``` 输出： ```text 3 ``` ### 样例 4 输入： ```text 20 VKVKVVVKVOVKVQKKKVVK ``` 输出： ```text 8 ``` ### 样例 5 输入： ```text 5 LIMAK ``` 输出： ```text 0 ``` ### 样例说明 在第一个样例中，初始字符串为 `"VKVK"`，最少需要执行 \(3\) 次操作。 一种最优的操作过程如下： 1. 交换最后两个字母，字符串变为 `"VKKV"`； 2. 交换最前面的两个字母，字符串变为 `"KVKV"`； 3. 交换第二个字母和第三个字母，字符串变为 `"KKVV"`。 最终字符串中确实不包含子串 `"VK"`。 在第二个样例中，有两种最优的操作过程： ```text BVVKV → VBVKV → VVBKV ``` 以及 ```text BVVKV → BVKVV → BKVVV ``` 在第五个样例中，不需要进行任何交换。 --- ## 题目 3 ### 题目描述 Radewoosh 正在玩一个电脑游戏。 游戏中共有 \(n\) 个关卡，编号为 \(1\) 到 \(n\)。这些关卡需要被划分为 \(k\) 个区域，每个区域都包含若干个连续的关卡，并且至少包含一个关卡。 游戏会不断重复以下过程： 1. 如果所有区域都已经通关，游戏立即结束。 2. 否则，系统找到第一个仍然包含未通关关卡的区域，记该区域为 \(X\)。 3. 系统创建一个空的令牌袋。每个令牌代表一个关卡，同一个关卡可以对应多个令牌。 4. 对于区域 \(X\) 中每个已经通关的关卡 \(i\)，系统向袋中加入 \(t_i\) 个代表第 \(i\) 个关卡的令牌。 5. 设 \(j\) 为区域 \(X\) 中第一个尚未通关的关卡。系统再向袋中加入 \(t_j\) 个代表第 \(j\) 个关卡的令牌。 6. 最后，系统从袋中等概率随机取出一个令牌，玩家开始游玩该令牌所代表的关卡。玩家会花费一小时完成这个关卡，即使这个关卡此前已经通关过。 给定 \(n\)、\(k\) 以及 \(t_1,t_2,\ldots,t_n\)，请将所有关卡划分为 \(k\) 个区域。 每个关卡必须恰好属于一个区域，并且每个区域必须由一段非空的连续关卡构成。 请计算，在最优划分方式下，完成整个游戏所需要的最小期望时间。 ### 输入格式 第一行包含两个整数 \(n,k\)： \[ 1\le n\le 200000,\qquad 1\le k\le \min(50,n)， \] 分别表示关卡数量和区域数量。 第二行包含 \(n\) 个整数： \[ t_1,t_2,\ldots,t_n， \] 其中 \[ 1\le t_i\le 100000。 \] ### 输出格式 输出一个实数，表示采用最优区域划分时，完成游戏所需小时数的最小期望值。 当答案的绝对误差或相对误差不超过 \(10^{-4}\) 时，答案将被判定为正确。 ### 样例 1 输入： ```text 4 2 100 3 5 7 ``` 输出： ```text 5.7428571429 ``` ### 样例 2 输入： ```text 6 2 1 2 4 8 16 32 ``` 输出： ```text 8.5000000000 ``` ### 样例说明 在第一个样例中，需要将 \(4\) 个关卡划分为 \(2\) 个区域。 最优方案是让第一个区域只包含第一个关卡，第二个区域包含剩余的三个关卡。 在第二个样例中，最优方案是将关卡划分为两个区域，每个区域恰好包含三个关卡。 --- ## 题目 4 本题的内存限制不同寻常。 ### 题目描述 一天晚上，金融家 Igor 和 Zhenya 感到十分无聊，于是决定玩一个游戏。 他们准备了 \(n\) 张纸，每张纸上记录着某家公司在某个时间段内的收入。需要注意的是，收入可以是正数、零或负数。 Igor 和 Zhenya 将这些纸排成一行，然后轮流进行操作： - Igor 从左侧拿走纸； - Zhenya 从右侧拿走纸； - Igor 先手，他可以自行选择从左侧拿走 \(1\) 张或 \(2\) 张纸； - 此后，假设对手在上一次操作中恰好拿走了 \(k\) 张纸，那么当前玩家必须从自己所在的一侧拿走 \(k\) 张或 \(k+1\) 张纸； - 玩家不能跳过自己的回合。 当所有纸都已经被拿走，或者某位玩家无法按照规则进行操作时，游戏结束。 请计算 Igor 所拿纸张上的收入总和与 Zhenya 所拿纸张上的收入总和之差： \[ \text{Igor 的收入总和}-\text{Zhenya 的收入总和}。 \] 假设双方都采用最优策略： - Igor 希望使这个差值尽可能大； - Zhenya 希望使这个差值尽可能小。 ### 输入格式 第一行包含一个正整数 \(n\)： \[ 1\le n\le 4000， \] 表示纸张数量。 第二行包含 \(n\) 个整数： \[ a_1,a_2,\ldots,a_n， \] 其中 \[ -10^5\le a_i\le 10^5。 \] \(a_i\) 表示从左向右数第 \(i\) 张纸上记录的收入。 ### 输出格式 输出一个整数，表示双方都采用最优策略时： \[ \text{Igor 的收入总和}-\text{Zhenya 的收入总和}。 \] ### 样例 1 输入： ```text 3 1 3 1 ``` 输出： ```text 4 ``` ### 样例 2 输入： ```text 5 -1 -2 -1 -2 -1 ``` 输出： ```text 0 ``` ### 样例 3 输入： ```text 4 -4 -2 4 5 ``` 输出： ```text -13 ``` ### 样例说明 在第一个样例中，Igor 最有利的选择是从左侧拿走两张纸，这两张纸上的收入总和为 \(4\)。 随后只剩下一张纸。由于 Igor 上一次拿走了两张，因此 Zhenya 只能拿走 \(2\) 张或 \(3\) 张纸，而剩余纸张数量不足，所以 Zhenya 无法进行操作，游戏结束。 --- ## 题目 5 ### 题目描述 Vasya 和 Petya 使用一种有趣的数据存储结构：金字塔。 金字塔共有 \(n\) 行，第 \(i\) 行包含 \(i\) 个单元格。相对于上一行，每一行都向左偏移半个单元格。 所有单元格按照题目图片所示的方式，被编号为 \[ 1,2,\ldots,\frac{n(n+1)}2。 \] 例如，当 \(n=5\) 时，金字塔的结构如原题图片所示。 这种数据结构支持以下两种操作。 #### 操作 1：修改单个单元格 该操作由三个数描述： ```text 1 i v ``` 其中： - \(1\) 表示操作类型； - \(i\) 表示要修改的单元格编号； - \(v\) 表示要赋给该单元格的新值。 因此，一次操作 1 的描述中共有 \(3\) 个数。 #### 操作 2：修改一个子金字塔 该操作用于修改以某个单元格为顶端的整个子金字塔。 设这个子金字塔共有 \(s\) 个单元格，则操作由 \(s+2\) 个数描述： ```text 2 i v1 v2 ... vs ``` 其中： - \(2\) 表示操作类型； - \(i\) 表示子金字塔顶端单元格的编号； - \(v_j\) 表示要赋给子金字塔中第 \(j\) 个单元格的值。 更形式化地说，假设编号为 \(i\) 的顶端单元格位于第 \(r\) 行、第 \(c\) 列。 那么这个子金字塔包含第 \(r\) 行到第 \(n\) 行的单元格。对于任意 \[ 0\le p\le n-r， \] 该子金字塔在第 \(r+p\) 行中包含第 \(c\) 列到第 \(c+p\) 列的所有单元格。 例如，编号为 \(5\) 的单元格是第三行的第二个单元格。以它为顶端的子金字塔，在第三行包含一个单元格，在第四行包含两个连续单元格，以此类推。 Vasya 和 Petya 原本拥有两个完全相同的金字塔。Vasya 修改了自己金字塔中的一些单元格，现在他希望将这些修改发送给 Petya，让 Petya 能够通过执行一系列操作复现 Vasya 的修改。 Vasya 可以选择任意合法的操作序列，但他希望操作序列的描述尽可能短。这里，一段操作序列的长度定义为描述这段操作序列时所使用的数字总数。 现在给定一个拥有 \(n\) 行的金字塔，其中有 \(k\) 个单元格发生了修改。 请找出一段操作序列，使得这 \(k\) 个被修改的单元格中的每一个，都至少被某次操作修改一次。 在所有满足条件的操作序列中，请选择使用数字总数最少的方案。 你只需要输出这个最小数字总数，不需要输出具体的操作内容或赋值。 ### 输入格式 第一行包含两个整数 \(n,k\)： \[ 1\le n,k\le 10^5， \] 分别表示金字塔的行数和被修改的单元格数量。 接下来 \(k\) 行，每行包含两个整数 \(r_i,c_i\)： \[ 1\le c_i\le r_i\le n， \] 表示某个被修改的单元格位于第 \(r_i\) 行、第 \(c_i\) 列。 保证给出的所有单元格互不相同。 ### 输出格式 输出一个整数，表示最优操作序列的描述中所包含的最少数字数量。 ### 样例 1 输入： ```text 4 5 3 1 3 3 4 1 4 3 4 4 ``` 输出： ```text 10 ``` ### 样例 2 输入： ```text 7 11 2 2 3 1 4 3 5 1 5 2 5 5 6 4 7 2 7 3 7 4 7 5 ``` 输出： ```text 26 ``` ### 样例说明 第一个样例的一种可行方案由以下两个操作组成： ```text 2 4 v4 v7 v8 ``` ```text 2 6 v6 v9 v10 ``` 按照全局编号： - 编号 \(4\) 的单元格位于第 \(3\) 行第 \(1\) 列，以它为顶端的子金字塔包含编号 \(4,7,8\) 的单元格； - 编号 \(6\) 的单元格位于第 \(3\) 行第 \(3\) 列，以它为顶端的子金字塔包含编号 \(6,9,10\) 的单元格。 每个操作都使用 \(5\) 个数，因此总共使用 \[ 5+5=10 \] 个数。 原题图片中，被修改的单元格用颜色标出，两个操作对应的子金字塔分别使用蓝色和黄色标出。