看到题单上写着“问题 N等差数”的时候我第一反应是这道题白给。等差数嘛就是一个数的每一位构成等差数列比如 123、2468、97531 都是。等到真上手写题才发现这个“朴素”题里藏的坎比想象中多而且最优解不是大多数人猜的数位DP而是先把集合完整生成出来。这篇文章把等差数这类题的完整思路拆开讲一遍重点放在定义边界、数量级分析、生成算法、高频问法落地以及我实际踩过的几个坑。无论你是备战比赛还是刷题想提效率看完基本能直接抄代码。先说结论等差数虽然在名字上听着一股数学味实际考的是“看清集合大小”的观察力。一旦你意识到在给定数值范围内等差数只有两三千个整道题的难度就断崖式下降剩下的全是常规操作。1. 先把题读完整等差数定义的几个岔路口1.1 主流定义与两个变体主流定义为一个正整数 x 的十进制表示从高位到低位排成序列 a1, a2, ..., ak如果存在常数 d使得对任意 i ≥ 2 都有 ai a_{i-1} d那么 x 就是等差数。等价的说法是这个数的所有数位落在同一条等差数列上。实际题目里可能存在变体比较常见的有两种。第一种是反向读即从低位到高位看也构成等差数列。但这个变体其实是等价的因为一个序列是等差数列把它反转后仍然是等差数列只是公差符号反了而已。所以你写程序时从个位开始判断效果和从高位开始完全一样。第二种是“公差非零”版本这种题会明确排除 11、222、9999 这类每一位都相同的数。如果题目没提默认公差可以为 0。还有个更偏门的变体定义“数本身是某条等差数列的某一项”这个和数位等差完全是两码事真遇到这种题建议直接放弃换思路。定义不同答案集合完全不同所以拿到题先别急着写花十秒看样例。样例里有没有 11、111 这种数字是最快的判断信号。1.2 一位数和两位数都是等差数一位数没什么好说的一个元素自成等差数列。两位数 ab给定任意 b − a 作为公差两个数字天然落在一条等差数列上所以任意两位数也都是等差数。这意味着判定等差数时位数小于等于 2 的情况可以直接返回 true。很多暴力判断程序的 bug 就出在这里有的人写循环判断相邻差二位数的逻辑没问题但遇到一位数时循环边界容易出问题。提前特判能省掉一堆麻烦。如果题目额外规定公差非零那么 10、22 这种两位数的判断就要另说这种情况下只有两个数字不相等才算等差。1.3 公差为 0 是分水岭有限集与无限集如果允许公差为 0那么 1、11、111、1111……全都是等差数位数可以无限增加集合是无限集。如果不允许公差为 0任意一条数位链从 0 到 9 最多 10 步就会越界集合是有限集。竞赛题为了不让“第 N 个等差数”这种问题失去意义通常都会限定数值范围比如保证答案在 64 位整数内。本质上这就是给最大位数设了一个上限。所以我们的处理策略很明确把题目隐含的位数上限当作 maxBits 参数生成时用它来截断所有无限延伸的链。这个细节在写生成代码时极其关键后面章节会专门讲。2. 反直觉的数量分析等差数在范围内少得可怜2.1 一条数字链为什么最多走 10 步考虑一条等差数位链第 k 位是 first k * diff其中 first 是首位diff 是公差。每一位都必须落在 0 到 9 这十个数字上。如果公差大于 0链会一路朝 9 靠近如果公差小于 0链会一路朝 0 靠近。举例来说明。首项 1、公差 2走出来的数字是 1、3、5、7、95 步到顶首项 9、公差 -1走出来的是 9、8、7、6、5、4、3、2、1、0正好 10 个数。任何一条链从一个首项出发经过一个方向上的数位走动最多经过 10 个不同的数字就会被 0 和 9 的边界挡住。这就是“链长最多 10”这个结论的直观来源。如果公差为 0链不会越界但它可以无限延伸重复数字。此时要借助题目给定的最大位数 maxBits 来截断。所以一条链的长度是 min(每个方向的自然界数, maxBits)。2.2 9 × 19 × maxBits 的推导首项只能是 1 到 9因为一个数的最高位不能是 00 本身最后单独处理共 9 种可能。公差是 -9 到 9共 19 种可能。两者组合最多有 9 × 19 171 条链。每条链最多提供 maxBits 个截断前缀所以数量上界为 9 × 19 × maxBits。位数上限暴力枚举量级等差数数量上界9 位10^99×19×9 153912 位10^129×19×12 205218 位10^189×19×18 3078上面表格里“暴力枚举量级”指的是从 0 扫到上限逐个判断“等差数数量上界”是我们实际需要存储的数据量。哪怕范围拉到 10^18等差数也就两三千个塞进一个 vector 完全是袖珍数组级别。这个数量级决定了后面所有操作都不会超过 O(M log M) 的预计算成本其中 M ≤ 3078。2.3 打表本身就是正解数位DP反而绕远很多人看到“数字位满足某性质 计数”就会条件反射式地想到数位DP等差数在形式上确实符合这种归类。但数位DP适合的是合法集合很大、无法枚举的场景比如统计数字和或二进制中 1 的个数。等差数的合法集合在题目的数值范围内只有两三千个硬套数位DP等于拿大炮打蚊子。数位DP要处理等差数状态至少要记录当前位数、前一个数字、公差还要额外处理前导零。状态设计复杂转移容易漏调试成本高。而“生成-排序-二分”三件套的代码量能控制在 50 行以内不需要任何记忆化多组查询也照样跑得飞快。所以这种题的核心思维不是 DP而是先判断集合大小再决定策略。2.4 适合这种思路的题目形态只要题目问的是下面任意一种都可以直接走生成全量的路子第 k 个等差数是什么区间 [L, R] 内有多少个等差数所有等差数中第 k 大是否存在某个位数的等差数求最小或最大等差数的和、最大值、最小值等聚合查询唯一需要调整的是两个开关生成时要不要包含公差 0 的前缀以及是否包含数字 0。这两个开关由题目定义决定对应修改代码里的两个位置即可。3. 全量生成的两种写法与大小比较细节3.1 写法A首项公差直接构造这是我最推荐的写法逻辑直白两层循环搞定#include bits/stdc.h using namespace std; vectorlong long generateAll(int maxBits) { setlong long st; for (int first 1; first 9; first) { for (int diff -9; diff 9; diff) { long long cur 0; int digit first; int len 0; while (digit 0 digit 9 len maxBits) { cur cur * 10 digit; st.insert(cur); digit diff; len; } } } st.insert(0); // 是否加入视题意 return vectorlong long(st.begin(), st.end()); }这里最需要注意的是 diff 0 的死循环问题。当 diff 0 时digit 永远不会越界唯一能停下来的条件就是 while 里的 len maxBits。我第一次写的时候没加这个条件程序直接卡死后来才发现是公差 0 的链在无限生成 11、111、1111……。如果担心 while 条件可读性差也可以单独处理 diff 0if (diff 0) { long long cur 0; for (int len2 1; len2 maxBits; len2) { cur cur * 10 first; st.insert(cur); } continue; }3.2 写法BDFS逐位延长如果习惯递归可以写成从第一个数字开始逐位追加下一位数字。初始阶段由于还没有确定公差需要先把一位数和两位数铺开后续的状态转移才有的放矢void dfs(long long cur, int last, int diff, int len, int maxBits, vectorlong long out) { if (len maxBits) return; if (cur 0) out.push_back(cur); int nxt last diff; if (nxt 0 || nxt 9) return; dfs(cur * 10 nxt, nxt, diff, len 1, maxBits, out); } void generateByDFS(int maxBits, vectorlong long out) { for (int first 1; first 9; first) out.push_back(first); for (int first 1; first 9; first) { for (int diff -9; diff 9; diff) { int nxt first diff; if (nxt 0 || nxt 9) continue; dfs(first * 10 nxt, nxt, diff, 2, maxBits, out); } } }注意这种写法里一位数要单独塞进去因为一位数没有“前两位”可以参考无法自然延出一条链。递归写法的优点是结构清晰缺点是代码行数比两层循环略多。整体上我推荐写法A更短也不容易漏一位数。3.3 set 去重后的大小与排序严格来说由首项和公差确定的链之间不会产生重复元素但 diff 0 和 diff 非 0 在边界上的行为不同代码改动时容易混入重复。用 set 天然去重就不用担心这个问题。一个 set 塞两三千个 long long插入和排序的开销几乎可以忽略不计。生成完以后从 set 转到 vector数组自然有序。如果你直接用的 vector 而没有 set要记得手动 sort 一遍sort(v.begin(), v.end());后续所有查询都依赖有序性这一步不能省。3.4 0 和前导零的处理争议数字 0 算不算等差数从定义看0 的十进制表示是单独一位数字属于一位数范畴应该算。但很多题目会把范围限定在正整数里这时 0 就不该出现在答案中。稳妥做法是生成后单独插入 0查询阶段再按题意决定是否纳入计数。还有一个常见的误区构造时从 first 0 开始枚举。看起来没毛病实际上 0、01、012、0123 这些“链”会把 1、12、123 重复生成而且 012 这种数字在十进制表示里实际上就是 12但从链的角度看它是一条独立链。这样会导致 set 里混入大量重复虽然去重后数量最终是对的但代码逻辑很难读统计链长和边界时容易把自己绕晕。正确姿势是 first 固定从 1 到 9最后单独处理一下 0。4. 两个高频问法的代码落地4.1 问第 N 个排序数组直接下标访问生成好全局数组 v 后第 N 个等差数就是 v[N - 1]。如果 N 超过 v.size()按题意返回 -1 或走出范围标记long long kthArith(int k) { if (k 0 || k (int)v.size()) return -1; return v[k - 1]; }这里唯一需要注意的是 k 从 1 开始还是从 0 开始。大多数题面写“第一个等差数是 0”或者“第一个等差数是 1”都有可能。我建议在赛场上先把 v 的前 20 个元素打印出来肉眼扫一遍确认下标和序列的对应关系能避免很多低级错误。数组本身有序所以这个操作非常快。4.2 问 [L, R] 内有多少个二分边界生成数组有序后区间计数就是标准的两行二分long long countArith(long long L, long long R) { return upper_bound(v.begin(), v.end(), R) - lower_bound(v.begin(), v.end(), L); }这里有个细节要注意用 upper_bound 而不是 lower_bound(R 1)。当 R 是 long long 最大值时R 1 会直接溢出成负数二分结果全错。本地测试时大多数人用不到这么大的数这个坑只有在极限数据或对拍中才会暴露。如果你遇到的是半开区间 [L, R)那么第二个参数要写成 lower_bound(v.begin(), v.end(), R)不是 upper_bound记混了大概率翻车。4.3 常见变体的统一套路这类题目看似变化多实际都是在一个有序数组上做操作。问第 k 大的等差数访问 v[v.size() - k]问所有不超过 X 的等差数之和先二分出最后一个小于等于 X 的位置配合前缀和数组一个减法得到问数位和为偶数的等差数有多少可以生成时顺带判断也可以生成完再筛一遍存进另一个数组。这套打法最舒服的地方在于预计算一次后不管题目有多少组查询单次回答都是 O(log M)M 不到 3100所以即使有 10^5 组查询也毫无压力。比赛时通常把预计算放 main 函数开头之后循环处理每个 case。注意如果题目有多个测试文件预计算别放在每次循环里面重复跑。5. 对拍验证与复盘我踩过的三个坑5.1 对拍脚本用最简单的判断函数当裁判写完备题代码后最担心的是生成法漏掉某些等差数。最有效的验证方式是用一个最笨的判断函数从 0 开始逐个检查把每个数是否等差记下来再和生成法得到的数组对比。下面这个 Python 脚本可以直接用def is_arith(x): s list(map(int, str(x))) if len(s) 2: return True d s[1] - s[0] return all(s[i] - s[i - 1] d for i in range(2, len(s))) def brute_list(limit): return [x for x in range(limit 1) if is_arith(x)] # 假设 generate_all 返回 C 生成并导出的有序列表 fast generate_all(6) brute brute_list(999999) assert fast brute, (len(fast), len(brute)) print(ok)把 maxBits 调成 6暴力可以扫到 10^6足以验证所有边界情况。小规模对上了再调回 18。这一步建议写题时顺手做能帮你发现一堆自己都没意识到的逻辑漏洞。5.2 坑1公差为 0 的死循环我第一次写生成函数时没加 maxBits 限制diff 0 的链会一直生成 111...循环永远停不下来。这不是我一个人的问题所有公差 0 的链都会触发。解决方式前面已经说过要么在 while 条件里加 len maxBits要么对 diff 0 单独循环处理。单独处理可读性更高也避免依赖 while 里的截断条件我建议写成单独分支。5.3 坑2从 0 开头生成导致的串数另一个常见翻车点是 first 从 0 开始枚举。看起来只是多了一个首项实际上 0、01、012、0123 这些链会把 1、12、123 重复生成还可能把同一个数值由多条链覆盖打乱你对链长的判断。后来我改成 first 固定 1 到 9最后单独插入 0代码一下子就干净了。判断函数不会遇到这个问题但生成函数一定要避开前导零。5.4 坑3区间计数的长整型溢出处理 [L, R] 时很多人习惯写 lower_bound(v.begin(), v.end(), R 1)。数据小的时候一切正常一旦 R 取到 10^18 量级R 1 溢出成负数二分结果全错。正确写法就是 upper_bound。另外L 和 R 如果按 int 读入大范围题目直接爆 int所有输入变量都用 long long 是比较稳妥的习惯。个人实际操作中的一点体会拿到这类“数学名词题”先别急着写算法的王道而是花两分钟把集合大小算清楚。等差数这个例子特别典型一个看起来很数学的性质题底层其实是个生成集合的题。这个套路还能延伸到不少类似题目比如回文数、幸运数字、各位数字单调递增的数核心都是先看数量级再决定是枚举还是设计复杂状态。希望这些内容能帮你在赛场上少踩几个我踩过的坑。