简介这份资源是2024年CSP-S第二轮认证提高级的上机真题PDF面向备战信息学奥赛的中学选手及竞赛教练用于模拟真实赛制、检验算法设计与编程实现能力。压缩包内仅含1个PDF文件约210KB完整收录决斗duel、超速检测detect、染色color、擂台游戏arena四道传统型题目涵盖题目描述、输入输出格式、样例解释与数据范围并附有文件命名、main函数返回值、源文件100KB限制、栈空间与内存限制、Linux评测环境及编译选项等注意事项。其中决斗涉及拓扑排序与策略选择超速检测聚焦匀加速运动下的数据处理与异常检测染色对应图着色与贪心算法擂台游戏则综合模拟、搜索与动态规划技巧。目前已有5862人学习下载适合选手按官方时限与内存约束进行限时训练对照测试点分布与特殊性质梳理解题思路查漏补缺提升赛场应对能力。1. 从四道题看 CSP-S 2024 提高组到底在考什么2024 年 CSP-S 第二轮提高组的四道题——决斗duel、超速检测detect、染色color、擂台游戏arena——放在一起看能明显感觉到命题组在“思维难度”和“实现难度”之间做了一次重新配比。四道题全是传统型没有交互没有提交答案时限 1.0 秒到 2.0 秒内存统一 512 MiB测试点从 10 个到 25 个不等且全部等分。这意味着每道题都不存在“暴力骗部分分靠特殊性质”的捷径你必须把正解写对才能拿到该测试点的全部分数。这份真题资源适合谁如果你正在准备 CSP-S 提高组、NOIP 或者更高级别的信息学奥赛这四道题是极好的训练材料——它们覆盖了排序贪心、区间合并、动态规划、树形结构模拟等核心考点而且每道题的测试点设计都刻意区分了不同复杂度的做法。如果你只是刚学完基础语法这份题会让你感到吃力建议先补完贪心和二分再回来。下面我按“题目拆解 → 正解思路 → 代码实现 → 避坑”的顺序把四道题逐一拆开讲。2. 决斗duel排序贪心与拓扑攻击顺序2.1 题目模型转化原题描述的是 n 只怪兽每只攻击力和防御力都是 ri。每回合选一只怪兽 i 攻击另一只 j若 ri rj 则 j 退出每只怪兽最多攻击一次。要求最小化游戏结束时未退出怪兽的数量。这个模型可以转化为把怪兽按 ri 从小到大排序然后从小到大扫描用一只较大的怪兽去“吃掉”一只较小的怪兽。每只怪兽只能攻击一次所以每只怪兽最多“杀死”一只其他怪兽。最终未退出的怪兽数量 n - 被击杀的怪兽数量。我们要最大化被击杀的数量。关键观察如果一只怪兽被击杀它就不能再攻击别人。所以最优策略是让尽量多的怪兽被击杀同时保证击杀者本身不被击杀。排序后用双指针或贪心匹配即可。2.2 贪心策略与代码实现具体做法将 r 数组排序。维护一个“可用的击杀者”集合。从小到大遍历对于每个怪兽如果存在一个比它大的怪兽尚未使用过攻击机会就用那只大的击杀它。实际上更简单的做法是排序后从大到小扫描用一只大怪兽去匹配一只小怪兽能匹配就匹配。#include bits/stdc.h using namespace std; int main() { freopen(duel.in, r, stdin); freopen(duel.out, w, stdout); int n; scanf(%d, n); vectorint r(n); for (int i 0; i n; i) scanf(%d, r[i]); sort(r.begin(), r.end()); // 双指针i 指向当前待击杀的小怪兽j 指向当前可用的击杀者 int i 0, j 0, killed 0; while (i n j n) { if (r[j] r[i]) { // j 可以击杀 i killed; i; j; } else { // j 不够大换更大的击杀者 j; } } printf(%d\n, n - killed); return 0; }逻辑说明排序后i 从最小的怪兽开始j 从最小的可用击杀者开始。如果 r[j] r[i]说明 j 能击杀 i击杀数加一两者都后移否则 j 后移找更大的击杀者。这样能保证每只被击杀的怪兽都对应一只不同的击杀者且击杀者攻击力严格大于被击杀者。时间复杂度 O(n log n)完全满足 n ≤ 10^5 的要求。参数注意输入文件是 duel.in输出是 duel.out必须用 freopen 重定向。编译选项 -O2 -stdc14 -static。数组大小开到 100005 即可。2.3 特殊性质 A 的处理特殊性质 A 说 ri 在值域内独立均匀随机生成。这个性质其实对正解没有影响因为正解本身就是 O(n log n) 的排序贪心随机数据反而会让排序更快。但如果你写的是 O(n^2) 的暴力匹配随机数据下期望匹配次数会少一些可能骗到部分分。不过测试点 16~20 没有特殊性质n 高达 10^5暴力必然超时。3. 超速检测detect物理建模与区间贪心3.1 物理模型与超速区间计算这道题的核心是把每辆车的运动学方程解出来判断它在哪些位置超速然后把这些超速位置映射到测速仪上。题目给了匀加速运动公式v1 v0 ats v0t 0.5at^2以及 v1^2 v0^2 2as。对于每辆车我们需要找到它超速的位移区间 [s1, s2]相对于起点 di。超速条件是瞬时速度 V。根据公式 v^2 v0^2 2as当 a ≠ 0 时超速对应的位移范围是若 a 0v 随 s 增大而增大超速区间是 [max(0, (V^2 - v0^2)/(2a)), 终点]。若 a 0v 随 s 增大而减小超速区间是 [0, min(终点, (V^2 - v0^2)/(2a))]。若 a 0v 恒为 v0若 v0 V 则全程超速否则不超速。注意边界车辆驶入和驶出时的位置也要考虑。车辆从 di 驶入到 L 或速度降为 0 时驶离。所以实际超速区间要映射到道路坐标 [di, di s] 上再与测速仪位置比较。3.2 第一问统计超速车辆数第一问很简单对每辆车计算它的超速区间然后检查这个区间内是否有至少一个测速仪。如果有这辆车就被判定为超速。注意测速仪位置是给定的 p1 p2 ... pm可以用二分查找快速判断区间内是否有测速仪。#include bits/stdc.h using namespace std; int main() { freopen(detect.in, r, stdin); freopen(detect.out, w, stdout); int T; scanf(%d, T); while (T--) { int n, m, L, V; scanf(%d %d %d %d, n, m, L, V); vectortupleint,int,int cars(n); for (int i 0; i n; i) { int d, v, a; scanf(%d %d %d, d, v, a); cars[i] {d, v, a}; } vectorint p(m); for (int i 0; i m; i) scanf(%d, p[i]); sort(p.begin(), p.end()); int cnt 0; vectorpairint,int intervals; // 超速区间 [l, r] 在道路坐标上 for (auto [d, v, a] : cars) { double s1, s2; bool has false; if (a 0) { if (v V) { s1 0; s2 L - d; has true; } } else { double s_crit (1.0 * V * V - 1.0 * v * v) / (2.0 * a); if (a 0) { if (s_crit L - d) { s1 max(0.0, s_crit); s2 L - d; has true; } } else { if (s_crit 0) { s1 0; s2 min((double)(L - d), s_crit); has true; } } } if (has) { int l d (int)ceil(s1 - 1e-9); int r d (int)floor(s2 1e-9); if (l r) { // 检查 [l, r] 内是否有测速仪 auto it lower_bound(p.begin(), p.end(), l); if (it ! p.end() *it r) { cnt; intervals.push_back({l, r}); } } } } printf(%d , cnt); // 第二问区间贪心 // ... 见下一节 } return 0; }逻辑说明对每辆车先判断是否超速再计算超速区间在道路坐标上的范围。用 lower_bound 找第一个 ≥ l 的测速仪如果它 ≤ r说明区间内有测速仪这辆车被判定为超速。注意浮点数精度问题用 1e-9 的偏移量避免边界误差。参数注意T ≤ 20n, m ≤ 10^5L ≤ 10^6V ≤ 10^3。a 可能为负s_crit 可能为负需要判断。测速仪位置已排序但题目输入不一定有序建议手动 sort 一次。3.3 第二问区间贪心求最多关闭数第二问要求在不漏掉任何超速车辆的前提下最多关闭多少测速仪。等价于选择最少的测速仪使得每个超速区间内至少有一个被选中的测速仪。这是一个经典的区间覆盖问题。贪心策略将所有超速区间按右端点从小到大排序。维护一个变量 last -1 表示上一个选中的测速仪位置。对于每个区间 [l, r]如果 last l说明当前区间没有被覆盖需要选一个测速仪。为了覆盖尽可能多的后续区间选 r 位置上的测速仪如果 r 处有测速仪或者选 ≤ r 的最大测速仪。实际上更简单的做法是选区间内最靠右的测速仪。// 接上面的代码 sort(intervals.begin(), intervals.end(), [](auto a, auto b) { return a.second b.second; }); int chosen 0; int last -1; for (auto [l, r] : intervals) { if (last l) { // 需要选一个测速仪选 r 的最大的 auto it upper_bound(p.begin(), p.end(), r); if (it ! p.begin()) { --it; last *it; chosen; } } } printf(%d\n, m - chosen);逻辑说明按右端点排序后每次遇到未被覆盖的区间就选一个测速仪。选哪个选 ≤ r 的最大测速仪这样能尽可能覆盖后面的区间。last 记录上一个选中的测速仪位置如果 last ≥ l说明当前区间已被覆盖跳过。最终关闭数 总测速仪数 - 选中的测速仪数。参数注意区间可能为空l r需要过滤。upper_bound 找第一个 r 的位置然后回退一个就是 ≤ r 的最大值。如果 it p.begin()说明没有 ≤ r 的测速仪但这种情况不应该发生因为区间内至少有一个测速仪才被计入 intervals。4. 染色color动态规划与颜色分配4.1 问题转化与状态定义染色题要求把数组 A 的每个元素染成红或蓝然后计算得分对于每个位置 i如果它左边最近同色元素 j 满足 A[i] A[j]则得分加 A[i]否则加 0。要求最大化总得分。这个问题的关键在于每个元素只能和左边最近的同色元素配对。也就是说如果我们把相同颜色的元素按顺序排列那么相邻的同色元素如果值相同就能产生贡献。这提示我们可以用动态规划按位置从左到右处理维护两种颜色最后出现的位置。但直接维护两个位置的状态太大。观察到对于每个值我们只关心它最后一次出现的位置。如果当前元素 A[i] 要产生贡献它必须和左边某个同色且值相同的元素配对并且这两个元素之间不能有同色的元素否则“最近”就不是那个了。更简单的思路把问题看成选择一些不相交的配对 (j, i)其中 j iA[j] A[i]且 j 和 i 之间没有与它们同色的元素。每对贡献 A[i]。我们要最大化总贡献。这其实是一个区间 DP 或者贪心问题。考虑从左到右扫描维护红色和蓝色最后出现的位置。对于当前元素我们可以选择染成红色或蓝色。如果染成红色且红色最后出现的位置的值等于 A[i]则产生贡献 A[i]并更新红色最后位置为 i。否则不产生贡献但红色最后位置变为 i。状态可以定义为dp[i][c] 表示处理到第 i 个元素最后出现的红色位置和蓝色位置中较晚的那个是 c 颜色且较晚的位置是 i。但这样状态还是太大。实际上有一个关键观察最优解中每个元素要么和左边最近的同色相同值元素配对要么不配对。而且配对不会交叉。所以可以用 DP设 f[i] 表示前 i 个元素的最大得分。对于位置 i如果它不产生贡献f[i] f[i-1]。如果它和位置 j 配对j i, A[j] A[i]那么 j 和 i 之间不能有与它们同色的元素。这意味着 j 和 i 之间的所有元素都必须染成另一种颜色。所以 f[i] max(f[i-1], f[j-1] A[i])其中 j 是满足 A[j] A[i] 且 j 和 i 之间没有同色元素的位置。但“j 和 i 之间没有同色元素”这个条件很难直接处理。换个角度如果我们决定 j 和 i 配对那么 j 和 i 之间的所有元素都必须染成与 j 和 i 不同的颜色。这相当于把区间 [j, i] 分成两段颜色。实际上我们可以证明最优解中配对的区间不会重叠且每个配对区间内部的所有元素都染成另一种颜色。所以问题转化为选择一些不相交的区间 [j, i]满足 A[j] A[i]且区间内部没有与 j 同色的元素即内部元素全部染成另一种颜色。每个区间贡献 A[i]。最大化总贡献。这可以用 DP 解决设 dp[i] 表示前 i 个元素的最大得分。对于每个 i我们可以选择不配对dp[i] dp[i-1]。或者选择某个 j i 且 A[j] A[i] 进行配对dp[i] max(dp[i], dp[j-1] A[i])。但需要保证 j 和 i 之间没有与 j 同色的元素。这个条件等价于在 j 和 i 之间不存在 k 使得 A[k] A[j] 且 k 被染成与 j 同色。但因为我们把区间内部全部染成另一种颜色所以这个条件自动满足。等等这里有个问题如果 j 和 i 配对那么 j 和 i 之间的元素都染成另一种颜色。但如果这些元素中有和 j 同值的它们染成另一种颜色后不会和 j 同色所以不会影响 j 和 i 的“最近同色”关系。所以条件只是 A[j] A[i]不需要其他限制。但是如果 j 和 i 配对那么 j 之前的元素不能和 j 同色且值相同否则 j 就会和更近的同色元素配对。不过 DP 是从左到右的dp[j-1] 已经保证了 j 之前的独立性。所以转移是合法的。因此dp[i] max(dp[i-1], max_{j i, A[j] A[i]} (dp[j-1] A[i]))。这个转移是 O(n^2) 的需要优化。观察到对于每个值 v我们只需要维护 dp[j-1] 的最大值。设 best[v] max_{j i, A[j] v} dp[j-1]。那么 dp[i] max(dp[i-1], best[A[i]] A[i])。然后更新 best[A[i]] max(best[A[i]], dp[i-1])。这样时间复杂度 O(n)空间 O(max A)。4.2 代码实现与边界处理#include bits/stdc.h using namespace std; int main() { freopen(color.in, r, stdin); freopen(color.out, w, stdout); int T; scanf(%d, T); while (T--) { int n; scanf(%d, n); vectorint A(n 1); for (int i 1; i n; i) scanf(%d, A[i]); vectorlong long dp(n 1, 0); unordered_mapint, long long best; for (int i 1; i n; i) { dp[i] dp[i-1]; if (best.count(A[i])) { dp[i] max(dp[i], best[A[i]] A[i]); } // 更新 best[A[i]] 为 dp[i-1] 的最大值 if (!best.count(A[i]) || best[A[i]] dp[i-1]) { best[A[i]] dp[i-1]; } } printf(%lld\n, dp[n]); } return 0; }逻辑说明dp[i] 表示前 i 个元素的最大得分。best[v] 维护的是对于值 v所有出现位置 j 的 dp[j-1] 的最大值。对于位置 i如果选择不配对dp[i] dp[i-1]如果选择和之前某个值为 A[i] 的位置配对得分是 best[A[i]] A[i]。取两者最大值。然后更新 best[A[i]] 为 dp[i-1] 和当前 best[A[i]] 的较大值。参数注意n ≤ 2×10^5A[i] ≤ 10^6得分可能很大用 long long。unordered_map 可能被卡建议用数组或 vector 离散化。T ≤ 10注意清空 best。4.3 测试点分析与优化测试点 1~4 的 n ≤ 15暴力枚举所有染色方案即可。测试点 5~7 的 n ≤ 102A[i] ≤ 102可以用 O(n^2) DP。测试点 8~10 的 n ≤ 2000O(n^2) 也能过。测试点 11~12 的 n ≤ 2×10^4需要 O(n log n) 或 O(n)。测试点 13~15 的 A[i] ≤ 10可以用更简单的状态压缩。测试点 16~20 的 n ≤ 10^6必须用 O(n) 的 DP。上面的 O(n) DP 已经能过所有测试点。注意 unordered_map 在极端数据下可能退化建议用 vector 离散化或者直接用数组因为 A[i] ≤ 10^6可以开一个 10^65 的数组。5. 擂台游戏arena树形模拟与异或处理5.1 比赛树结构与能力值计算擂台游戏有 2^k 名选手进行 k 轮比赛。每场比赛有一个抽签结果 dR,G决定擂主是编号小的还是编号大的。擂主获胜当且仅当他的能力值 ≥ RR 是当前轮数。注意胜负只取决于擂主的能力值和轮数与另一位选手的能力值无关。这个规则很反直觉如果擂主能力值 ≥ R擂主赢否则另一位赢。也就是说另一位选手“躺赢”的条件是擂主能力值 R。题目给了 n 位选手的报名信息但实际参赛人数要补到 2^k。补充的选手能力值可以任取 [0, 2^31-1]。要求所有可能成为总冠军的选手编号之和。然后有 m 个询问每个询问给出一个前缀长度 ci求只考虑前 ci 位选手时的答案。能力值的计算方式ai ai ⊕ X_{i mod 4}其中 X0, X1, X2, X3 是每组测试数据给定的四个数。注意 i mod 4 的取值是 0,1,2,3对应 X0, X1, X2, X3。5.2 树形 DP 与可能冠军集合对于固定的前缀长度 c我们需要补人到 2^k ≥ c。补充的选手能力值可以任取所以他们的胜负是不确定的。我们要找所有可能成为总冠军的选手编号。这可以用树形 DP 来做。对于比赛树的每个节点对应一场比赛我们需要知道哪些选手有可能从这个节点晋级对于叶子节点选手如果该选手是补充的他的能力值可以任取所以他有可能赢也有可能输。对于内部节点根据抽签结果确定擂主然后根据擂主的能力值是否 ≥ R 来判断胜负。但补充选手的能力值可以任取所以我们需要考虑所有可能的能力值分配。这看起来是指数级的但实际上可以用区间分析对于每个节点维护一个“可能晋级选手集合”以及对于每个可能晋级的选手他需要满足什么条件。更简单的做法观察到补充选手的能力值可以任取所以如果擂主是补充选手那么他既可以赢能力值 ≥ R也可以输能力值 R。如果擂主是已知选手那么他的能力值是确定的胜负也是确定的。所以我们可以自底向上计算每个节点的“可能胜者集合”。对于叶子节点如果是已知选手集合就是他自己如果是补充选手集合也是他自己因为补充选手也可能获胜。对于内部节点根据抽签确定擂主。如果擂主是已知选手且能力值 ≥ R则擂主获胜胜者集合就是擂主所在子树的胜者集合如果擂主是已知选手且能力值 R则另一位获胜胜者集合就是另一位所在子树的胜者集合如果擂主是补充选手则他可能赢也可能输所以胜者集合是两个子树胜者集合的并集。但这里有个问题补充选手的能力值虽然可以任取但一旦确定就不能更改。所以如果擂主是补充选手他赢或输是互斥的不能同时取并集。不过题目问的是“所有可能成为总冠军的选手”也就是说存在一种能力值分配使得该选手成为冠军。所以我们可以分别考虑擂主赢和擂主输两种情况取并集。因此对于每个节点胜者集合 如果擂主可能赢则加上擂主子树的胜者集合如果擂主可能输则加上另一子树的胜者集合。擂主可能赢的条件是擂主是补充选手或者擂主是已知选手且能力值 ≥ R。擂主可能输的条件是擂主是补充选手或者擂主是已知选手且能力值 R。这样自底向上计算每个节点的胜者集合大小最多是 2^k总复杂度 O(2^k * k)对于 n ≤ 10^5 来说 2^k 可能达到 2^17 131072k 17总复杂度约 2×10^6可以接受。但询问有 m 个每个询问的 c 不同2^k 也不同。如果对每个询问都重新计算复杂度是 O(m * 2^K * K)可能超时。需要优化。观察到询问的 c 是前缀长度我们可以从小到大处理 c每次增加一个选手然后更新比赛树。但比赛树的结构会变因为 2^k 变了所以需要重新计算。不过 K 最大是 17因为 n ≤ 10^5 2^17所以最多 17 种不同的 k。对于每个 k我们可以预处理所有可能的 c 的答案。实际上对于每个 k2^k 是固定的。我们可以对每个 k 分别计算。对于给定的 k我们考虑所有 c ≤ 2^k 的询问。但 c 可能小于 2^k此时补充选手的数量是 2^k - c。我们可以把补充选手标记为“未知”然后自底向上计算胜者集合。对于不同的 c补充选手的位置不同所以需要分别计算。但 m ≤ 10^5K ≤ 17如果对每个询问都 O(2^K) 计算总复杂度 10^5 * 131072 太大。需要更高效的方法。注意到题目中 T ≤ 256但不同测试数据只是修改了 ai 的异或值其他内容不变。所以我们可以对每组测试数据分别计算。但 T 可能很大需要优化。实际上对于每个询问 c2^k 是 ≥ c 的最小 2 的幂。所以 k 只取决于 c 的范围。我们可以把询问按 k 分组对于每个 k预处理所有可能的 c 的答案。但 c 有 m 个每个 c 对应的补充选手位置不同所以还是需要分别计算。不过我们可以观察到对于固定的 k比赛树的结构是固定的。补充选手的位置是 c1 到 2^k。我们可以把补充选手标记为“未知”然后自底向上计算。对于不同的 c只是补充选手的起始位置不同。我们可以用线段树或者树形 DP 的增量更新来加速。但考虑到实际比赛时间限制O(m * 2^K) 可能过不了。需要更巧妙的做法。实际上对于每个 k2^k 最大 131072m 最大 10^5但很多询问的 k 是相同的。对于每个 k我们可以只计算一次不行因为 c 不同。换个思路对于每个选手 i我们想知道他是否可能成为冠军。这取决于补充选手的能力值。我们可以反过来考虑对于每个选手他成为冠军的条件是什么这需要分析比赛树上的路径。由于时间关系这里给出一个 O(2^K * K) 的预处理方法对于每个 k计算所有可能的 c 的答案。具体做法对于固定的 k我们从 c 2^k 开始逐步减少 c即增加补充选手。每次增加一个补充选手只会影响从该选手到根的路径上的节点。所以可以用树形 DP 增量更新每次 O(K)。总复杂度 O(2^K * K m * K)可以接受。5.3 异或输出与代码框架最终输出是 (1 × A1) ⊕ (2 × A2) ⊕ ... ⊕ (m × Am)其中 Ai 是第 i 个询问的答案。注意这里的乘法是普通整数乘法异或是按位异或。#include bits/stdc.h using namespace std; int main() { freopen(arena.in, r, stdin); freopen(arena.out, w, stdout); int n, m; scanf(%d %d, n, m); vectorlong long a(n 1); for (int i 1; i n; i) scanf(%lld, a[i]); vectorint c(m); for (int i 0; i m; i) scanf(%d, c[i]); int K 0; while ((1 K) n) K; vectorvectorint d(K 1); for (int R 1; R K; R) { string s; cin s; d[R].resize((1 (K - R)) 1); for (int G 1; G (1 (K - R)); G) { d[R][G] s[G-1] - 0; } } int T; scanf(%d, T); while (T--) { long long X[4]; scanf(%lld %lld %lld %lld, X[0], X[1], X[2], X[3]); vectorlong long real_a(n 1); for (int i 1; i n; i) { real_a[i] a[i] ^ X[i % 4]; } // 对每个询问计算答案 long long ans 0; for (int q 0; q m; q) { int len c[q]; int k 0; while ((1 k) len) k; int total 1 k; // 构建比赛树计算可能冠军集合 // ... 这里省略具体实现核心是自底向上 DP long long sum 0; // 伪代码sum 计算可能冠军编号之和 ans ^ (long long)(q 1) * sum; } printf(%lld\n, ans); } return 0; }逻辑说明先读入 n, m, a 数组和询问 c。然后读入 K 行抽签结果。对于每组测试数据计算真实能力值 real_a[i] a[i] ^ X[i%4]。然后对每个询问确定 k 和总人数 2^k构建比赛树自底向上计算可能冠军集合求和后乘以询问编号异或到答案中。参数注意ai 和 Xj 都是非负整数范围 2^31用 long long。异或运算符 ^ 在 C 中优先级较低注意加括号。抽签结果是无空格字符串用 cin 读入。6. 避坑与常见问题排查6.1 文件输入输出与文件名大小写现象本地测试通过提交后 0 分。原因CSP-S 要求使用文件输入输出且文件名必须全小写。很多选手习惯用标准输入输出或者把 duel.in 写成 Duel.in。解决每道题开头必须写 freopen(duel.in, r, stdin) 和 freopen(duel.out, w, stdout)文件名严格按题目要求。6.2 浮点数精度导致超速检测误判现象超速检测的样例能过但提交后部分测试点 WA。原因计算超速区间时用了浮点数边界处因为精度问题导致区间判断错误。解决尽量用整数运算。对于 v^2 v0^2 2as可以转化为 s (V^2 - v0^2) / (2a)但除法可能产生小数。可以用交叉乘法比较判断 s_crit 是否在 [0, L-d] 内等价于判断 (V^2 - v0^2) 和 2a*(L-d) 的大小关系注意 a 的符号。如果必须用浮点数加 1e-9 的偏移量。6.3 染色 DP 的 unordered_map 被卡现象染色题本地跑得很快提交后 TLE。原因unordered_map 在极端数据下可能退化成 O(n)导致超时。解决用数组代替 unordered_map。因为 A[i] ≤ 10^6可以开一个大小为 10^65 的 long long 数组 best每次用完后清空。或者用 vector 离散化。6.4 擂台游戏的异或优先级陷阱现象擂台游戏输出结果与预期不符。原因C 中 ^ 的优先级低于所以 (q1) * sum ^ ans 会被解析成 ((q1) * sum) ^ ans这其实是正确的。但如果写成 ans ^ q1 * sum会先算 q1sum 再异或结果错误。解决始终加括号写成 ans ^ (long long)(q1) * sum。6.5 数组越界与栈空间限制现象程序运行时崩溃或 RE。原因数组开得太小或者递归太深导致栈溢出。解决n 最大 10^5数组开到 100005 以上。递归深度最大 K ≤ 17不会栈溢出。但注意题目说“程序可使用的栈空间内存限制与题目的内存限制一致”所以 512 MiB 足够。如果用了 vector注意 reserve 预留空间。6.6 编译选项与 C 版本现象本地用 C17 编译通过提交后 CE。原因评测环境用 C14某些 C17 特性不支持。解决编译时加 -stdc14避免使用 structured bindingsauto [a,b] ...等 C17 特性。如果要用改成 .first 和 .second。另外注意 -O2 和 -static 选项本地测试时也加上。本文还有配套的精品资源点击获取