CSP-S第二轮四题真题解析：排序贪心、区间覆盖与考场时间分配

发布时间：2026/11/3 6:18:22

简介：这份2024年CSP-S第二轮上机真题PDF面向备战CCF非专业级软件能力认证提高级的信息学奥赛选手与指导教师，可用于赛前模拟、命题风格研究和赛后复盘。压缩包共1个PDF文件，约210KB，完整收录决斗、超速检测、染色、擂台游戏四道传统题，涵盖题目描述、输入输出格式、样例与解释、数据范围及测试点分布，并附文件命名、main函数返回值、源文件大小、栈空间、编译选项和评测环境等注意事项。读者可据此熟悉提高级第二轮的文件IO写法、Linux评测流程与时间内存限制，按四题模块开展限时训练，对照样例检验思路，并借数据范围设计部分分策略。已有5869人学习，适合需要系统刷真题、查漏补缺的中高级竞赛选手。

1. 决斗题就能看出你够不够 CSP-S 第二轮的水平：先弄清四道题在筛什么

很多选手估分后第一反应是「我前两题写完了，应该稳了」，结果成绩单下来，第三题爆零、第四题连样例都没过。CSP-S 第二轮上机真题一共四道传统型题目：决斗（duel）、超速检测（detect）、染色（color）、擂台游戏（arena），时限 1.0 秒到 2.0 秒、内存 512 MiB、测试点从 20 个到 25 个不等、全部等分。它考的内容是：能不能在四小时内把四道题按难度分成「必须拿满、努力抢分、只骗部分分」三档，并且把文件名、输入输出、返回值这些非算法动作一次做对。适合已经能写基础数据结构与 DP、但一到大模拟和大分类讨论就开始翻车的选手。这篇按「考什么、高频考点、真题怎么答、哪里最容易丢分」的顺序讲透，能直接拿来对着练。

2. 四题考点分布：从决斗到擂台，难点落在哪

2.1 决斗：看着像图论，实际是排序加计数

题目里怪兽 i 的攻击力和防御力都是 r_i，一只怪兽整场最多发起一次攻击，攻击方攻击力严格大于被攻击方防御力才能让对方退场，目标是让游戏结束时场上剩余怪兽数最少。

很多人第一眼往拓扑排序上想，因为「谁打谁」天然像有向图。但注意一个关键约束：每只怪兽只能发起一次攻击，也就是说每个点出度至多 1，被攻击方退场后不能再被打也不能再打。真正决定答案的不是连边结构，而是数值大小关系：一只攻击力大的怪兽可以一击带走一只攻击力严格小于它的怪兽，且它自己只能出手一次。

这类题的正确切入点是先排序再贪心配对。把 r 升序排列，问题变成：用尽量少的「出手次数」覆盖尽量多的「退场名额」。一只怪兽退场需要另一只攻击力严格更大的怪兽攻击它，而被攻击的那只如果本来也要出手，它的出手机会就浪费了。所以答案跟「有多少只怪兽的攻击力严格大于某只怪兽」强相关，重复值是最需要小心的地方——r_i 相等时打不掉，这是本题最容易翻车的边界。

提示：题目给了特殊性质 A（每个 r_i 在值域内独立均匀随机生成），这是出题人明示「随机数据下答案有规律、可以用期望或计数近似快速过」，也说明正解大概率带着排序 + 前缀计数或双指针的味道，而不是复杂图算法。

2.2 超速检测：物理建模加区间覆盖，浮点精度是大坑

这题分两问。第一问：所有测速仪开启时，有多少辆车会被判定超速。第二问：在不漏判任何一辆原本超速的车的前提下，最多能关闭多少个测速仪。

第一问是纯物理 + 判定。车从 d_i 进入，初速 v_i，加速度 a_i，到 L 或速度降为 0 时驶离。瞬时速度公式 v² = v₀² + 2a·s，超速条件是某测速仪位置 p_j 上速度严格大于 V。注意题目强调「驶入与驶出位置若有开启的测速仪也会测速」，这是边界条件，漏了直接错。

第二问本质是区间覆盖问题：对每辆超速车，它在道路上超速的位置构成一个区间（可能是单点、可能是从某处到驶离点、也可能是从驶入点到某处），这辆车必须至少被一个开启的测速仪「打中」。要求关闭最多，等价于选最少的测速仪覆盖所有超速车的超速区间，再取补集。这就是经典的贪心区间覆盖：按区间右端点排序，每次选能覆盖当前最左未覆盖区间右端点的那个测速仪。

真正的难点在两处：一是超速区间的端点要精确算出来，除以 2a 的时候 a 可正可负可零，要分三类讨论；二是「严格大于 V」意味着速度恰好等于 V 的位置不算超速，用浮点算 v² 时极易在等号附近判错，稳妥做法是把比较式乘开成整数不等式，避免开方和除法。

// 判断在位置 p 处，这辆车速度是否严格大于 V // 由 v^2 = v0^2 + 2a(p - d)，避免开方 long long lhs = 1LL * v0 * v0 + 2LL * a * (p - d); // 代表 v^2 long long rhs = 1LL * V * V; // a > 0: lhs 单调增；a < 0: lhs 单调减；a == 0: lhs 恒定 bool overspeed = (lhs > rhs);

上面这段是全题的地基：所有「某位置是否超速」「超速区间左端点在哪」都靠它推导。lhs 用 long long 是因为 v₀ 最大 10³、a 最大 10³、位移最大 10⁶，中间量会到 10⁹ 量级，但乘 2 和累加之后仍在 64 位内，不需要高精度。真正要小心的是当 a < 0 且车在到达测速仪前速度已经降到 0 时，这段行程不存在，必须跳过——很多人的做法是硬算一个负数位移然后判错。

注意：题目提示里专门写了「如果使用浮点数计算要注意潜在精度问题」，这是出题人递过来的提示条。凡是能两边平方或乘开的比较，一律不要引入 double。

2.3 染色：最像 DP 的贪心，重复值决定一切

数组 A 每个数染红或蓝。对位置 i，看它左侧最近的同色数 A_j：如果 A_i = A_j，得分加 A_i，否则加 0。要求最大化总分。

这个设定的精髓在于「最近的同色数」。一种直觉是：为了让 A_i 得分，只要它左边某个同色数的位置到 i 之间，中间的数和 A_i 全染成不同色即可——因为只要中间没有同色，那个同色数就是「最近同色」。

于是问题被转化为：对每个值 x，考虑它在数组中出现的所有位置。把这些位置排序，如果把其中若干个染成同一种颜色且中间没有其他同色，那么这一串里除了第一个，其余每个都能得分。所以最优策略就是：对每个值，在出现的所有位置里，让除第一个之外的尽可能多地拿到分，而限制条件是同一段连续位置里必须交替染色来「腾出空间」。

这类题的标准解法是记录每个值上一次出现的位置和上上次出现的位置，用一点点状态转移或贪心去处理「染哪个色能保住得分」。因为只有两个颜色，任意时刻只需知道两个颜色「最近一次染的位置」，这个状态是 O(1) 的，整体 O(n)。n 到 2×10⁵，时间完全够。

2.4 擂台游戏：明显的分层骗分题，别硬刚正解

这题是最难的一道，也是最能体现策略的一道。2^k 名选手，k 轮淘汰，每场先抽签决定擂主是编号小的还是大的（给定 0/1 串），擂主能力值 ≥ 当前轮数 R 则擂主胜，否则挑战者胜。关键在于：补足 2 的幂次时，补进来的选手能力值可以任取，且如果补的选手可能获胜也要计入答案。多组询问前缀 c_i，多组测试数据用异或生成能力值，最后还要按 i×A_i 异或输出。

这题的正确做法是「先别想正解」。数据范围里给了大量特殊性质：性质 A 询问全是 2 的幂次，性质 B 所有 d_{R,G} = 0。前几个测试点 n 很小，直接暴力模拟前缀 + 枚举补充选手能力值即可拿到不低的分。

真正的难点在于：一位选手能否成为总冠军，取决于从他所在的叶子到根的路径上，每一场「擂主」是否是他，以及他的能力值是否 ≥ 该轮轮数。反过来推：一个位置 i 的选手要赢，需要他在某些轮次作为擂主且能力值达标；若他不是擂主，那么他只能靠「对方擂主能力值不足」获胜，而对方（可能是补位选手）能力值可以任意大，这就让「可能获胜」的判定变成了对补位选手能力值上界的分析。因为 d 串给定、轮数给定，每位选手的「获胜能力值门槛」是确定的，于是答案变成一个前缀统计问题，用倍增或线段树维护即可。

提示：arena 的 T 可以到 256，但不同测试数据只是通过修改 a 得到（异或 X_i），输入结构完全一致，这说明本题的正确做法是一次预处理、多次查询，而不是每组数据重跑一遍。

3. 真题式演练：四道题的答题思路逐个拆

3.1 决斗的标准答题路径与代码骨架

按「读入 → 排序 → 计数」三步走。先把 r 排序，然后统计每个值出现次数，用双指针或后缀和想清楚：一只攻击力为 r 的怪兽，能打掉的必须是严格小于 r 的。每只怪兽只能出手一次，所以「出手者」和「被淘汰者」是两批不同角色，同一只怪兽不能既攻击别人又被别人打掉。

由此得到一个清晰的模型：最终残留的怪兽 = n − 被淘汰数。被淘汰数 = 能配上的「攻击者-被攻击者」对数，而配对受两个约束：攻击者攻击力严格大于被攻击者，且每个攻击者最多用一次。这就是排序后贪心配对，答案某种程度上接近「n − 最大匹配数」，但因为在一条数轴上按大小贪心即可，不需要真跑二分图匹配。

// 排序后贪心：小的一半尽量被大的一半吃掉 sort(r + 1, r + n + 1); int ans = n; int j = 1; // 指向当前最弱的待淘汰怪兽 for (int i = (n + 1) / 2 + 1; i <= n && j < i; ++i) { if (r[i] > r[j]) { --ans; ++j; } // 强者吃弱者，淘汰数+1 }

这里r[i] > r[j]用的是严格大于，直接对应题目「攻击力小于等于对方防御力则无事发生」。循环里i从中位之后开始，是因为最弱的一半不可能全部互相吃掉，最优点是强者吃弱者。变量含义：ans记录残留数，每成功配对一次减一；j是被吃掉的指针，只前进不回退，所以整体是 O(n log n) 排序加 O(n) 扫描。为什么从中位起：如果让弱者吃弱者，打不动；让强者互吃，浪费出手次数。这个贪心的正确性靠「大小关系单调」保证，需要自己用反证法写清楚：若存在更优方案，必有某次攻击可以被替换成「当前最弱可吃者」，不劣。

3.2 超速检测两问的分离式写法

第一问单独写一个函数：遍历每辆车，在 m 个测速仪里找是否有位置满足超速条件。但 n、m 都是 10⁵，直接枚举是 O(nm)，会超时。正确做法是利用单调性二分：a > 0 时速度随位置单调增，超速区间是某个左端点之后；a < 0 时是某段区间；a = 0 时全程恒速。用二分找超速区间的两个端点，复杂度 O(n log m)。

第二问拿到每辆车的超速区间 [l_i, r_i]（若不存在则跳过），问题变成用最少的测速仪位置点覆盖这些区间。经典贪心：把所有区间按右端点排序，维护一个「已选最后一个测速仪位置」变量，若当前区间左端点大于它，就选区间右端点之前最后一个测速仪。

// intervals 已按右端点升序排好 int chosen = 0, last = -1; for (auto &seg : intervals) { if (seg.l > last) { // 当前区间没被覆盖 int pos = upper_bound(p+1, p+m+1, seg.r) - p - 1; // 选 <= seg.r 的最右测速仪 last = p[pos]; ++chosen; } }

参数说明：p是升序测速仪坐标，last是上一个选中测速仪的位置，seg.l > last判断当前超速车是否已被覆盖。upper_bound找的是第一个大于seg.r的位置再减一，即不超过区间右端的最晚测速仪，这是贪心最优性的直接体现。易错点：若upper_bound结果落在 p 的头部之外（即没有 ≤ seg.r 的测速仪），说明该区间无法覆盖，但题设保证第一问判定超速的车一定能被至少一个测速仪抓到，所以这个分支理论上不会触发，但仍应加保护防止数组越界。

3.3 染色题的状态设计与转移

只有两种颜色，可以用「红蓝各自最近一次出现位置」作为状态。扫描到 i 时，若把 A_i 染成红，得分来自「红色上一次出现的位置 last_red 的值是否等于 A_i」；但严格说，得分条件是「最近同色数的值相等」，所以只需记录红、蓝两色最近一次出现的位置上的值，就足以判断本次能否加分。

于是状态可以压成 dp[i][0/1] 表示第 i 个数染红/染蓝时前 i 个的最大得分，转移时看「另一种颜色的最近出现位置」。为了 O(1) 转移，需要预处理每个位置 i 的「上一个相同值的位置」pre[i] 和「上上个相同值的位置」pre2[i]。

转移的核心是：如果 A_i 染红，那么能与它配对的、位置最近的红是同色数。若上一次红色染在 j，且 A_j = A_i，则加分。为了保住这个配对，中间的蓝色不能干扰——但蓝色不影响红色之间的「最近」关系，所以贪心可行：谁离得近就配谁。

// pre[i]: i 之前最近的与 A[i] 相等的位置 // 转移时考虑：让 A[i] 与 pre[i] 同色，则得分 +A[i] // 但若 pre[i] 与 i 之间已有同色元素，则需检查是否冲突 dp[i][0] = max(dp[i-1][0], dp[i-1][1]) ; // 占位思路

上面只是状态形式的示意。真正写的时候，推荐用「记录两色各自最后位置」的滚动数组，转移只依赖常数个下标，空间 O(1)。关键判断：若 pre[i] 存在且 pre[i] 到 i 之间没有与 A_i 同色的元素，那么把 i 与 pre[i] 染同色一定能加分，且不会破坏其他配对——这就是本题贪心能过、不用复杂 DP 的原因。写完必须用样例里的第三个数组3 5 2 5 1 2 1 4手推一遍，答案是 38，对不上就是状态漏了情况。

3.4 擂台游戏的分层得分策略

这题不要求全对。按测试点结构分层写：

层次	做法	覆盖测试点
暴力模拟	对每个询问 c 建树，枚举补位选手能力值上下界	n,m ≤ 500 的小点
性质 A	询问全是 2 的幂次，无补位，直接对每层判胜负	性质 A 的测试点
性质 B	所有 d = 0，擂主恒为编号小者，胜负退化成前缀最小值问题	性质 B 的测试点
正解	预处理每个叶子的能力门槛 + 前缀倍增统计	高分点

性质 B 特别值得写：d 全为 0 时每场擂主是编号小的那位，比赛变成「小号守擂、能力值达标才赢」，等价于从叶子往上取能力值的某种前缀约束，容易用单调栈或倍增在 O(n log n) 内做完。把这档先写死，能稳定拿一部分分，比死磕正解到最后四题全空要划算得多。

注意：输出是按 i×A_i 异或后的单个整数，不是每行一个答案。异或题的常见翻车是中间变量用了 int 溢出，A_i 最大到 10⁵ 量级、i×A_i 会到 10¹⁰，务必用 long long 承接。

4. 易错点：这五处最容易把到手的分丢掉

4.1 文件名和输入输出重定向写错，整题零分

错在哪：把duel.in写成duel.txt，或者忘记freopen，或者程序名用了大写。为什么错：题面注意事项第一条就是文件名必须英文小写，第三、四条明确「因违反以上三点出现的错误，申诉一律不予受理」。怎么答对：比赛开始前先给四道题各写一个空壳模板，把#include、freopen("xxx.in","r",stdin)、freopen("xxx.out","w",stdout)、return 0一次写好复制四份，只改名字。这五分钟能救一整题。