2022年CSP-S2复赛试题

__SECTIONS__:[{"name": "编程题", "count": 4}] 从PDF导入：2022年CSP-S2复赛试题

C++ 240分钟 总分 400.0 4 题
试卷题目预览
第1题 中级 100.0分 编程
假期计划（holiday）

小熊的地图上有 n 个点，其中编号为 1 的是它的家、编号为 2, 3, ..., n 的都是景点。部分点对之间有双向直达的公交线路。
如果点 x 与 z1、z1 与 z2、...、zk-1 与 zk、zk 与 y 之间均有直达的线路，那么我们称 x 与 y 之间的行程可转车 k 次通达；特别地，如果点 x 与 y 之间有直达的线路，则称可转车 0 次通达。
很快就要放假了，小熊计划从家出发去 4 个不同的景点游玩，完成 5 段行程后回家：家 → 景点 A → 景点 B → 景点 C → 景点 D → 家，且每段行程最多转车 k 次。
假设每个景点都有一个分数，请帮小熊规划一个行程，使得小熊访问的四个不同景点的分数之和最大。

【输入格式】
从文件 holiday.in 中读入数据。
第一行包含三个正整数 n, m, k，分别表示地图上点的个数、双向直达的点对数量、每段行程最多的转车次数。
第二行包含 n-1 个正整数，分别表示编号为 2, 3, ..., n 的景点的分数。
接下来 m 行，每行包含两个正整数 x, y，表示点 x 和 y 之间有道路直接相连。
【输出格式】
输出到文件 holiday.out 中。
输出一个正整数，表示小熊经过的 4 个不同景点的分数之和的最大值。
【样例】
8 8 1
9 7 1 8 2 3 6
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 1
【样例解释】
27
第2题 中级 100.0分 编程
策略游戏（game）

小 L 和小 Q 在玩一个策略游戏。
有一个长度为 n 的数组 A 和一个长度为 m 的数组 B，在此基础上定义一个大小为 n×m 的矩阵 C，满足 Ci,j = Ai × Bj。
游戏一共会进行 q 轮，在每一轮游戏中，会事先给出 4 个参数 l1, r1, l2, r2。
游戏中，小 L 先选择一个 l1~r1 之间的下标 x，然后小 Q 选择一个 l2~r2 之间的下标 y。
定义这一轮游戏中二人的得分是 Cx,y。
小 L 的目标是使得这个得分尽可能大，小 Q 的目标是使得这个得分尽可能小。同时两人都是足够聪明的玩家，每次都会采用最优的策略。
请问：按照二人的最优策略，每轮游戏的得分分别是多少？

【输入格式】
从文件 game.in 中读入数据。
第一行输入三个正整数 n, m, q。
第二行 n 个整数，表示数组 A 的元素。
第三行 m 个整数，表示数组 B 的元素。
接下来 q 行，每行四个正整数 l1, r1, l2, r2。
【输出格式】
输出到文件 game.out 中。
输出共 q 行，每行一个整数，表示每一轮游戏的得分。
【样例】
3 2 2
0 1 -2
-3 4
1 3 1 2
2 3 2 2
【样例解释】
0
4
第3题 中级 100.0分 编程
星战（galaxy）

在这一轮的星际战争中，我方在宇宙中建立了 n 个据点，以 m 个单向虫洞连接。我们把终点为据点 u 的所有虫洞归为据点 u 的虫洞。
战火纷飞之中这些虫洞很难长久存在，敌人的打击随时可能到来。这些打击中的有效打击可以分为两类：
1. 敌人会摧毁某个虫洞，这会使它连接的两个据点无法再通过这个虫洞直接到达。
2. 敌人会摧毁某个据点，这会导致该据点的所有还未被摧毁的虫洞被一同摧毁。
我方发展出了两种特种部队负责修复虫洞：
A 型特种部队可以将某个特定的虫洞修复。
B 型特种部队可以将某据点的所有损坏的虫洞修复。
为了把握发动反攻的最佳时机，指挥部必须关注战场上的所有变化。
总指挥认为：如果从我方的任何据点出发，可以进行无限次的虫洞穿梭，且只有一个从该据点出发的虫洞可用，那么这个时刻就是一个绝佳的反攻时刻。

【输入格式】
从文件 galaxy.in 中读入数据。
输入的第一行包含两个正整数 n, m。
接下来 m 行每行两个数 u, v，表示一个从据点 u 出发到据点 v 的虫洞。
接下来一行一个正整数 q 表示询问个数。
接下来 q 行每行表示一次询问或操作。
【输出格式】
输出到文件 galaxy.out 中。
输出一共 q 行。对于每个指令，输出这个指令执行后能否进行反攻。
【样例】
3 6
2 3
2 1
1 2
1 3
3 1
3 2
11
1 3 2
1 2 3
1 1 3
1 1 2
3 1 3
3 3 2
2 3
1 3 1
3 1 3
4 2
1 3 2
【样例解释】
NO
NO
YES
NO
YES
NO
NO
NO
YES
NO
NO
第4题 中级 100.0分 编程
数据传输（transmit）

小 C 正在设计计算机网络中的路由系统。
测试用的网络总共有 n 台主机，依次编号为 1~n。这 n 台主机之间由 n-1 根网线连接，第 i 条网线连接主机 ai 和 bi。保证任意两台主机可以通过有限根网线直接或者间接地相连。
受制于信息发送的功率，主机 a 能够直接将信息传输给主机 b 当且仅当两个主机在可以通过不超过 k 根网线直接或者间接的相连。
在计算机网络中，数据的传输往往需要通过若干次转发。每台主机处理信息都需要一定的时间，第 i 台主机处理信息需要 vi 单位的时间。
现在总共有 q 次数据发送请求，第 i 次请求会从主机 si 发送数据到主机 ti。小 C 想要知道，对于每一次请求至少需要花费多少单位时间才能完成传输。

【输入格式】
从文件 transmit.in 中读入数据。
输入的第一行包含三个正整数 n, Q, k，分别表示网络主机个数、请求个数、传输参数。
输入的第二行包含 n 个正整数 vi。
接下来 n-1 行，每行包含两个正整数 ai, bi。
接下来 Q 行，每行包含两个正整数 si, ti。
【输出格式】
输出到文件 transmit.out 中。
输出 Q 行，每行一个正整数，表示每次请求至少需要花费的单位时间。
【样例】
7 3 3
1 2 3 4 5 6 7
1 2
1 3
2 4
2 5
3 6
3 7
4 7
5 6
1 2
【样例解释】
12
12
3
💬