ARTICLE · 1211418
2022 CSP-S 复赛真题及答案解析(完整版)|四题全解
2022 CSP-S 复赛真题及答案解析（完整版）｜四题全解
2022 年 CSP-S 第二轮（2022 年 10 月 29 日）共 4 题，难度分布均匀、整体偏难。本文按「真题原文 + 逐题解析」组织，读者可先做真题、再看解析。
获取 2022CSP-S真题及解析.pdf
请关注状元编程公众号，回复 20261019csp-s
四题速览
第一部分：真题原文
T1 假期计划（Holiday）
题目描述
小熊的地图上有 n 个点，编号为 1 的是它的家，编号 2,3,…,n 都是景点。部分点对之间有双向直达的公交线路。如果点 x 与 z₁、z₁ 与 z₂、……、zₖ 与 y 之间均有直达线路，则称 x 与 y 之间的行程可转车 k 次通达；特别地，x 与 y 直达称为转车 0 次通达。
小熊计划从家出发去 4 个不同的景点游玩，完成 5 段行程后回家：家 → A → B → C → D → 家，且每段行程最多转车 k 次。转车时经过的点没有任何限制（可以是家、景点，也可重复）。每个景点都有一个分数，求访问的 4 个不同景点分数之和的最大值。
输入格式
第一行三个整数 n,m,k，分别表示点数、直达点对数、每段行程最多转车次数。第二行 n−1 个正整数，为景点 2,3,…,n 的分数。接下来 m 行每行两个正整数 x,y，表示点 x 和 y 之间直接相连（无重边、自环）。
输出格式
输出一个正整数，表示 4 个不同景点分数之和的最大值。
样例 1
输入：
8 8 19 7 1 8 2 3 61 22 33 44 55 66 77 88 1输出：
27样例 2
输入：
7 9 01 1 1 2 3 41 22 33 41 51 61 75 46 47 4输出：
7数据范围：5≤n≤2500，1≤m≤10000，0≤k≤100，景点分数 1≤sᵢ≤10¹⁸，保证至少存在一组符合要求的行程。
T2 策略游戏（Game）
题目描述
有一个长度为 n 的数组 A 和长度为 m 的数组 B，定义矩阵 C，满足 Cᵢⱼ = Aᵢ × Bⱼ（下标从 1 开始）。
游戏进行 q 轮。每轮给出 l₁,r₁,l₂,r₂（1≤l₁≤r₁≤n，1≤l₂≤r₂≤m）。小 L 先选一个 l₁r₁ 之间的下标 x，然后小 Q 选一个 l₂r₂ 之间的下标 y，得分是 C_xy。小 L 目标是使得分尽可能大，小 Q 使得分尽可能小，两人都采用最优策略。求每轮游戏的最优得分。
输入格式
第一行 n,m,q。第二行 n 个整数 Aᵢ，第三行 m 个整数 Bᵢ。接下来 q 行每行四个正整数 l₁,r₁,l₂,r₂。
输出格式
q 行，每行一个整数，表示该轮最优策略下的得分。
样例 1
输入：
3 2 20 1 -2-3 41 3 1 22 3 2 2输出：
04数据范围：1≤n,m,q≤10⁵，−10⁹≤Aᵢ,Bᵢ≤10⁹。
T3 星战（Galaxy）
题目描述
我方在宇宙中建立 n 个据点，以 m 个单向虫洞连接。把终点为据点 u 的所有虫洞归为据点 u 的虫洞。
敌人的有效打击分两类：① 摧毁某个虫洞（不影响据点）；② 摧毁某个据点 u，导致该据点所有未被摧毁的虫洞（终点为 u 的虫洞）被一同摧毁，而从 u 出发的虫洞不受影响。摧毁只使虫洞不可用，不消除其存在。
我方两种特种部队负责修复：A 型修复某个特定虫洞；B 型修复某据点所有损坏的虫洞。只要据点某条虫洞可用，该据点即可用。
总指挥判断「反攻时刻」的条件：从任何据点出发都能进行无限次虫洞穿梭（实现反击），且当且仅当只有一个从该据点出发的虫洞可用时，该据点能实现连续穿梭；所有据点都同时满足两者时，即为反攻时刻。
你需要根据实时操作，每次操作后判断当前能否进行反攻。
输入格式
第一行 n,m。接下来 m 行每行 u,v，表示从 u 出发到 v 的虫洞（u≠v，无重复）。接下来一行 q，之后 q 行操作：
t=1 u v：摧毁从 u 到 v 的虫洞（保证存在且未摧毁）； t=2 u：摧毁据点 u； t=3 u v：修复从 u 到 v 的虫洞（保证存在且已摧毁）； t=4 u：修复据点 u。
每次操作后输出 YES 或 NO。
样例 1
输入：
3 62 32 11 21 33 13 2111 3 21 2 31 1 31 1 23 1 33 3 22 31 3 13 1 34 21 3 2输出：
NONOYESNOYESNONONOYESNONO数据范围：1≤n,m,q≤5×10⁵。
T4 数据传输（Transmit）
题目描述
网络有 n 台主机，由 n−1 根网线连成一棵树。主机 a 能直接向主机 b 传信息，当且仅当两者间可通过不超过 k 根网线直接或间接相连（1≤k≤3）。
传输需经若干次转发：选主机 c₁=a,c₂,…,cₘ=b，对 1≤i<m，cᵢ 直接把信息发给 cᵢ₊₁。第 i 台主机处理信息需 vᵢ 单位时间（传输时间忽略）。一次传输总耗时 = Σ v_{cᵢ}。
有 q 次请求，第 i 次从 sᵢ 传数据到 tᵢ，求每次请求的最小耗时。
输入格式
第一行 n,Q,k。第二行 n 个正整数 vᵢ。接下来 n−1 行每行 aᵢ,bᵢ 表示一条网线。接下来 Q 行每行 sᵢ,tᵢ。
输出格式
Q 行，每行一个正整数表示最小耗时。
样例 1
输入：
7 3 31 2 3 4 5 6 71 21 32 42 53 63 74 75 61 2输出：
12123数据范围：1≤n,Q≤2×10⁵，1≤k≤3，1≤vᵢ≤10⁹，sᵢ≠tᵢ。
第二部分：题目解析
T1 假期计划（BFS + 枚举剪枝）
考点：BFS 预处理 / 枚举 / 去重剪枝
思路：
预处理可达性：从每个点 i 做 BFS，得到 ok[i][j]（i 到 j 的边数 ≤ k+1，即"转车 ≤ k 次"）。枚举中间两个景点 B、C：要求 ok[1][B]、ok[B][C]、ok[C][1]均成立。预处理最优端点：对每个 B，维护"最优 A"前三大（满足 ok[1][A] && ok[A][B]且 A≠B，按分数降序）；对每个 C，维护"最优 D"前三大（满足ok[C][D] && ok[D][1]且 D≠C）。取前三是为在枚举 B、C 时保证 A、B、C、D 四者互不相同。枚举 B、C 时，从 bestA[B]、bestD[C] 各取候选组合，校验四景点互异后更新答案。
复杂度：O(n² + n·m)（n≤2500 可过）
易错点：① "转车 k 次" = 边数 ≤ k+1；② 枚举时避免 A/B/C/D 重复；③ 分数达 10¹⁸，用 long long。
完整代码：
#include<bits/stdc++.h>usingnamespace std;typedeflonglong ll;constint MAXN = 2505;int n, m, k;ll score[MAXN];vector<int> g[MAXN];bool ok[MAXN][MAXN];structCand { ll s; int id; };vector<Cand> bestA[MAXN], bestD[MAXN];voidbfs(int s){ queue<pair<int,int>> q; q.push({s, 0}); ok[s][s] = true;while (!q.empty()) {auto [u, d] = q.front(); q.pop();if (d >= k + 1) continue; // 已走 k+1 条边，不再扩展for (int v : g[u])if (!ok[s][v]) { ok[s][v] = true; q.push({v, d + 1}); } }}voidupd(vector<Cand>& v, ll s, int id){ v.push_back({s, id});sort(v.begin(), v.end(), [](Cand a, Cand b){ return a.s > b.s; });if (v.size() > 3) v.pop_back(); // 只保留前三}intmain(){ ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m >> k;for (int i = 2; i <= n; i++) cin >> score[i];for (int i = 0; i < m; i++) {int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); }for (int i = 1; i <= n; i++) bfs(i);for (int b = 2; b <= n; b++)for (int a = 2; a <= n; a++)if (a != b && ok[1][a] && ok[a][b])upd(bestA[b], score[a], a);for (int c = 2; c <= n; c++)for (int d = 2; d <= n; d++)if (d != c && ok[c][d] && ok[d][1])upd(bestD[c], score[d], d); ll ans = -1;for (int b = 2; b <= n; b++)for (int c = 2; c <= n; c++) {if (b == c || !ok[b][c]) continue;for (auto A : bestA[b])for (auto D : bestD[c]) {if (A.id == b || A.id == c || A.id == D.id) continue;if (D.id == b || D.id == c) continue; ans = max(ans, A.s + score[b] + score[c] + D.s); } } cout << ans << '\n';return0;}T2 策略游戏（ST 表 + 博弈分类）
考点：ST 表 / RMQ / 博弈分类讨论
思路：
乘积的最值只取决于区间极值。小 L 想让 A_x×B_y 最大，需分正负性讨论：
维护 A 区间的：最大正数、最大负数（最接近 0）、最小负数（最负）、是否含 0； 维护 B 区间的：最小值、最大值。
小 L 的策略分三类：
取正数 x>0：小 Q 会选最小 B 使乘积最小 → 贡献 = 最大正数 × minB； 取负数 x<0：小 Q 会选最大 B 使乘积最小 → 若 maxB≥0，贡献 = 最大负数 × maxB；若 maxB<0（负负得正），小 L 应选最负的负数 → 贡献 = 最小负数 × maxB； 可取 0：贡献 ≥ 0。
三者取最大即最优得分。
复杂度：O((n+m) log(n+m) + q)
易错点：① 分类必须完整（含 0 的情况）；② 负负得正，正负性分开维护；③ 值域 ±10⁹，乘积用 long long；④ 判断区间是否含 0 用前缀和，避免每轮 O(n) 扫描。
完整代码：
#include<bits/stdc++.h>usingnamespace std;typedeflonglong ll;constint MAXN = 100005;const ll NEG = -4e18, POS = 4e18;int n, m, q;ll A[MAXN], B[MAXN];int lg2[MAXN], zero[MAXN];ll mxPos[MAXN][20], mxNeg[MAXN][20], mnNeg[MAXN][20];ll mnB[MAXN][20], mxB[MAXN][20];intmain(){ ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m >> q;for (int i = 1; i <= n; i++) cin >> A[i];for (int i = 1; i <= m; i++) cin >> B[i];for (int i = 2; i <= max(n, m); i++) lg2[i] = lg2[i / 2] + 1;for (int i = 1; i <= n; i++) { mxPos[i][0] = (A[i] > 0 ? A[i] : NEG); mxNeg[i][0] = (A[i] < 0 ? A[i] : NEG); mnNeg[i][0] = (A[i] < 0 ? A[i] : POS); zero[i] = zero[i - 1] + (A[i] == 0); }for (int i = 1; i <= m; i++) { mnB[i][0] = B[i]; mxB[i][0] = B[i]; }for (int j = 1; (1 << j) <= max(n, m); j++)for (int i = 1; i + (1 << j) - 1 <= max(n, m); i++) {if (i + (1 << j) - 1 <= n) { mxPos[i][j] = max(mxPos[i][j-1], mxPos[i + (1<<(j-1))][j-1]); mxNeg[i][j] = max(mxNeg[i][j-1], mxNeg[i + (1<<(j-1))][j-1]); mnNeg[i][j] = min(mnNeg[i][j-1], mnNeg[i + (1<<(j-1))][j-1]); }if (i + (1 << j) - 1 <= m) { mnB[i][j] = min(mnB[i][j-1], mnB[i + (1<<(j-1))][j-1]); mxB[i][j] = max(mxB[i][j-1], mxB[i + (1<<(j-1))][j-1]); } }while (q--) {int l1, r1, l2, r2; cin >> l1 >> r1 >> l2 >> r2;int j1 = lg2[r1 - l1 + 1], j2 = lg2[r2 - l2 + 1]; ll aMaxPos = max(mxPos[l1][j1], mxPos[r1 - (1<<j1) + 1][j1]); ll aMaxNeg = max(mxNeg[l1][j1], mxNeg[r1 - (1<<j1) + 1][j1]); ll aMinNeg = min(mnNeg[l1][j1], mnNeg[r1 - (1<<j1) + 1][j1]); ll bMin = min(mnB[l2][j2], mnB[r2 - (1<<j2) + 1][j2]); ll bMax = max(mxB[l2][j2], mxB[r2 - (1<<j2) + 1][j2]);bool hasZero = (zero[r1] - zero[l1 - 1] > 0); ll best = NEG;if (aMaxPos != NEG) best = max(best, aMaxPos * bMin); // 取最大正数if (aMaxNeg != NEG) { // 取负数if (bMax >= 0) best = max(best, aMaxNeg * bMax); // 取最大负数else best = max(best, aMinNeg * bMax); // 取最小负数(负负得正) }if (hasZero) best = max(best, 0LL); // 取 0 cout << best << '\n'; }return0;}T3 星战（图论性质 + 出度平方和判等）
考点：图论性质 / 哈希 / O(1) 维护
思路：
关键性质转化——「所有点可反击」等价于每个点出度 ≥ 1（能无限穿梭）；「所有点可连续穿梭」等价于每个点出度恰为 1。
「每个点出度恰为 1」不能用「出度和 = n」直接判定（反例：一个点出度 2、另一个点出度 0，和仍 = n）。正确做法是维护出度的平方和 Σout²：因为出度是非负整数，Σout² = n 当且仅当每个点出度都恰为 1。
因此判定反攻 ⟺ 可用边数 = n 且 Σout² = n，O(1) 完成。
维护要点：
「摧毁点 u」影响的是终点为 u 的可用边（该边的起点出度 −1），而非从 u 出发的边； 每条边用状态标记（0 可用 / 1 被边打击毁 / 2 被点打击毁），修复时按状态精确恢复； 出度变化时同步更新 Σout²。
复杂度：O(m + q)
易错点：① 摧毁点影响的是终点为该点的边；② 修复点恢复其所有被点打击毁掉的入边；③ 平方和判等防"和 = n 但分布不均"。
完整代码：
#include<bits/stdc++.h>usingnamespace std;typedeflonglong ll;constint MAXN = 500005;int n, m;structEdge { int u, v; };vector<Edge> edges;vector<int> inEdges[MAXN]; // 终点为 u 的边编号int state[MAXN]; // 0 可用, 1 边打击毁, 2 点打击毁ll outDeg[MAXN];ll cntEdge, sumSq;voidupdateOut(int u, int delta){ sumSq -= outDeg[u] * outDeg[u]; outDeg[u] += delta; sumSq += outDeg[u] * outDeg[u];}intmain(){ ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m; edges.resize(m + 1);for (int i = 1; i <= m; i++) {int u, v; cin >> u >> v; edges[i] = {u, v}; inEdges[v].push_back(i); outDeg[u]++; } cntEdge = m;for (int i = 1; i <= n; i++) sumSq += outDeg[i] * outDeg[i];int q; cin >> q;while (q--) {int t; cin >> t;if (t == 1) { // 摧毁边 (u,v)int u, v; cin >> u >> v;for (int id : inEdges[v])if (edges[id].u == u && state[id] == 0) { state[id] = 1; cntEdge--; updateOut(u, -1); break; } } elseif (t == 2) { // 摧毁点 uint u; cin >> u;for (int id : inEdges[u])if (state[id] == 0) { state[id] = 2; cntEdge--; updateOut(edges[id].u, -1); } } elseif (t == 3) { // 修复边 (u,v)int u, v; cin >> u >> v;for (int id : inEdges[v])if (edges[id].u == u && state[id] == 1) { state[id] = 0; cntEdge++; updateOut(u, +1); break; } } else { // 修复点 uint u; cin >> u;for (int id : inEdges[u])if (state[id] == 2) { state[id] = 0; cntEdge++; updateOut(edges[id].u, +1); } } cout << (cntEdge == n && sumSq == n ? "YES" : "NO") << '\n'; }return0;}T4 数据传输（树上 DP + 倍增 min-plus 矩阵）
考点：树上 DP / 倍增 / min-plus 矩阵
思路（官方算法框架，完整实现约 250 行）：
k=1：主机间只能沿树边逐点传递，答案 = s→t 路径上所有点权和，用树上前缀和 + LCA 即可。
k=2, 3：主机间可跨 2/3 条边直传，路径可绕道"非路径节点"（走支路）。为每个节点设计状态向量：状态 j 表示"当前已连续走了 j 条边（0≤j<k）时，走完剩余路程的最优代价"。
相邻两点的转移写成 (min,+) 意义的 k×k 矩阵（自定义矩阵乘：C[i][j] = min over m (A[i][m] + B[m][j])）。每个点的"点权矩阵"表示经过该点支付 v[u]，并在转移中限制单跳 ≤ k。
倍增预处理：up[u][p] = u 向上 2^p 条边的转移矩阵。查询 s→t 时，把 s 向上段（升序乘）与 t 向上段（逆序乘，注意方向）在 LCA 处合并，最后乘入 LCA 点权。
复杂度：O((n+q) log n × k³)，k≤3
易错点：① 状态维度定义（还需几步到达）；② 矩阵乘法顺序沿路径方向；③ 绕道支路节点的处理要体现在状态里。
四题考点总结
2022 年是「思维转化」考查最强的一年：T2 的乘积博弈分类、T3 的出度平方和判等、T4 的倍增矩阵，是三个高价值方法论，值得反复体会。
