前几天刷题时碰到一道很有意思的构造题题面只有一句话用不超过 nn≤100根火柴摆出一个尽量大的、且能被 mm≤3000整除的正整数即可。日期标着 2025-1-6应该是某次训练或每日一题。猛一看像小学奥数的火柴棒游戏真上手写代码才发现它把资源约束、大整数比较、模数状态压缩全揉在了一起。我一开始想贪心莽一版结果挂得很惨后来老老实实转动态规划才把各种边界坑填平。这篇文章就把完整思路、两套代码和踩坑记录整理出来适合正在准备算法竞赛、刷 DP 专题或者想练“带余数的背包变体”的朋友参考。1. 把题面拆干净三个约束分别对应什么套路这种题最忌讳拿到手就写代码。先把三个关键词——火柴、整除、正整数——在草稿纸上翻译成程序模型后面才不容易跑偏。1.1 火柴棒与数字的固定消耗表七个段码显示风格下0 到 9 各需要几根火柴是一个必须背熟的基础映射。我直接列出正确版本数字0123456789火柴数6255456376对应的 cost 数组就是{6,2,5,5,4,5,6,3,7,6}。记忆诀窍不复杂1 最省只要 2 根7 需要 3 根4 需要 4 根2、3、5 都是 5 根0、6、9 都是 6 根只有 8 是 7 根。我一开始把 2 记成 4 根样例直接多算一位这种低级错误很浪费调试时间。为什么这个表很重要因为题目里的“正整数”最终要转成一个数字串而每一位的“成本”就是这张表。我们要在总成本不超过 n 的前提下把数字串拼到最大。1.2 “不超过 n 根”不是“恰好 n 根”很多人看到这类题第一反应是“恰好用完 n 根火柴”。但题面写的是“不超过”这俩有本质区别。原因在于并不是任何剩余火柴数都能凑成一个数字。最小成本的数字是 1需要 2 根如果剩余 1 根就没有办法继续在末尾添加任何数字。举个例子n3 时3 根正好可以摆一个 73 根答案 7n7 时可以摆 87 根但也能摆 7112327 根711 显然更大n8 时10 需要 268 根答案 10而如果 n9可以摆 11118 根加 1 根剩余也可以摆 18279 根1111 比 18 大所以答案是 1111并不是恰好用满 9 根。这说明代码里不能只查“恰好用 n 根、余数 0”的状态必须扫描所有 i≤n 的“余数 0”状态再取最大。这个坑在后面所有写法里都要注意。1.3 “尽量大”的排序规则先位数再字典序两个没有前导零的正整数比较大小规则很简单谁位数多谁大位数相同从高到低逐位比较。所以“尽量大”可以拆成两步先最大化数字的位数再在同一长度下让字典序最大。在动态规划里这会体现在字符串比较函数上。不能直接用 C 里a b去比因为100 99是真的但整数 100 大于 99。正确做法是先比较长度长度相同再比较字典序。这个细节也是很多新手的重灾区。1.4 “能被 m 整除”要用取模状态压缩数字可能很长用整型根本存不下必须把“当前前缀模 m 的结果”带在状态里。每添加一位数字 d新的余数就是(nextRem) (currentRem * 10 d) % m这个式子非常关键。它保证不管数字串有多长我们只关心 m 个余数状态。m≤3000n≤100状态规模才 30 万上下动态规划完全可以承受。2. 为什么第一反应是动态规划而不是贪心2.1 贪心的诱惑与反例如果只看“火柴消耗”和“数字大小”很容易产生贪心想法先优先用 87 根位数多或者从高位开始每次挑最大的可行数字。但这种局部最优对整除约束完全不敏感。我试过的最典型反例是 n7、m3。最大单个数字 8 用 7 根余数 8 mod 3 2不合法但 711 也用 7 根三个数字加起来 7119 能被 3 整除合法而且 711 8。如果第一位贪心选 8就已经死了。所以题目的三个约束互相耦合必须用状态搜索。2.2 状态定义根数和余数我采用的动态规划状态是dp[i][r] 恰好使用 i 根火柴且当前数字串模 m 等于 r 的“最大合法数字串”初始状态只有dp[0][0] 表示还没开始摆数字空串模任何数都是 0成本 0。注意空串不是答案只是转移起点。转移时枚举下一数字 d成本cost[d]新余数(r*10d)%m新成本 icost[d]如果不超过 n就可以拼出候选串。这里有个很重要的“最优子结构”性质对于同一个状态(i, r)我们只保留最大的那个数字串是安全的。因为后续无论拼接什么后缀前缀越大拼接结果一定越大。前缀位数多拼上同样后缀位数还是多前缀位数相同但字典序大拼上同样后缀字典序仍然大。所以没必要保存多个候选。2.3 状态转移和复杂度分析按 i 从小到大扫描每个状态枚举 0 到 9 十个数字。状态总数是(n1)*m ≈ 101*3000 ≈ 30 万转移次数约 300 万。每次转移涉及字符串复制和比较但字符串长度上限大约 50因为最少 2 根一位n100 最多 50 位在 C 里绰绰有余用 Python 也基本能过。需要注意转移方向永远是i - icost[d]而cost[d] 2所以状态图没有环按 i 递增顺序扫描每个状态被处理时它的值已经是被所有更小 i 更新后的最终值。这可以类比“完全背包”正序更新的感觉但因为有“成本递增”保证不会出现环。3. 完整实现字符串 DP 与回溯版本3.1 最直观的字符串 DP 代码C先给一版最容易理解的实现。代码里我用better函数实现“先长度后字典序”的比较避免踩string默认比较的坑。#include bits/stdc.h using namespace std; const int costDigit[10] {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}; bool better(const string a, const string b) { if (a.size() ! b.size()) return a.size() b.size(); return a b; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorvectorstring dp(n 1, vectorstring(m)); dp[0][0] ; // 空串是转移起点 for (int i 0; i n; i) { for (int r 0; r m; r) { // 空串非可行状态只有 dp[0][0] 是特例 if (dp[i][r].empty() !(i 0 r 0)) continue; for (int d 0; d 9; d) { // 首位不能是 0 if (dp[i][r].empty() d 0) continue; int ni i costDigit[d]; if (ni n) continue; int nr (r * 10 d) % m; string cand dp[i][r] char(0 d); if (better(cand, dp[ni][nr])) { dp[ni][nr] cand; } } } } string ans; for (int i 0; i n; i) { if (dp[i][0].empty()) continue; if (better(dp[i][0], ans)) ans dp[i][0]; } if (ans.empty()) cout impossible\n; else cout ans \n; return 0; }关键点有三个一是dp[0][0]虽然是空串但它是合法状态不能因为empty()就被跳过二是首位不能为零这是“正整数”的硬要求三是最后答案从所有 i 的余数 0 状态里挑而不是只看 n。这个代码我用样例自测过逻辑是稳的。3.2 Python 版本如果习惯 Python写法几乎一样。字符串不可变会让复制成本略高但这个数据规模下没压力。n, m map(int, input().split()) cost [6, 2, 5, 5, 4, 5, 6, 3, 7, 6] def better(a: str, b: str) - bool: if len(a) ! len(b): return len(a) len(b) return a b dp [[ for _ in range(m)] for _ in range(n 1)] dp[0][0] # 表示可行空串 for i in range(n 1): for r in range(m): if i 0 and r 0: cur else: cur dp[i][r] if not cur: continue for d in range(10): if not cur and d 0: continue ni i cost[d] if ni n: continue nr (r * 10 d) % m cand cur str(d) if better(cand, dp[ni][nr]): dp[ni][nr] cand ans for i in range(n 1): if dp[i][0] and better(dp[i][0], ans): ans dp[i][0] print(ans if ans else impossible)这个版本把“空串可行”和“其他空串不可行”分开判断。新手最容易在这儿写成if not dp[i][r]然后直接跳过导致dp[0][0]永远无法转移整个 DP 跑不出任何答案。3.3 想说更省时间/空间前驱数组回溯字符串 DP 胜在直观缺点是要为每个状态都保存一份完整字符串比较时反复复制。如果题目加大到 n 几百几千或者比赛环境里时限很紧可以改成记录前驱信息最后再回溯出完整数字串。核心思路是不直接存字符串而是维护len[i][r]表示当前最优数字串的长度同时记录这一位数字digit[i][r]和它来自哪个状态(fromStick[i][r], fromRem[i][r])。更新条件仍是先比较长度长度相同需要比较候选串和原串的字典序。但这里比较字典序没法只看长度通常还是需要临时生成候选串或者额外存一份字符串。所以它主要是省了“所有状态各自保留字符串”的长期内存复制操作并没有完全消失。下面给一个精简框架vectorvectorint lenDp(n 1, vectorint(m, 0)); vectorvectorint preStick(n 1, vectorint(m, -1)); vectorvectorint preDigit(n 1, vectorint(m, -1)); vectorvectorint preRem(n 1, vectorint(m, -1)); // 初始化时 lenDp[0][0] 0其他为 -1 表示不可达回溯时从某个满足r0 len0的状态出发不断用preDigit收集数字然后逆序输出。这种写法能帮你理解“状态里没必要真的存大数”的思想很多数位 DP 的高级题都会用到。3.4 记忆化搜索也是一种选择除了从前往后递推还可以写记忆化搜索。不过这道题的转移方向是“从小成本到大成本”递归版需要额外维护一个dfs(i, r)表示“用不超过 i 根火柴、当前余数为 r 时能得到的最大后缀”设计起来不如递推直观。我实际刷题时更推荐递推因为更容易处理“不超过 n”这种最后扫描答案的需求。4. 从“能过”到“优雅”先最大长度再逐位贪心如果不想每次比较都带着整个字符串还有一个更贴合“先比长度再比字典序”的解法两步走。4.1 第一步算出最大位数先用 DP 计算“用不超过 n 根火柴能组成的合法且余数为 0 的数字串的最大位数”。因为最小成本是 2所以最大位数理论不超过n/2 50。可以定义minCost[len][r]表示“摆成一个长度为 len、余数为 r 的数字串至少要消耗多少根火柴”。初始时第一位只能放 1 到 9后面各位可以放 0 到 9。转移时枚举新增数字minCost[len1][(r*10d)%m] min( minCost[len][r] cost[d], 当前值 )只要minCost[len][0] n长度 len 就是可达的。从大到小找到最大的 len就是答案的位数 Lmax。这个思路为什么成立因为两个正整数先比长度。只要能把位数做到更大任何“少一位但首位更大”的数都不可能是最优答案。这一点是题目“尽量大”的排序规则决定的。4.2 第二步在最大位数下逐位构造字典序最大有了 Lmax再逐位确定答案。假设当前已经构造出前缀已经用了 used 根火柴当前余数为 rem还需要填 rest Lmax - 已填位数 位数字。我们需要判断是否存在一种填法让剩余位数正好填完并且最终余数为 0。这可以提前预处理一个can[needLen][needRem]数组表示“用不超过某剩余成本、填 needLen 位数字能否让余数从 0 走到 needRem”。更准确地说在每一步剩余可用的根数不同所以要做成三维或者直接暴力判断。因为 Lmax 最多 50m 最多 3000枚举每个候选数字时跑一次小 DP 也完全可以接受。实现上我从高位到低位枚举数字 d 从 9 到 0检查“当前已用根数 cost[d] n”且“剩余长度的后缀能让最终余数归零”。能放下就选择 d进入下一位。这个套路我在数位 DP 题里经常用它把“全局最优化”拆成“可行性判断 贪心选位”代码逻辑比字符串 DP 复杂一点但内存占用小构造答案时也更有“手工拼数字”的实感。4.3 两种解法对比维度字符串 DP两步法最大长度 贪心思路复杂度低状态直接存答案中需要预处理可行性代码量较短稍长内存每个状态一个 string只需长度/成本/前驱对“不超过 n”的处理最后扫描所有 i在转换时判断成本适用场景n、m 都不大的常规题更大型的数位构造题我实际做题时第一遍提交用的字符串 DP因为最容易写对。等确认思路无误后再用两步法重新实现主要是为了练手感也方便以后应对更大的 n。5. 常见问题与避坑清单这类题代码不长但隐藏坑非常多。我把刷题过程中真实踩过的、以及帮别人 review 时见过的问题整理成清单按频率排序。5.1 首位为零题目要的是正整数0 不是正整数所以整个数字的第一位不能是 0。代码里必须在从空串转移时特判d 0跳过。但注意0 出现在中间或末尾完全合法比如 10、101、100 都可以。很多人会在转移时一股脑禁止 0结果漏掉了 10 这种合法答案。5.2 无解时输出什么如果根本凑不出任何合法数字需要输出一个明确的无解标记。常见做法是输出-1或impossible。我见过有人把dp初始化为空最后输出空行这在评测系统里基本就是 WA。别忘了一开始判断 n2因为根数少于 2 时连 1 都摆不出来。5.3 cost 表记错数字 2 究竟是 5 根还是 4 根数字 6 究竟是 6 根还是 5 根这是最容易出错的地方。建议把表抄在代码注释里或者用数组初始化时从 0 到 9 逐个核对。我自己的做法是记两条辅助线1 最少 2 根8 最多 7 根其余都是 3 到 6 根。5.4 取模公式写错正确公式是(r*10 d) % m不是(r d) % m也不是(r*10 % m d) % m漏了括号。因为新数字串相当于原来的数字串整体左移一位再加 d所以要乘 10。m 最大 3000过程中r*10d最多 30009int 完全够用不需要 long long。5.5 字符串比较函数没写对刚才已经强调过string的默认比较是字典序不是数值序。100 99成立但 100 99。所以比较函数一定要先size()再lexicographical。这一步错了DP 里所有“保留最大”的判断都会失真最终答案大概率不是真的最大。5.6 只查恰好 n 根由于“不超过 n”答案可能出现在任意 i≤n 的状态。比如 n9 的答案是 1111用 8 根如果只查 dp[9][0]会因为 9 根状态里没有合法答案而输出 impossible。这个坑我第一次写就踩了后来把答案扫描改成从 0 到 n 才通过。5.7 DP 顺序和环的问题每次加一位数字至少消耗 2 根火柴所以状态只会从 i 流向更大的 i不可能出现i - i的环。按 i 从小到大扫描是安全的。同时它也保证了同一个状态不会在同一轮里被无限次更新因为成本严格增加。6. 用小样例验证 DP 逻辑光说理论容易晕我用两个小样例手动跑一遍帮助理解。6.1 n6m3数字 0 到 9 里单根数不超过 6 的数字有 12根、73根、44根、2/3/55根、0/6/96根。但首位不能是 0所以单个合法候选只有 1、7、4、2、3、5、6、9。其中能被 3 整除的有 6 和 9但 6 和 9 都是一位数。用 6 根还可以摆 111111 能被 3 整除而且是三位数明显大于一位的 6 或 9所以答案 111。DP 会先由 dp[2][1]数字 1扩展到 dp[4][2]数字 11再扩展到 dp[6][0]数字 111。6.2 n7m37 根最多可以摆三位数比如 711 用 2327 根711 mod 3 0710 用 23611 根超了8 用 7 根但余 2 不合法。所以答案 711。如果贪心先选 8这一位就错了DP 会保留 dp[7][0] 下的 711。这两组样例也说明题目的“火柴”包装并不难难的是把“余数”和“字符串比较”两条线同时处理好。一些调试心得最后聊点个人经验。我写这道题的调试顺序是先跑最朴素的暴力搜索枚举所有可用火柴组合拿到 n 很小、m 很小时的正确答案再用 DP 实现把两组答案对拍。暴力代码虽然跑不了大数据但能用来验证状态转移和比较函数尤其适合抓“首位 0”和“恰好 n 根”这种边界问题。另外DP 里字符串复制虽然在这个数据范围下没问题但如果你打算把代码提交到更严格的平台建议将vectorvectorstring改成前驱回溯版本或者用数组存长度和最后一位。等位贪心法码量更大但思路更接近数位 DP遇到 n 扩大到几千的时候会从容很多。我个人实际写完这道题的体会是它本质上是“带余数约束的资源背包”只是用火柴数字做了个可爱的包装。以后做类似“用几种元素拼成最大值”“满足整除条件的最大数”的题第一反应都应该是把整除条件转化为余数状态把比较大小转化为先长度后字典序然后放心 DP。至于 2025-1-6 这个日期倒不用纠结题好就行。