国庆真题精讲特辑 · DAY 4 / 5 · CSP-J
真题精讲③｜CSP-J 2024：T3 小木棍 + T4 接龙
今天回到入门组（CSP-J）2024 年，讲 T3、T4——一个考"构造 + 贪心"，一个考"DP + 前缀和"。这两题也是近年 J 组的难度担当：T3 看似暴力能骗分，T4 则需要把状态设计清楚。
题目一：T3「小木棍」
这道题特别能拉开差距：思路朴素的孩子会去"枚举 + 拼数"，聪明的孩子一眼看出是构造最小数字。
一、真题重现（通俗版）
用火柴棒拼数字：数字 0~9 各有固定的"耗棒数"（比如拼 1 用 2 根、拼 8 用 7 根）。现在给你 n 根火柴，必须恰好用完，拼出一个不含前导 0 的最小正整数。问这个数是什么？
二、考点定位
贪心 + 构造 + 整除/取模。核心目标很清晰：位数越多数字越小，所以在"位数最多"的前提下，再把高位尽量放小数字。
三、思路拆解（分步点拨）
1. 位数最多：用最"省棒"的数字（数字 1 只要 2 根）尽量多拼几位，即 n / 2 位起步。
2. 调整余数：如果 n 是奇数根，多出来的 1 根要"匀"到某一位上（把某个 1 换成 7，7 用 3 根 = 2+1），保证恰好用完且位数不变。
3. 最小优先：在位数固定的情况下，从左到右把能放的最小合法数字放上去（注意首位不能是 0）。
👉 给孩子的小任务：先想"怎么让位数最多"，再想"余数怎么分配才不破坏最小性"。
四、易错预警
⚠️ 坑 1：忘了"必须恰好用完 n 根"，多拼或少拼都错。
⚠️ 坑 2：构造出前导 0（如 01…），题目要求正整数无前导 0。
⚠️ 坑 3：贪心顺序错——先放小数字但忽略了"位数优先于数值大小"。
题目二：T4「接龙」
T4 是 J 组里少见的DP/递推题。难点不在算法多难，而在状态怎么定义、怎么快速回答多次询问。
一、真题重现（通俗版）
有 n 个人，每人手里有一个数字序列。玩接龙：第 1 轮必须以数字 1 开头；之后每轮，某人拿出自己序列里一段连续的子序列（长度在 2~k 之间），以上一轮的结尾数字接上。可以重复接，但不能连续两轮都是同一个人。给定 q 次询问：能否进行 r 轮、并且最后以数字 c 结尾？
二、考点定位
动态规划 / 递推 + 前缀和优化。定义"第 r 轮能否以某个数字 c 开头/结尾"，并维护"来自不同人"的限制，用前缀和把查询降到 O(1)。
三、思路拆解（分步点拨）
1. 把每个人的序列拍平成一维，记录"每张牌属于哪个人"。
2. 定义 dp[r][j]：第 r 轮以一维序列第 j 张牌结尾是否可行；转移时要求"前 k−1 张里存在不是同一人的可转移牌"。
3. 用"记录两个来自不同人的候选" + 前缀和，把每轮转移优化到 O(n)，避免超时。
👉 给孩子的小任务：先写出 O(r·n·k) 的暴力 DP，再想"怎么用前缀和砍掉 k 这维"。
四、易错预警
⚠️ 坑 1：忘了"不能连续两轮同一人"的限制，状态转移写错。
⚠️ 坑 2："子序列长度 2~k"边界没处理，k=1 或 k 很大时越界。
⚠️ 坑 3：暴力 DP 不优化，大数据点 T 轮 × n 直接超时。
💬 互动：T3 的构造思路和 T4 的 DP，孩子哪道更有感觉？留言说说，教练会在群里挑典型问题统一答疑。
▍免责声明
本文题解为教练团队基于公开真题的讲解，仅供参考学习，不构成任何培训承诺；真题最终以 CCF 官方公布为准。文中提到的社群由本号运营，本号仅作信息分享，不对其内容与服务质量作担保。
