2024 CSP-S 复赛真题及答案解析（完整版）｜四题全解
本文分两部分：前半部分为 2024 CSP-S 第二轮（复赛）完整真题，后半部分为四道题的详细解析与参考代码。2024 年 S 组呈现"两易两难"：T1 双指针贪心、T2 区间覆盖送分，T3 线段树优化 DP 是区分点，T4 擂台游戏是压轴难题。建议先通读真题、独立尝试，再对照解析查漏补缺。
获取 2024CSP-S复赛真题及解析.pdf
请关注状元编程公众号，回复 20260929csp-s
第一部分：真题原文
考试说明
考试：CSP-S 2024 第二轮认证（提高级） 时间：2024 年 10 月 26 日 四道题：决斗（Duel）、超速检测（Detect）、染色（Color）、擂台游戏（Arena）
T1 决斗（Duel）
【题目描述】
今天是小 Q 的生日，他得到了 n 张卡牌作为礼物。这些卡牌属于火爆的"决斗怪兽"，其中，第 i 张卡代表一只攻击力为 rᵢ、防御力也为 rᵢ 的怪兽。
一场游戏分为若干回合。每回合，小 Q 会选择某只怪兽 i 以及另一只怪兽 j（i≠j），并让怪兽 i 向怪兽 j 发起攻击。此时，若怪兽 i 的攻击力小于等于怪兽 j 的防御力，则无事发生；否则，怪兽 j 的防御被打破，怪兽 j 退出游戏不再参与到剩下的游戏中。一只怪兽在整场游戏中至多只能发起一次攻击。当未退出游戏的怪兽都已发起过攻击时，游戏结束。
小 Q 希望决定一组攻击顺序，使得在游戏结束时，未退出游戏的怪兽数量尽可能少。
【输入格式】 第一行一个正整数 n；第二行 n 个正整数，第 i 个表示第 i 个怪兽的攻击力及防御力 rᵢ。
【输出格式】 输出一行一个整数，表示游戏结束时未退出游戏的怪兽数量的最小值。
【样例 1】
输入:51 2 3 1 2输出:2【样例 2】
输入:10136 136 136 2417 136 136 2417 136 136 136输出:8【数据范围】 1 ≤ n ≤ 10⁵，1 ≤ rᵢ ≤ 10⁵。特殊性质 A：每个 rᵢ 在可能值域中独立均匀随机生成。
T2 超速检测（Detect）
【题目描述】
小 D 新入职了某国的交管部门，第一个任务是负责一条长度为 L 的南北主干道的车辆超速检测。
这个周末，主干道上预计出现 n 辆车，第 i 辆车从距离最南端 dᵢ 的位置驶入，以 vᵢ 的初速度和 aᵢ 的加速度做匀加速运动向北行驶。只考虑从南向北的车辆，故 vᵢ>0，但 aᵢ 可正可负，也可以为零。当车辆行驶到主干道最北端（距离最南端 L 的位置）或速度降为 0（只在 aᵢ<0 时发生）时，该车驶离主干道。
主干道上设置了 m 个测速仪，第 j 个位于距离最南端 pⱼ 的位置，每个测速仪可设置开启或关闭。当某辆车经过某个开启的测速仪时，若这辆车的瞬时速度超过道路限速 V，则这辆车被判定为超速。
上司想知道：① 若所有测速仪都开启，有多少辆车被判定为超速；② 为了不漏掉超速的车，最多可以关闭多少个测速仪。
【输入格式】 第一行一个正整数 T（数据组数）。每组：第一行四个整数 n, m, L, V；接下来 n 行每行三个整数 dᵢ, vᵢ, aᵢ；最后一行 m 个整数 p₁, p₂, …, pₘ。
【输出格式】 每组输出一行两个整数：全开测速仪时被判定超速的车辆数、不漏超速车时最多可关闭的测速仪数。
【样例】
输入:15 5 15 30 3 012 4 01 1 45 5 -26 4 -42 5 8 9 15输出:3 3【数据范围】 1 ≤ T ≤ 20；1 ≤ n,m ≤ 10⁵，1 ≤ L ≤ 10⁶，1 ≤ V ≤ 10³；0 ≤ dᵢ < L，1 ≤ vᵢ ≤ 10³，|aᵢ| ≤ 10³；0 ≤ p₁ < p₂ < … < pₘ ≤ L。特殊性质 A：aᵢ=0；B：aᵢ>0；C：aᵢ<0 且所有车都不在最北端驶离。
【提示】 匀加速运动位移为 s 时，瞬时速度 v = √(v₀² + 2·a·s)。
T3 染色（Color）
【题目描述】
给定一个长度为 n 的正整数数组 A，所有数从左至右排成一排。你需要将 A 中的每个数染成红色或蓝色之一，然后计算最终得分：
设 C 为长度为 n 的整数数组，对于 A 中的每个数 Aᵢ（1 ≤ i ≤ n）：
如果 Aᵢ 左侧没有与其同色的数，则令 Cᵢ = 0。 否则，记其左侧与其最靠近的同色数为 Aⱼ，若 Aᵢ = Aⱼ，则令 Cᵢ = Aᵢ，否则令 Cᵢ = 0。
最终得分为 ΣCᵢ。你需要最大化最终得分，求最大值。
【输入格式】 多组测试数据。第一行一个正整数 T；每组：第一行 n，第二行 n 个正整数 A₁, A₂, …, Aₙ。
【输出格式】 每组输出一行一个非负整数，表示最终得分的最大可能值。
【样例】
输入:331 2 141 2 3 483 5 2 5 1 2 1 4输出:108【数据范围】 1 ≤ T ≤ 10，2 ≤ n ≤ 2×10⁵，1 ≤ Aᵢ ≤ 10⁶。
T4 擂台游戏（Arena）
【题目描述】
小 S 想要举办一场擂台游戏，共有 2ᵏ 名选手，游戏分为 k 轮：第一轮编号 1,2 的选手对局、3,4 对局、……；第二轮相邻两位胜者依次对局；以此类推直到决赛。
每位选手都有能力值 aᵢ（[0, 2³¹−1] 内的整数）。每场比赛先抽签决定一个数 0/1，记第 R 轮第 G 场抽到的数为 d(R,G)。抽到 0 表示编号小的选手为擂主，抽到 1 表示编号大的选手为擂主。擂主获胜当且仅当他的能力值 a ≥ R——胜负只取决于擂主能力值与轮次的大小关系，与另一位能力值无关。
小 S 陆续收到 n 位选手报名，按先后顺序编号 1,2,…,n。补充尽量少的选手使总人数为 2 的整次幂（补充选手能力值可任取），求所有可能成为总冠军的选手的编号之和。小 S 给了 m 个询问 cᵢ，对每个 cᵢ 求只收到前 cᵢ 位选手报名时的答案。
【输入格式】 第一行 n, m；第二行 n 个非负整数 a′₁,…,a′ₙ（用于计算真正能力值）；第三行 m 个正整数 c₁,…,cₘ；接下来 K 行抽签序列（K 为使 2^K ≥ n 的最小非负整数）；再一行一个正整数 T（测试数据组数）；接下来 T 行每行 4 个非负整数 X₀,X₁,X₂,X₃，该组能力值 aᵢ = a′ᵢ ⊕ (Xᵢ mod 4)。
【输出格式】 共 T 行，每行输出 (1×A₁) ⊕ (2×A₂) ⊕ … ⊕ (m×Aₘ) 的结果（Aᵢ 为第 i 组询问的答案）。
【样例】
输入:5 50 0 0 0 05 4 1 2 3100110142 1 0 01 2 1 00 2 3 12 2 0 1输出:51971【数据范围】 2 ≤ n,m ≤ 10⁵，0 ≤ aᵢ, Xⱼ < 2³¹，1 ≤ cᵢ ≤ n，1 ≤ T ≤ 256。特殊性质 A：询问的 cᵢ 均为 2 的幂次；B：所有 d(R,G)=0。
第二部分：题目解析
T1 决斗（Duel）｜双指针贪心
考点：排序 / 双指针贪心 难度：普及−，2024 年 T1 送分
思路：排序后，小怪兽只能被更大的怪兽杀死，一只怪兽杀死一只。双指针：i 指向"待消灭"的怪兽（防御小），j 指向"攻击者"；当 r[j] > r[i] 时消灭一对（i++, j++），否则 j++（攻击者不够强，换更大的）。幸存数 = n − 消灭数。
易错点：① 攻击者必须严格大于被攻击者（≤ 则无事发生）；② 每只怪兽只能攻击一次。
#include<bits/stdc++.h>usingnamespace std;constint MAXN = 100005;int n, r[MAXN];intmain(){ ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n;for (int i = 0; i < n; i++) cin >> r[i];sort(r, r + n);int i = 0, j = 0; // i: 待消灭者，j: 攻击者while (i < n && j < n) {if (r[j] > r[i]) { i++; j++; } // 攻击者更强 → 消灭一只else j++; // 不够强 → 换更大的攻击者 } cout << n - i << '\n'; // i = 被消灭数return0;}T2 超速检测（Detect）｜区间点覆盖贪心
考点：物理公式转化 / 二分 / 区间点覆盖贪心 难度：普及+/提高−，常规但细节多
思路：
第一步：对每辆车计算超速位置区间（整数端点，避免浮点误差）——超速 ⟺ v² = v₀²+2a(s−d) > V²：
a>0：速度递增，超速区间 [d + ⌈(V²−v₀²+1)/(2a)⌉, L]； a=0：v₀>V 则全程 [d, L] 超速； a<0：速度递减，v₀≤V 则无；否则超速区间 [d, d + ⌊(v₀²−V²−1)/(−2a)⌋]，并与驶离位置 min(L, 停车点) 求交。
第一问：区间内是否存在测速仪（测速仪位置排序 + 二分）。
第二问：超速区间按右端点升序排序，用经典"最小点覆盖区间"贪心——对未覆盖区间在"≤ 其右端点的最大测速仪"处放点；最少保留数 = 覆盖所有区间的点数；答案 = m − 最少保留数。
易错点：① 严格大于 V（用 +1 处理整数不等式）；② a<0 时不等式两边同乘负数要变号；③ 驶离点截断区间。
#include<bits/stdc++.h>usingnamespace std;typedeflonglong ll;structInterval { ll l, r; };intmain(){ ios::sync_with_stdio(false); cin.tie(nullptr);int T; cin >> T;while (T--) {int n, m; ll L, V; cin >> n >> m >> L >> V;vector<ll> d(n + 1), v(n + 1), a(n + 1);for (int i = 1; i <= n; i++) cin >> d[i] >> v[i] >> a[i];vector<ll> p(m);for (int i = 0; i < m; i++) cin >> p[i];sort(p.begin(), p.end()); vector<Interval> segs; ll cnt1 = 0;for (int i = 1; i <= n; i++) { ll l = -1, r = -1;if (a[i] > 0) { ll num = V * V - v[i] * v[i] + 1; ll off = num <= 0 ? 0 : (num + 2 * a[i] - 1) / (2 * a[i]); l = d[i] + off; r = L; } elseif (a[i] == 0) {if (v[i] > V) { l = d[i]; r = L; } } else {if (v[i] > V) { ll stopDisp = v[i] * v[i] / (-2 * a[i]); ll R = min(L, d[i] + stopDisp); ll num = v[i] * v[i] - V * V - 1; l = d[i]; r = min(R, d[i] + num / (-2 * a[i])); } }if (l != -1 && l <= r) {auto it = lower_bound(p.begin(), p.end(), l);if (it != p.end() && *it <= r) { cnt1++; segs.push_back({l, r}); } } }sort(segs.begin(), segs.end(), [](const Interval& x, const Interval& y) {return x.r != y.r ? x.r < y.r : x.l < y.l; }); ll keep = 0, cur = -4e18;for (auto &sg : segs) {if (cur >= sg.l && cur <= sg.r) continue;auto it = upper_bound(p.begin(), p.end(), sg.r); --it; cur = *it; keep++; } cout << cnt1 << ' ' << m - keep << '\n'; }return0;}T3 染色（Color）｜分段 DP + 线段树区间加
考点：动态规划 / 线段树区间加 / 贪心分段模型 难度：提高，2024 年最有区分度的题
思路：
关键建模：把染色序列按颜色分成若干连续同色段——同色段内任意位置与"左侧最近同色"同段，故段内值 x 出现 t 次贡献 (t−1)·x；不同段之间无贡献。
dp[i] = 前 i 个位置的最大得分，score(j+1, i) = 段 (j+1..i) 的贡献 = Σₓ (cntₓ−1)·x。 dp[i] = max over j ( dp[j] + score(j+1, i) )。 用 last[x]（x 上一次出现位置）：处理 i 时，对所有 j ≤ last[Aᵢ]−1，score(j+1,i) 增加 Aᵢ（Aᵢ 在段内已出现过）→ 区间加。 线段树维护 best[j] = dp[j] + score(j+1, i) 的最大值，O(n log n)。
易错点：① 段内贡献是 (t−1)·x（第一个出现无贡献）；② 区间加范围 j ∈ [0, last−1]；③ 每步先区间加、再取全局最大、再把 dp[i] 作为新段起点插入。
#include<bits/stdc++.h>usingnamespace std;typedeflonglong ll;constint MAXN = 200005;int n;ll A[MAXN];ll dp[MAXN];int lastPos[MAXN];ll seg[4 * MAXN], lazy[4 * MAXN];voidpushdown(int p){if (lazy[p]) { seg[p*2] += lazy[p]; seg[p*2+1] += lazy[p]; lazy[p*2] += lazy[p]; lazy[p*2+1] += lazy[p]; lazy[p] = 0; }}voidadd(int p, int l, int r, int ql, int qr, ll val){if (ql > r || qr < l) return;if (ql <= l && r <= qr) { seg[p] += val; lazy[p] += val; return; }pushdown(p);int mid = (l + r) / 2;add(p*2, l, mid, ql, qr, val);add(p*2+1, mid+1, r, ql, qr, val); seg[p] = max(seg[p*2], seg[p*2+1]);}voidsetv(int p, int l, int r, int pos, ll val){if (l == r) { seg[p] = val; lazy[p] = 0; return; }pushdown(p);int mid = (l + r) / 2;if (pos <= mid) setv(p*2, l, mid, pos, val);elsesetv(p*2+1, mid+1, r, pos, val); seg[p] = max(seg[p*2], seg[p*2+1]);}intmain(){ ios::sync_with_stdio(false); cin.tie(nullptr);int T; cin >> T;while (T--) { cin >> n;for (int i = 1; i <= n; i++) cin >> A[i];vector<ll> tim(1000005, 0);for (int i = 0; i < 4 * (n + 2); i++) seg[i] = lazy[i] = 0;setv(1, 0, n, 0, 0);for (int i = 1; i <= n; i++) { ll x = A[i];int lst = tim[x];if (lst > 0) add(1, 0, n, 0, lst - 1, x); dp[i] = seg[1];setv(1, 0, n, i, dp[i]); tim[x] = i; } cout << dp[n] << '\n'; }return0;}T4 擂台游戏（Arena）｜线段树区间合并
考点：线段树 / 区间合并 / 位运算（异或）/ 分治 难度：省选，2024 年压轴难题
思路：
每个选手 i 的能力值 aᵢ = a′ᵢ ⊕ (Xᵢ mod 4)。擂台胜负只取决于擂主能力值与轮次：抽到 0 编号小者为擂主，抽到 1 编号大者为擂主；擂主能力 ≥ 轮次 R 则擂主胜。 对长度为 2ᵏ 的完整赛程，定义区间信息：若区间全部是"补充选手"（能力可任取），该区间可能产生的冠军是全集；否则维护"可能冠军集合"的压缩表示（用区间能力最大/次大值压缩）。 合并左右子区间时按抽签 d(R,G) 决定擂主侧，讨论擂主能否取胜，得到父区间的可能冠军集合。 对询问 cᵢ：只取前 2ᵏ ≥ cᵢ 轮的数据；真实选手之外补"万能选手"（能力任取，可当作阈值 ±∞）；从叶子向根合并 → 根集合中真实选手编号和。 输出 ans = (1×A₁) ⊕ (2×A₂) ⊕ … ⊕ (m×Aₘ)（用 long long）。
该题实现难度大（约 300 行：线段树 + 位运算 + 冠军集合压缩），建议考场争取部分分（特殊性质 A：cᵢ 均为 2 的幂次；性质 B：所有 d=0）。
四题考点总结
💡 年份点评：2024 年"两易两难"——T1 贪心、T2 区间覆盖送分到位；T3 线段树优化 DP 属"经典模型 + 经典优化"；T4 是全场最难的区间合并题。T3 的"同色段 + last 出现位置 + 区间加"三步转化是近几年最典型的 DP 优化套路；T2 提醒把运动学公式转成整数不等式避免精度坑。T3 拿满、T4 拿部分分即为高分。
本文真题基于 2024 CSP-S 第二轮认证官方试卷整理，答案与解析供学习参考，最终以 CCF 官方发布为准。祝各位同学复赛顺利！
