2024 CSP-J 复赛真题及答案解析（完整版）｜四题全解

获取 2024CSP-J复赛真题及解析.pdf

请关注状元编程公众号，回复  20260928csp-j

本文分两部分：前半部分为 2024 CSP-J 第二轮（复赛）完整真题，后半部分为四道题的详细解析与满分 C++ 代码。2024 年复赛 T1/T2 送分，T3 贪心构造是区分点，T4 接龙 DP 是压轴难题。建议先通读真题、独立尝试，再对照解析查漏补缺。

第一部分：真题原文

考试说明

• 考试：CSP-J 2024 第二轮认证（入门级）
• 时间：2024 年 10 月 26 日
• 四道题：扑克牌（poker）、地图探险（explore）、小木棍（stick）、接龙（chain）

T1 扑克牌（poker）

【题目描述】

小 P 从同学小 Q 那儿借来一副 n 张牌的扑克牌。本题中不考虑大小王，此时每张牌具有两个属性：花色和点数。花色共有 4 种：方片、草花、红桃和黑桃。点数共有 13 种，从小到大分别为 A23456789TJQK。注意：点数 10 在本题中记为 T。

一副扑克牌是完整的，当且仅当对于每一种花色和每一种点数，都恰好有一张牌具有对应的花色和点数。由此，一副完整的扑克牌恰好有 4×13=52 张牌。

小 P 借来的牌可能不是完整的，为此小 P 准备再向同学小 S 借若干张牌（小 S 每种牌都有无限张）。小 P 想知道他至少得向小 S 借多少张牌，才能让从小 S 和小 Q 借来的牌中，可以选出 52 张牌构成一副完整的扑克牌。

使用字符 D 代表方片，C 代表草花，H 代表红桃，S 代表黑桃，每张牌通过一个长度为 2 的字符串表示，第一个字符表示花色，第二个字符表示点数，例如 CA 表示草花 A，ST 表示黑桃 T。

【输入格式】 输入的第一行包含一个整数 n 表示牌数。接下来 n 行，每行包含一个长度为 2 的字符串描述一张牌。

【输出格式】 输出一行一个整数，表示最少还需要向小 S 借几张牌才能凑成一副完整的扑克牌。

【样例 1】

输入:1SA输出:51

【样例 2】

输入:4DQH3DQDT输出:49

【数据范围】 对于所有测试数据，保证：1 ≤ n ≤ 52，输入的 n 个字符串每个都代表一张合法的扑克牌。

T2 地图探险（explore）

【题目描述】

小 A 派遣机器人去丛林探险。丛林的地图可以用一个 n 行 m 列的字符表来表示。位置 (i,j)（1 ≤ i ≤ n，1 ≤ j ≤ m）的字符为 x 代表有障碍不可通过；为 . 代表空地可以通过。

机器人的状态由位置和朝向两部分组成。朝向用整数 d 表示：d=0 向东，d=1 向南，d=2 向西，d=3 向北。初始时机器人位置为 (x₀, y₀)，朝向为 d₀（保证初始位置为空地）。接下来进行 k 次操作，每一步：

1. 假设当前位置为 (x,y)，朝向 d，则下一步位置 (x′,y′)：d=0 时 (x,y+1)，d=1 时 (x+1,y)，d=2 时 (x,y−1)，d=3 时 (x−1,y)。
2. 判断 (x′,y′) 是否在地图内且为空地。若成立则向前走一步（位置变为 (x′,y′)，朝向不变）；否则执行"向右转"操作，令 d′=(d+1) mod 4，位置保持不变，朝向变为 d′。

小 A 想知道，在机器人执行完 k 步操作之后，地图上所有被机器人经过的位置（包括起始位置）有几个。

【输入格式】 本题有多组测试数据。输入的第一行包含一个正整数 T，表示数据组数。每组数据：第一行三个正整数 n, m, k；第二行两个正整数 x₀, y₀ 和一个非负整数 d₀；接下来 n 行，每行一个长度为 m 的字符串（只包含 x 和 .）。

【输出格式】 对于每组数据，输出一行包含一个正整数，表示被机器人经过的位置个数。

【样例】

输入:21 5 41 1 2....x5 5 201 1 0......xxx..x.x...xx.x....输出:313

【数据范围】 对于所有测试数据，保证：1 ≤ T ≤ 5，1 ≤ n,m ≤ 10³，1 ≤ k ≤ 10⁶，1 ≤ x₀ ≤ n，1 ≤ y₀ ≤ m，0 ≤ d₀ ≤ 3，且机器人的起始位置为空地。

T3 小木棍（stick）

【题目描述】

小 S 喜欢收集小木棍。在收集了 n 根长度相等的小木棍之后，他闲来无事，便用它们拼起了数字。用小木棍拼每种数字的方法：数字 0、6、9 各需 6 根，1 需 2 根，2、3、5 各需 5 根，4 需 4 根，7 需 3 根，8 需 7 根。

小 S 希望拼出一个正整数，满足如下条件：

• 拼出这个数恰好使用 n 根小木棍；
• 拼出的数没有前导 0；
• 在满足以上两个条件的前提下，这个数尽可能小。

如果不存在正整数满足以上条件，输出 −1 进行报告。

【输入格式】 本题有多组测试数据。输入的第一行包含一个正整数 T，表示数据组数。每组数据一行包含一个整数 n，表示木棍数。

【输出格式】 对于每组数据，输出一行，如果存在满足题意的正整数，输出这个数；否则输出 −1。

【样例】

输入:5123618输出:-1176208

【数据范围】 对于所有测试数据，保证：1 ≤ T ≤ 50，1 ≤ n ≤ 10⁵。

T4 接龙（chain）

【题目描述】

总共有 n 个人参与接龙游戏，第 i 个人会获得一个整数序列 Sᵢ 作为他的词库。一次游戏分为若干轮，每一轮规则如下：

• n 个人中的某个人 p 带着他的词库 Sₚ 进行接龙。若这不是游戏的第一轮，那么这一轮进行接龙的人不能与上一轮相同，但可以与上上轮或更往前的轮相同。
• 接龙的人选择一个长度在 [2,k] 的 Sₚ 的连续子序列 A 作为这一轮的接龙序列，其中 k 是给定的常数。若这是游戏的第一轮，那么 A 需要以元素 1 开头，否则 A 需要以上一轮的接龙序列的最后一个元素开头。

小 J 给了 n 个参与游戏的人 q 个任务，第 j 个任务需要这 n 个人进行一次游戏，在这次游戏里进行恰好 rⱼ 轮接龙，且最后一轮的接龙序列的最后一个元素恰好为 cⱼ。请判断这 q 个任务是否可以完成。

【输入格式】 本题有多组测试数据。输入的第一行包含一个正整数 T，表示数据组数。每组数据：第一行三个整数 n, k, q；接下来 n 行，第 i 行包含 (lᵢ+1) 个整数 lᵢ, Sᵢ,₁, …, Sᵢ,ₗᵢ；接下来 q 行，第 j 行两个整数 rⱼ, cⱼ。

【输出格式】 对于每个任务，输出一行包含一个整数，若任务可以完成输出 1，否则输出 0。

【样例】

输入:13 3 75 1 2 3 4 13 1 2 53 5 1 61 21 42 43 46 61 17 7输出:1010100

【数据范围】 对于所有测试数据，保证：1 ≤ T ≤ 5；1 ≤ n ≤ 10⁵，2 ≤ k ≤ 2×10⁵，1 ≤ q ≤ 10⁵；1 ≤ lᵢ ≤ 2×10⁵，1 ≤ Sᵢ,ⱼ ≤ 2×10⁵；1 ≤ rⱼ ≤ 10²，1 ≤ cⱼ ≤ 2×10⁵；单组测试数据内所有 lᵢ 的和 ∑l ≤ 2×10⁵。

第二部分：题目解析

T1 扑克牌（poker）｜集合去重

• 考点：去重 / 集合（set）/ 模拟
• 难度：入门，送分题

思路：已有 n 张牌（可能重复），问至少再借几张才能凑齐 52 张完整扑克牌（4 花色 × 13 点数）。用 set<string> 对输入牌去重，统计不同牌的数量 cnt，答案 = 52 − cnt。

易错点：① 重复的牌只算一张；② 点数 10 记作 T，按字符串处理最稳。

#include<bits/stdc++.h>usingnamespace std;intmain(){int n;    cin >> n;    set<string> st;for (int i = 0; i < n; i++) {        string s;        cin >> s;        st.insert(s);    }    cout << 52 - (int)st.size() << '\n';   // 不同牌的数量return0;}

T2 地图探险（explore）｜方向模拟

• 考点：模拟 / 方向数组 / 判重
• 难度：普及−，送分模拟题

思路：机器人按朝向每步前进，遇障碍或越界则右转（不移动），问 k 步内经过的不同格子数（含起点）。方向数组 d=0 东、1 南、2 西、3 北，即 (0,1)、(1,0)、(0,−1)、(−1,0)；右转 d=(d+1)%4。用二维 bool 数组记录访问，访问新格时计数。

易错点：① 每步至多右转一次（不移动），不要循环转向；② 起点也算经过；③ 多组数据要重置访问数组。

#include<bits/stdc++.h>usingnamespace std;constint MAXN = 1005;char mp[MAXN][MAXN];bool vis[MAXN][MAXN];int dx[4] = {0, 1, 0, -1};   // 东、南、西、北int dy[4] = {1, 0, -1, 0};intmain(){    ios::sync_with_stdio(false);    cin.tie(nullptr);int T; cin >> T;while (T--) {int n, m, k;        cin >> n >> m >> k;int x, y, d;        cin >> x >> y >> d;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++) { cin >> mp[i][j]; vis[i][j] = false; }        vis[x][y] = true;int cnt = 1;for (int step = 0; step < k; step++) {int nx = x + dx[d], ny = y + dy[d];if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && mp[nx][ny] == '.') {                x = nx; y = ny;if (!vis[x][y]) { vis[x][y] = true; cnt++; }            } else {                d = (d + 1) % 4;   // 右转一次，不移动            }        }        cout << cnt << '\n';    }return0;}

T3 小木棍（stick）｜贪心构造

• 考点：贪心 / 可行性构造
• 难度：普及，2024 年的区分题

思路：用恰好 n 根火柴拼出无前导 0 的最小正整数（各数字所需火柴数：0,6,9→6；1→2；2,3,5→5；4→4；7→3；8→7）。

关键贪心：位数越少数越小 → 最少位数 = ⌈n/7⌉（每位数最多用 7 根，如 8）。逐位构造：从高位到低位，每次选"当前可行的最小数字"——首位用 1..9、其余位用 0..9，需保证剩余木棍数能恰好填满剩余位数（每位 2~7 根）。n=1 无解输出 −1。

易错点：① 必须恰好用完 n 根（不是不超过）；② 首位不能为 0；③ "位数最少"优先于"首位最小"。

#include<bits/stdc++.h>usingnamespace std;int cost[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};   // 0..9 各自所需木棍数intmain(){    ios::sync_with_stdio(false);    cin.tie(nullptr);int T; cin >> T;while (T--) {int n; cin >> n;if (n == 1) { cout << -1 << '\n'; continue; }int digits = (n + 6) / 7;      // 最少位数：每位最多用 7 根（数字 8）        string ans;int rem = n;for (int pos = 0; pos < digits; pos++) {int left = digits - pos - 1;   // 剩余位数for (int dig = (pos == 0 ? 1 : 0); dig <= 9; dig++) {int c = cost[dig];int rest = rem - c;if (pos == digits - 1) {if (rest == 0) { ans += char('0' + dig); rem = 0; break; }                } elseif (rest >= 2 * left && rest <= 7 * left) {                    ans += char('0' + dig); rem = rest; break;                }            }        }        cout << ans << '\n';    }return0;}

T4 接龙（chain）｜轮次 DP + 排除计数

• 考点：动态规划 / 计数排除 / 区间查询优化
• 难度：提高−，六年 T4 中最考验实现功底的一道

思路：

设 g_r[x] = 第 r 轮能以元素 x 结尾的玩家数（同一玩家多种方案只计 1）。

• 对第 r 轮、玩家 p：位置 i 能作为"上一轮末元素"当且仅当 g_{r-1}[Sᵢ] − [p 上轮能以 Sᵢ 结尾] > 0（排除 p 自己接龙自己，即相邻两轮不能同一人）。
• 玩家 p 能以位置 j 的元素结尾 ⟺ 存在 i ∈ [j−k+1, j−1] 使上述条件成立 → 用前缀和/滑动窗口 O(1) 判断。
• 每轮扫一遍所有玩家的序列（总量 ∑l ≤ 2×10⁵），r ≤ 100 → 总 O(r·∑l)。

易错点：① 相邻轮次不能同一玩家 → 计数时要减去玩家自己上轮的贡献；② 子序列长度 ∈[2,k]，起点 i 最远到 j−1；③ 第一轮任意玩家均可，且必须从元素 1 开头。

#include<bits/stdc++.h>usingnamespace std;constint MAXV = 200005;intmain(){    ios::sync_with_stdio(false);    cin.tie(nullptr);int T; cin >> T;while (T--) {int n, k, q;        cin >> n >> k >> q;        vector<vector<int>> S(n + 1);int maxR = 0;for (int i = 1; i <= n; i++) {int l; cin >> l;            S[i].resize(l);for (int j = 0; j < l; j++) cin >> S[i][j];        }        vector<pair<int,int>> queries(q);for (int i = 0; i < q; i++) {            cin >> queries[i].first >> queries[i].second;            maxR = max(maxR, queries[i].first);        }// g[x]: 上一轮能以元素 x 结尾的玩家数vector<int> g(MAXV, 0);        vector<vector<int>> prevSet(n + 1), curSet(n + 1);// 第 1 轮：任意玩家，子序列以 1 开头，长度 ∈ [2, k]for (int p = 1; p <= n; p++) {int len = (int)S[p].size();for (int i = 0; i < len; i++) {if (S[p][i] != 1) continue;for (int j = i + 1; j < len && j - i + 1 <= k; j++)                    curSet[p].push_back(S[p][j]);            }sort(curSet[p].begin(), curSet[p].end());            curSet[p].erase(unique(curSet[p].begin(), curSet[p].end()), curSet[p].end());for (int x : curSet[p]) g[x]++;        }        prevSet.swap(curSet);// 逐轮转移for (int r = 2; r <= maxR; r++) {vector<int> ng(MAXV, 0);for (int p = 1; p <= n; p++) {auto canPrev = [&](int x) {auto &v = prevSet[p];returnbinary_search(v.begin(), v.end(), x);                };const vector<int> &seq = S[p];int len = (int)seq.size();vector<int> pref(len + 1, 0);for (int i = 0; i < len; i++) {int avail = g[seq[i]] - (canPrev(seq[i]) ? 1 : 0);                    pref[i + 1] = pref[i] + (avail > 0 ? 1 : 0);                }                vector<int> &cur = curSet[p];                cur.clear();for (int j = 0; j < len; j++) {int lo = max(0, j - k + 1), hi = j - 1;if (lo <= hi && pref[hi + 1] - pref[lo] > 0)                        cur.push_back(seq[j]);                }sort(cur.begin(), cur.end());                cur.erase(unique(cur.begin(), cur.end()), cur.end());for (int x : cur) ng[x]++;            }            g.swap(ng);            prevSet.swap(curSet);        }for (auto &qr : queries)            cout << (g[qr.second] > 0 ? 1 : 0) << '\n';    }return0;}

四题考点总结

💡 年份点评：2024 年 T1/T2 送分，T3 贪心构造（中等），T4 接龙 DP 是绝对的区分题。知识结构是"集合去重 + 方向模拟 + 贪心构造 + 轮次 DP 与排除计数"。"恰好用完"的可行性判断、滑动窗口把区间条件化成前缀和、以及"排除同一玩家"的计数技巧，是今年最重要的三个方法。

本文真题基于 2024 CSP-J 第二轮认证官方试卷整理，答案与解析供学习参考，最终以 CCF 官方发布为准。祝各位同学复赛顺利！