简介这份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(p1, pm1, 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一次写好复制四份只改名字。这五分钟能救一整题。4.2 浮点判等号导致超速检测边界判断错误错在哪用sqrt(v0*v0 2*a*s) V判断超速。为什么错题面专门提示精度问题速度恰好等于 V 时不算超速而开方后浮点误差会让「等于」变成「略大于」。怎么答对一律两边平方成整数比较v0*v0 2*a*s V*V并注意 a 的正负方向决定不等号两边的单调性。4.3 决斗题重复值处理成「可以互相打掉」错在哪看到两个相等的 r 就直接配成一对淘汰。为什么错题目要求攻击力严格大于防御力相等时「无事发生」两边都不退场。怎么答对判断条件写严格大于且贪心时用r[i] r[j]而不是样例 2 里大量重复的 136 就是专门用来打这个点的。4.4 染色题忽略「最近的同色数」这个限定词错在哪认为只要左侧存在同值就能加分。为什么错如果同色序列中间夹了一个同值的最近同色就变成了中间那个得分归属完全不同。怎么答对维护两色最近位置而不是简单统计出现次数写完后用样例 3 手推。4.5 擂台游戏每组数据重跑导致超时错在哪对 T 组数据每组重新建树重新算。为什么错T 最大 256n 到 10⁵重跑必炸。怎么答对看清「不同测试数据只是修改 a 得到」这句话把树结构和 d 串预处理一次每组只改叶子能力值后做一遍自底向上更新。5. 考场四小时怎么分配我后来一直用的时间切分法四道题、四小时、四道题的难度大致是「决斗 超速检测 染色 擂台」。我踩过的最大坑是开局冲第三题结果前两题没时间调试血亏。后来固定成一套时间切分法每场都强制走一遍。第一小时决斗拿满 超速检测第一问。决斗的排序贪心只要想清楚严格大于30 分钟内能写完并过样例剩下半小时写超速检测的第一问二分找超速车 物理公式整数化先把稳定分装进口袋。第二小时超速检测第二问 染色暴力。超速检测的区间覆盖贪心是模板题写完立刻用样例 1 验证「关闭 3 个」这个答案。染色的暴力 O(n²) 先拿小测试点之后有时间再升级成 O(n) 的状态压缩。第三小时擂台游戏分层写。先暴力拿小点再写性质 B如果还有余力再碰性质 A。这个顺序保证不会出现「一题爆零」的极端情况。第四小时整套回测。四道题全部重新编译、重新跑样例、检查文件读写、检查数组大小是否够n 到 10⁵ 时开 100005 而不是 10005、检查是否会栈溢出题面说了栈空间与内存限制一致深递归要小心。最后半小时绝不改算法只改明显笔误。有个小习惯我一直保留每道题写完立刻在纸上写下「这题我用了什么结论、依据是题面哪句话」比如决斗写「严格大于见题目描述攻击力小于等于防御力则无事发生」。这张纸既是自查清单也是万一要申诉时唯一的后悔药。希望帮到你。本文还有配套的精品资源点击获取 
长河君 · 2026/11/3 6:18:25 · 阅读 1.2k CSP-S第二轮四题真题解析：排序贪心、区间覆盖与考场时间分配
简介这份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(p1, pm1, 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一次写好复制四份只改名字。这五分钟能救一整题。4.2 浮点判等号导致超速检测边界判断错误错在哪用sqrt(v0*v0 2*a*s) V判断超速。为什么错题面专门提示精度问题速度恰好等于 V 时不算超速而开方后浮点误差会让「等于」变成「略大于」。怎么答对一律两边平方成整数比较v0*v0 2*a*s V*V并注意 a 的正负方向决定不等号两边的单调性。4.3 决斗题重复值处理成「可以互相打掉」错在哪看到两个相等的 r 就直接配成一对淘汰。为什么错题目要求攻击力严格大于防御力相等时「无事发生」两边都不退场。怎么答对判断条件写严格大于且贪心时用r[i] r[j]而不是样例 2 里大量重复的 136 就是专门用来打这个点的。4.4 染色题忽略「最近的同色数」这个限定词错在哪认为只要左侧存在同值就能加分。为什么错如果同色序列中间夹了一个同值的最近同色就变成了中间那个得分归属完全不同。怎么答对维护两色最近位置而不是简单统计出现次数写完后用样例 3 手推。4.5 擂台游戏每组数据重跑导致超时错在哪对 T 组数据每组重新建树重新算。为什么错T 最大 256n 到 10⁵重跑必炸。怎么答对看清「不同测试数据只是修改 a 得到」这句话把树结构和 d 串预处理一次每组只改叶子能力值后做一遍自底向上更新。5. 考场四小时怎么分配我后来一直用的时间切分法四道题、四小时、四道题的难度大致是「决斗 超速检测 染色 擂台」。我踩过的最大坑是开局冲第三题结果前两题没时间调试血亏。后来固定成一套时间切分法每场都强制走一遍。第一小时决斗拿满 超速检测第一问。决斗的排序贪心只要想清楚严格大于30 分钟内能写完并过样例剩下半小时写超速检测的第一问二分找超速车 物理公式整数化先把稳定分装进口袋。第二小时超速检测第二问 染色暴力。超速检测的区间覆盖贪心是模板题写完立刻用样例 1 验证「关闭 3 个」这个答案。染色的暴力 O(n²) 先拿小测试点之后有时间再升级成 O(n) 的状态压缩。第三小时擂台游戏分层写。先暴力拿小点再写性质 B如果还有余力再碰性质 A。这个顺序保证不会出现「一题爆零」的极端情况。第四小时整套回测。四道题全部重新编译、重新跑样例、检查文件读写、检查数组大小是否够n 到 10⁵ 时开 100005 而不是 10005、检查是否会栈溢出题面说了栈空间与内存限制一致深递归要小心。最后半小时绝不改算法只改明显笔误。有个小习惯我一直保留每道题写完立刻在纸上写下「这题我用了什么结论、依据是题面哪句话」比如决斗写「严格大于见题目描述攻击力小于等于防御力则无事发生」。这张纸既是自查清单也是万一要申诉时唯一的后悔药。希望帮到你。本文还有配套的精品资源点击获取