今天看 CSP-J 2024 的这道题考点是动态规划。题目来源ACGO A34464 洛谷 P11230难度定位提高/省选- 通过率41.41%一、题目信息题目名称接龙所属赛事2024 年 CSP-J 组复赛官方难度提高/省选-涉及知识点动态规划、图论题目链接https://www.acgo.cn/problemset/info/34464洛谷编号P11230同一道题两个平台均可提交代码通用坑点这题失分基本都在这状态定义要写清楚最好注释在代码里遍历顺序错了会用到本层刚更新的值结果就偏了多阶段 DP 每进入新阶段之前的数组要重新初始化高难度题的暴力分很关键先写一版能过的部分分再想正解题意简述用一句话概括[CSP-J 2024] 接龙题目描述在玩惯了成语接龙之后小 J 和他的朋友们发明了一个新的接龙规则。总共有 n 个人参与这个接龙游戏第 i 个人会获得一个整数序列 S_i 作为他的词库。一次游戏分为若干轮每一轮规则如下n 个人中的某个人 p 带着他的词库 S_p 进行接龙。若这不是游戏的第一轮那么这一轮进行接龙的人不能与上一轮相同但可以与上上轮或更往前的轮相同。接龙的人选择一个长度在 [2, k] 的 S_p 的连续子序列 A 作为这一轮的接龙序列其中 k 是给定的常数。若这是游戏的第一轮那么 A 需要以元素 1 开头否则 A 需要以上一轮的接龙序列的最后一个元素开头。序列 A 是序列 S 的连续子序列当且仅当可以通过删除 S 的开头和结尾的若干元素可以不删除得到 A。为了强调合作小 J 给了 n 个参与游戏的人 q 个任务第 j 个任务需要这 n 个人进行一次游戏在这次游戏里进行恰好 r_j 轮接龙且最后一轮的接龙序列的最后一个元素恰好为 c_j。为了保证任务的可行性小 J 请来你判断这 q 个任务是否可以完成的即是否存在一个可能的游戏过程满足任务条件。前置知识先把这题需要的基础理一遍熟悉的可以直接跳到思路部分。状态 转移DP 三步定义状态 f[i] 表示什么写转移方程 f[i] ...确定初始值和遍历顺序。初学者最容易错在状态定义太模糊。点与边的建模图论题第一步是「把题目里的关系和点、边对应起来」。建完图再看是求最短路、连通性还是拓扑序。二、思路分析在 CSP-J 2024 里属于提高/省选-档考场上建议放在中场先拿暴力分做。先说结论再讲为什么。这道「接龙」属于动态规划类问题。拿不到官方题解的题我们把推导过程还原一遍重点是让你能自己想出来。第一步读清目标。题目要我们求什么是求一个数值、一个方案还是判断可行性目标不同做法差别很大。第二步看数据范围。数据范围往往直接告诉你该用什么复杂度的算法这一步比想算法更重要。第三步从小规模入手。先手算题目给的样例把中间过程写下来规律往往就在这个过程中浮现。第四步落到动态规划的标准套路。确定方向后把题目条件翻译成代码结构再处理边界。下面给出的是一份可在 ACGO 与洛谷两平台提交的参考实现建议先自己写一遍再回来对照。三、完整代码#include bits/stdc.h using namespace std; // CSP-J 2024 接龙 (ACGO A34464) // // 题意n 个人各有整数序列 S_i。游戏分 r 轮每轮由某人 p 从其序列中选一段 // 长度在 [2, k] 的连续子序列作为这一轮的接龙序列首轮必须以 1 开头 // 之后每轮必须以上一轮接龙序列的末尾元素开头相邻两轮不能是同一个人。 // 有 q 次询问 (r, c)恰好进行 r 轮后末尾元素能否恰好为 c。 // // ── 做法按轮递推 滑动窗口────────────────────── // 记 dp[r][v] 表示「第 r 轮以数值 v 结尾」时这一轮的接龙者是谁 // -1 表示第 r 轮以 v 结尾不可行 // i 表示可行且唯一接龙者是第 i 个人 // 0 表示可行且接龙者不止一人于是下一轮任意人除 i 外都能接 // 初始 dp[0][1] 0第 0 轮「以 1 结尾」是钦定的起点且无人限制。 // // 逐轮更新对每个人 i扫它的序列 S_i。维护窗口内「可作为本轮起点的 // 数值个数」cnt —— 当读到某个数 x 时 // · 若 cnt 0说明 x 可以作为本轮终点把 dp[r][x] 按上面规则用 i 更新 // · 若上一轮 dp[r-1][x] 可行且接龙者不是 i则 x 可以开始新一轮 // 于是把 cnt 重置为 k-1表示从 x 往后 k-1 个位置都在合法窗口内。 // // r ≤ 100Σl ≤ 2×10⁵故复杂度 O(r·Σl q)。 const int N 200005; const int R 105; int n, k, q; vectorint S[100005]; int dp[R][N]; int main() { int T; scanf(%d, T); while (T--) { scanf(%d %d %d, n, k, q); int maxv 2; // 数值上界仅用于调试参考 for (int i 1; i n; i) { int l; scanf(%d, l); S[i].clear(); for (int j 0; j l; j) { int x; scanf(%d, x); S[i].push_back(x); if (x maxv) maxv x; } } (void)maxv; // 清空 dp整表置 -1数值上界为 2e5用 memset 更快更稳 memset(dp, -1, sizeof(dp)); dp[0][1] 0; // 起点第 0 轮以 1 结尾 for (int r 1; r 100; r) { for (int i 1; i n; i) { int cnt 0; // 窗口内可作为本轮起点的数值个数 for (size_t j 0; j S[i].size(); j) { int x S[i][j]; if (cnt 0) { // x 可作本轮终点 if (dp[r][x] -1) dp[r][x] i; else if (dp[r][x] ! i) dp[r][x] 0; cnt--; } if (dp[r - 1][x] ! -1 dp[r - 1][x] ! i) cnt k - 1; // x 可开始新一轮窗口长度 k-1 } } } while (q--) { int r, c; scanf(%d %d, r, c); puts(dp[r][c] -1 ? 0 : 1); } } return 0; }四、代码分段拆解代码不长但每一行都有讲究分段过一遍。头文件与全局变量先把用到的头文件和全局变量放上来。全局变量在竞赛里很常用好处是函数之间共享方便代价是要小心初始化和被意外改写。#include bits/stdc.husing namespace std; const int N 200005; const int R 105; int n, k, q; vectorint S[100005]; int dp[R][N]; int main() { int T; int maxv 2; // 数值上界仅用于调试参考主体逻辑主体部分按顺序完成读入、计算、输出。main函数尽量保持线性把复杂的逻辑拆成独立函数出问题时更容易定位。状态与转移DP 部分建议在代码里写上状态含义的注释。过几天回头看没有注释的 DP 基本读不懂。五、实例模拟用题目给的样例走一遍验证我们的思路。样例 1输入1 3 3 7 5 1 2 3 4 1 3 1 2 5 3 5 1 6 1 2 1 4 2 4 3 4 6 6 1 1 7 7输出1 0 1 0 1 0 0样例 2输入见选手目录下的 chain/chain2.in 与 chain/chain2.ans。 该样例满足测试点 1 的特殊性质。输出样例 3输入见选手目录下的 chain/chain3.in 与 chain/chain3.ans。 该样例满足测试点 2 的特殊性质。输出以第一组样例为例输入是1、3 3 7、5 1 2 3 4 1、3 1 2 5、3 5 1 6、1 2、1 4、2 4、3 4、6 6、1 1、7 7正确输出是1、0、1、0、1、0、0。建议把这两行数据抄在纸上用上面的代码手动走一遍重点看循环变量怎么变化、答案在哪一步被更新。能自己推出来的东西比看懂代码印象深得多。六、踩坑总结把这题的经验固化下来。状态定义要写清楚最好注释在代码里遍历顺序错了会用到本层刚更新的值结果就偏了多阶段 DP 每进入新阶段之前的数组要重新初始化高难度题的暴力分很关键先写一版能过的部分分再想正解另外提醒一句这题在 CSP-J 2024 里是提高/省选-难度考场上如果没有把握拿满分先把暴力写法交上去拿到部分分再回头优化。CSP 是打分制空着不写才是最亏的。七、知识点拓展这题的核心是动态规划。CSP 的 DP 题很少单独考通常和别的知识点结合。判断能不能用 DP就看有没有「阶段 状态」的结构以及当前决策会不会影响后面的选择。建议的练习路径先把本题独立写一遍不看代码遇到卡壳再看提示换个平台提交ACGO 和洛谷都试试确保代码在两个平台都能过找两到三道同类型的题练手巩固这类问题的识别能力本题还涉及 图论建议一并复习八、适用人群这题适合这些阶段的同学目标是 CSP-S 高分或省选的同学想通过真题理解高难度题如何从暴力优化到正解的同学想弄明白动态规划类问题标准解法的同学有更好的写法欢迎在评论区交流一起进步。关于这个系列这是「CSP 真题逐题精讲」的第 46 篇。我会按年份从 2019 一路刷到 2025CSP-J 和 CSP-S 全覆盖。每篇都给双平台题号ACGO 洛谷 逐行代码拆解 真实样例模拟。跟着刷完这一套CSP 第一轮的选择题和基础题基本就稳了。下一篇CSP-S 2024 决斗普及- 关注我不错过后续更新。评论区告诉我你现在刷到哪一年了我看看能不能按大家的进度调整更新节奏。