2024年CSP-S2复赛试题
__SECTIONS__:[{"name": "编程题", "count": 4}] 从PDF导入：2024年CSP-S2复赛试题
试卷题目预览
决斗（duel）
今天是小 Q 的生日，他得到了 n 张卡牌作为礼物。这些卡牌属于火爆卡牌游戏"决斗"。第 i 张卡代表一只攻击力为 ri，防御力也为 ri 的怪兽。
在"决斗"游戏中，玩家需要为自己的怪兽安排出场顺序。游戏规则如下：
游戏开始时，所有怪兽按玩家安排的顺序依次上场。
对于每个位置，可以选择攻击任意一个其他位置，如果对方的攻击力小于当前怪兽的攻击力，则对方被消灭。
问如何选择，才能使剩余未被消灭的怪兽数量最少。
从文件 duel.in 中读入数据。 输入的第一行包含一个正整数 n，表示卡牌的数量。 输入的第二行包含 n 个正整数 r1, r2, ..., rn，分别表示每张卡牌的攻击力。
输出到文件 duel.out 中。 输出一行一个整数，表示剩余未被消灭的怪兽的最少数量。
5 1 2 3 4 5
3
超速检测（detect）
小 D 新入职了某国的交管部门，他的第一个任务是负责国家的一条长度为 L 的南北主干道的车辆超速检测。
这条主干道上有 n 辆车行驶，第 i 辆车从南向北行驶，初始位置为 di，初始速度为 vi，加速度为 ai。
主干道上设置了 m 个测速仪，第 j 个测速仪的位置为 pj。所有测速仪都朝南放置，检测经过的车辆是否超速。
若某辆车在经过测速仪时的瞬时速度超过了限速 V，则该测速仪会记录该车超速。
现在需要回答两个问题：
1. 当所有测速仪都打开时，有多少辆超速的车被检测到？
2. 最多可以关闭多少测速仪，使得在所有测速仪都打开时能被检测到的超速的车仍能被检测到？
从文件 detect.in 中读入数据。 输入的第一行包含四个正整数 n, m, L, V，分别表示车辆数量、测速仪数量、主干道长度和限速。 接下来 n 行，每行包含三个整数 di, vi, ai，表示第 i 辆车的初始位置、初始速度和加速度。 接下来一行包含 m 个正整数 p1, p2, ..., pm，表示每个测速仪的位置。
输出到文件 detect.out 中。 输出一行两个整数，分别表示两个问题的答案。
5 5 15 3 0 3 0 12 1 0 1 5 0 5 4 -1 6 0 1 1 2 5 10 15
3 3
染色（color）
小 P 有一个长度为 n 的数组 a，他想将这个数组分成两个子序列，使得得分最大。
得分规则如下：
对于同一个子序列中，如果位置 i 的元素与位置 i-1 的元素相等，则位置 i 的元素得分为 ai，否则得分为 0。
两个子序列的得分之和即为总得分。
问如何拆分子序列，才能使总得分最大。
从文件 color.in 中读入数据。 输入的第一行包含一个正整数 n，表示数组的长度。 输入的第二行包含 n 个正整数 a1, a2, ..., an，表示数组的元素。
输出到文件 color.out 中。 输出一行一个整数，表示最大的总得分。
7 3 3 3 1 3 2 1
6
擂台游戏（arena）
小 S 想要举办一场擂台游戏，如果共有 2^k 名选手参加，那么游戏分为 k 轮进行。
第一轮编号为 1, 2 的选手进行一次对局，编号为 3, 4 的选手进行一次对局，以此类推。
第二轮在只保留第一轮的胜者的前提下，相邻的两位依次进行一场对局。
第 k 轮即为决赛。
每位选手都有一个能力值 ai。对于每场比赛，会先抽签决定擂主，擂主获胜当且仅当他的能力值 ≥ 当前轮数。
现在有 n 位选手报名，需要补充 (2^k - n) 名选手。问所有可能成为总冠军的选手的编号之和是多少。
给定 m 个询问 ci，对于每个询问，求只收到前 ci 位选手的报名信息时的答案。
从文件 arena.in 中读入数据。 输入的第一行包含两个正整数 n, m，分别表示选手数量和询问数量。 输入的第二行包含 n 个非负整数 a1, a2, ..., an，表示每位选手的能力值。 输入的第三行包含 m 个正整数 c1, c2, ..., cm，表示每个询问。 接下来 k 行，每行包含一个 01 串，表示每轮比赛的抽签结果。 输入的下一行包含一个正整数 T，表示数据组数。 接下来 T 行，每行包含 4 个非负整数，用于计算每位选手的实际能力值。
输出到文件 arena.out 中。 输出 T 行，每行一个整数，表示对应数据组所有询问答案的异或和。
5 5 1 2 3 4 5 1 2 3 4 5 01 0 1 0 0 0 0
5 10 11 12 13