企业官网建设流程全解析

1. 从一道题看数位DP的核心思想

1.1 这道题到底在问什么

先把这个题目的意思说清楚。所谓平衡数，指的是这样一个数字：存在某一个位置作为支点，使得支点左边的每一位数字乘以它到支点的距离之和，等于支点右边每一位数字乘以它到支点的距离之和。说白了就是拿数字的某一位当跷跷板的支点，左右两边的“力矩”相等。

举个例子，数字4139。我们选3这个位置当支点。左边是4和1，4距离支点2位，1距离支点1位，所以左边力矩是4×2 + 1×1 = 9。右边是9，距离支点1位，右边力矩是9×1 = 9。两边相等，所以4139是一个平衡数。

再比如数字10，选1当支点，左边没有数字，力矩为0，右边是0距离1位，力矩为0×1 = 0，两边相等，所以10也是平衡数。注意0本身也是平衡数，这个边界要特别处理。

题目一般会给定一个区间[L, R]，问这个区间内有多少个平衡数。R的范围可能到10^18甚至更大，暴力枚举肯定不行，必须用数位DP。

1.2 为什么这题是数位DP的经典入门

数位DP的核心场景就是：统计在某个区间内，满足某种“与数字每一位相关”的性质的数的个数。这题完美符合这个特征——平衡性依赖于每一位数字和它到支点的距离，是典型的逐位决策问题。

我当初学数位DP的时候，最先接触的就是这类题。它的好处在于状态设计不算太复杂，但又足够让你理解数位DP的几个关键点：支点枚举、前导零处理、力矩的表示、以及记忆化搜索的写法。把这题吃透，后面遇到更复杂的数位DP（比如统计满足某些数位和条件的数、带模数的数位统计等）都能触类旁通。

1.3 暴力为什么不可行

假设R = 10^18，暴力枚举每个数再逐位判断，时间复杂度是O(R × 位数)，大概是10^18 × 19次操作，这个量级任何计算机都跑不完。就算是区间长度小一点，比如10^9，也基本要跑好几秒甚至超时。所以必须找到一种方法，利用数字的“位”结构来压缩状态。

数位DP的本质就是：把“从0到N”的枚举，转化成对每一位的决策，并用记忆化避免重复计算。对于平衡数这题，我们枚举支点位置，然后从高位到低位逐位填数字，同时维护当前的力矩差值，最后看差值是否为零。

2. 状态设计与转移方程的推导

2.1 支点枚举的必要性

平衡数的定义里，支点位置是不确定的。一个数可能有多个支点，也可能没有。比如0有无数个支点（因为两边都是0），但通常我们只统计一次。

最直接的想法是：枚举支点位置。对于一个最多有len位的数，支点可能在第1位到第len位。我们固定支点，然后统计在这个支点下满足力矩平衡的数的个数。最后把所有支点的结果加起来，再减去重复计数的部分。

这里有个关键点：一个数如果有多个支点，会被重复统计。但实际上，除了0以外，一个数最多只有一个支点。这个结论可以简单证明：假设有两个不同的支点，那么两个支点之间的力矩关系会导致矛盾。所以除了0，其他数最多贡献一次。0比较特殊，它在每个支点下都被统计了一次，所以最后要减去(len - 1)次多余的0。

2.2 力矩差值的状态表示

固定支点后，我们需要在逐位填数的过程中维护一个“力矩差”。具体来说，如果当前填到第pos位（从高位往低位），支点在pivot位，那么这一位的贡献是：digit × (pos - pivot)。左边为正，右边为负，或者反过来，只要最后总和为0就行。

这个力矩差的范围是多少？假设最多19位，每位最大9，距离最大18，那么单边最大力矩大约是9 × (1+2+...+18) = 9 × 171 = 1539。两边差值范围大概在[-1539, 1539]之间。所以我们可以用一个偏移量offset = 2000左右来把负数映射到数组下标。

状态可以设计为：dp[pos][pivot][sum]，表示当前处理到第pos位，支点在pivot，当前力矩差为sum（加上偏移量后）的方案数。但这样三维数组，pos最多19，pivot最多19，sum最多4000左右，总状态数19 × 19 × 4000 ≈ 1.44M，完全可接受。

不过实际写的时候，我们通常把pivot放在外层枚举，dp数组只记pos和sum，这样每次枚举pivot时清空dp数组。虽然多了一些重复计算，但代码更清晰，而且状态数更少。

2.3 前导零的处理技巧

前导零是数位DP里最容易出错的地方。对于平衡数这题，前导零会影响支点的选择。比如数字00123，实际上就是123，但如果你把前导零也当成有效位，支点位置就变了。

处理方式有两种：一种是在状态里加一个flag表示是否还在前导零阶段，另一种是枚举支点时只考虑有效位。我比较推荐第一种，因为更通用。

具体来说，在dfs过程中，如果当前位之前全是前导零，且当前位填0，那么这一位不贡献力矩，支点位置也不变（或者说支点还没确定）。只有当填了第一个非零数字后，支点才真正开始起作用。

但这样会带来一个问题：支点是在枚举时固定的，如果前导零导致实际有效位数变少，支点位置可能需要调整。所以更稳妥的做法是：在枚举支点时，支点位置是相对于有效数字的位置。我们可以先确定数字的总位数，然后枚举支点在这个位数中的位置。

实际编码时，我通常这样处理：dfs(pos, pivot, sum, lead, limit)，其中lead表示是否还在前导零。如果lead为真且当前填0，那么sum不变，继续下一位。如果lead为真且填了非零，那么这一位开始贡献力矩，距离是pos - pivot。

2.4 记忆化的边界条件

记忆化的条件是：当没有limit限制时，可以记录dp[pos][sum]的值。注意这里pivot是外层枚举的，所以dp数组不需要包含pivot维度，但每次换pivot要重新初始化。

边界条件是pos < 0时，返回sum == 0 ? 1 : 0。但要注意，如果整个数都是前导零（即数字0），那么sum始终为0，会被统计一次。由于我们枚举了所有支点，0会被统计len次，最后要减去(len - 1)。

还有一个细节：当lead为真时，不应该记录dp值，因为此时sum的状态依赖于前导零的处理，不同支点下可能不同。不过由于pivot是外层枚举的，lead为真时sum始终为0，记录也无妨，但为了安全起见，通常不记录lead为真的状态。

3. 完整代码实现与逐行解析

3.1 代码框架与变量定义

#include <bits/stdc++.h> using namespace std; typedef long long ll; int digit[20]; ll dp[20][4000]; int pivot; ll dfs(int pos, int sum, bool lead, bool limit) { if (pos < 0) return sum == 0; if (!limit && !lead && dp[pos][sum] != -1) return dp[pos][sum]; int up = limit ? digit[pos] : 9; ll res = 0; for (int i = 0; i <= up; i++) { if (lead && i == 0) { res += dfs(pos - 1, sum, true, limit && i == up); } else { res += dfs(pos - 1, sum + i * (pos - pivot), false, limit && i == up); } } if (!limit && !lead) dp[pos][sum] = res; return res; } ll solve(ll n) { if (n < 0) return 0; int len = 0; while (n) { digit[len++] = n % 10; n /= 10; } if (len == 0) { digit[len++] = 0; } ll ans = 0; for (pivot = 0; pivot < len; pivot++) { memset(dp, -1, sizeof(dp)); ans += dfs(len - 1, 2000, true, true); } return ans - (len - 1); } int main() { int T; cin >> T; while (T--) { ll L, R; cin >> L >> R; cout << solve(R) - solve(L - 1) << endl; } return 0; }

这段代码就是完整的解法。下面我逐部分解释。

3.2 dfs函数的参数含义与转移逻辑

pos表示当前处理到第几位（从高位往低位，0是最高位，len-1是最低位）。注意这里的pos是从len-1递减到0，所以pos - pivot就是当前位到支点的距离。如果pos > pivot，距离为正，表示在支点左边；如果pos < pivot，距离为负，表示在支点右边。

sum是当前力矩差，初始值设为2000（偏移量），因为力矩差可能为负。最后判断sum == 2000时表示平衡。

lead表示是否还在前导零阶段。如果lead为真且当前填0，那么这一位不贡献力矩，继续下一位。如果填了非零，lead变为false，开始正常贡献。

limit表示是否受到上界限制。如果limit为真，当前位最多填digit[pos]；否则可以填0到9。

转移逻辑很直接：枚举当前位填什么，如果还在前导零且填0，sum不变；否则sum加上i × (pos - pivot)。然后递归下一位。

3.3 solve函数的区间处理与支点枚举

solve(n)计算的是[0, n]内平衡数的个数。如果n < 0返回0。然后把n的每一位拆到digit数组里，注意digit[0]是最低位，digit[len-1]是最高位。但在dfs里，pos是从len-1到0，所以pos对应的是高位到低位。

然后枚举pivot从0到len-1。每次枚举前清空dp数组。调用dfs(len-1, 2000, true, true)。最后把所有pivot的结果加起来，减去(len - 1)。

为什么减去(len - 1)？因为数字0在每个pivot下都被统计了一次，总共统计了len次，但实际只应该算一次，所以要减去len - 1次。

3.4 偏移量的选择与数组大小

偏移量选2000是经验值。最大力矩差是多少？假设19位，每位最大9，距离最大18，单边最大力矩是9 × (1+2+...+18) = 9 × 171 = 1539。两边差值最大是1539 - 0 = 1539，或者0 - 1539 = -1539。所以sum的范围是[-1539, 1539]，加上偏移量2000后范围是[461, 3539]。数组开4000足够。

实际写的时候，我习惯开dp[20][4000]，偏移量用2000。这样既不会越界，也不会浪费太多空间。

3.5 时间复杂度的估算

外层枚举pivot，最多19次。每次dfs的状态数是pos × sum = 19 × 4000 = 76000。每个状态转移最多10次。所以单次dfs大约是76000 × 10 = 760000次操作。总共19次pivot，大约是1.44 × 10^7次操作。对于T组测试数据，如果T = 100，总操作量是1.44 × 10^9，可能会超时。

优化方法：不要每次pivot都清空dp数组，而是把pivot也作为dp的一个维度。这样dp[pos][pivot][sum]，状态数19 × 19 × 4000 = 1.44M，但只需要计算一次。不过内存会大一些，1.44M × 8字节 ≈ 11.5MB，可以接受。

或者，注意到solve(R)和solve(L-1)会重复计算很多状态，可以把dp数组做成全局的，只初始化一次。但pivot不同时状态不能共用，所以还是需要pivot维度。

我实际测试下来，对于T = 100，R = 10^18的情况，不优化也能过，因为很多状态实际上不会被访问到。但如果T更大，建议加上pivot维度。

4. 常见错误与调试经验

4.1 前导零导致的重复计数

最常见的错误就是前导零处理不当。比如数字0，如果不在最后减去(len - 1)，会被统计len次。还有数字10，如果前导零处理不对，可能会把01当成一个有效的两位数，支点位置就错了。

我当初写的时候，犯过一个错误：在lead为真时，仍然让sum加上i × (pos - pivot)。这样当i = 0时，sum不变，看起来没问题。但当i > 0时，lead变为false，这一位的贡献是对的。问题在于，如果整个数都是前导零，sum始终为0，最后返回1，这是对的。但如果前导零后面有非零数字，支点位置是相对于整个len的，而不是相对于有效数字的。比如数字00123，len = 5，支点枚举的是0到4，但实际有效数字是123，支点应该在1到3之间。这样就会导致错误。

解决方法：在枚举pivot时，只考虑有效位。但有效位在dfs之前不知道，所以更通用的做法是在dfs里动态调整。不过这样比较复杂。我推荐的做法是：先确定数字的实际长度，然后在solve里枚举pivot时，只枚举0到len-1，但在dfs里，如果lead为真，支点位置实际上还没确定，所以距离计算要特殊处理。

实际编码时，我采用的方式是：在dfs里，如果lead为真且i == 0，直接递归下一位，不贡献力矩。这样支点位置pivot是相对于整个len的，但前导零不贡献力矩，所以实际效果等价于支点相对于有效数字。但要注意，如果整个数都是0，那么所有pivot下sum都是0，最后减去(len - 1)即可。

4.2 力矩差值为负的处理

sum可能为负，所以要用偏移量。我见过有人用map来存状态，虽然可以，但效率低。用数组加偏移量是最快的。

偏移量选多少？我一般选2000，因为最大力矩差不超过1600。但如果你不确定，可以选3000或4000，数组开大一点，不会影响正确性，只是多占点内存。

4.3 多组测试数据的初始化问题

如果有多组测试数据，dp数组每次都要清空。但清空整个4000 × 20的数组需要时间。优化方法是把dp数组初始化为-1，但只初始化用到的部分。或者用时间戳标记，避免重复清空。

我通常的做法是：在solve函数里，每次枚举pivot时，memset(dp, -1, sizeof(dp))。虽然有点慢，但对于T = 100来说，100 × 19 × 4000 × 8字节 ≈ 60MB的写入，现代计算机几毫秒就完成了，可以接受。

如果T很大，比如10^5，那就需要优化。可以把dp数组做成全局的，用pivot作为一维，这样只需要初始化一次。但要注意，solve(R)和solve(L-1)会共用dp数组，所以dp数组不能包含limit和lead的信息，这些在记忆化时已经排除了。

4.4 边界情况：L = 0, R = 0

如果L = 0, R = 0，答案应该是1（0是平衡数）。solve(0)会返回1，solve(-1)返回0，所以结果是1。但要注意，solve(0)里len = 1，pivot枚举0到0，dfs返回1，最后减去(len - 1) = 0，所以结果是1。正确。

如果L = 1, R = 1，答案应该是1（1是平衡数，支点在1本身，两边力矩都是0）。solve(1)返回2（0和1），solve(0)返回1，所以结果是1。正确。

4.5 常见问题速查表

5. 数位DP的通用套路与扩展

5.1 数位DP的通用模板

数位DP的题目千变万化，但核心套路是固定的。我总结了一个通用模板：

ll dfs(int pos, /* 状态参数 */, bool lead, bool limit) { if (pos < 0) return /* 边界条件 */; if (!limit && !lead && dp[pos][/* 状态 */] != -1) return dp[pos][/* 状态 */]; int up = limit ? digit[pos] : 9; ll res = 0; for (int i = 0; i <= up; i++) { if (lead && i == 0) { res += dfs(pos - 1, /* 状态不变 */, true, limit && i == up); } else { res += dfs(pos - 1, /* 状态转移 */, false, limit && i == up); } } if (!limit && !lead) dp[pos][/* 状态 */] = res; return res; }

这个模板适用于绝大多数数位DP题目。区别只在于状态参数的设计和转移方程。

5.2 从平衡数到其他数位DP题

平衡数这题的状态是力矩差，其他题可能是数位和、数位乘积、模数等。比如统计数位和能被某个数整除的数的个数，状态就是数位和对模数的余数。统计包含某些数字的数的个数，状态就是是否出现过这些数字的标记。

我建议初学者从平衡数这题入手，因为它状态简单，但又包含了数位DP的所有关键点：支点枚举、前导零、记忆化、区间减法。把这题写熟练了，其他题就是换汤不换药。

5.3 记忆化搜索与递推的取舍

数位DP有两种写法：记忆化搜索和递推。记忆化搜索更直观，代码更短，适合初学者。递推效率更高，但代码复杂，容易出错。

我个人的习惯是：先用记忆化搜索写一遍，确保正确。如果超时，再考虑改成递推或者优化状态。对于平衡数这题，记忆化搜索完全够用，不需要递推。

5.4 实操心得与避坑建议

第一，前导零一定要处理。我见过太多人因为前导零导致答案错误，调试半天找不到原因。记住：前导零不贡献力矩，但支点位置是相对于整个数字的。

第二，偏移量要足够大。不要为了省内存把偏移量设得很小，否则会越界。我一般设2000，数组开4000，稳妥。

第三，多组数据要清空dp数组。如果不清空，上一组的数据会污染下一组的结果。虽然memset有点慢，但正确性优先。

第四，0要特殊处理。0是平衡数，但在每个支点下都被统计了一次，最后要减去(len - 1)。这个细节很容易忽略。

第五，支点枚举范围是0到len-1。不要从1开始，也不要到len结束。支点可以在最高位，也可以在最低位。

第六，limit和lead为真时不记录dp值。因为这两种状态下，后续的决策依赖于前面的限制，不是独立的状态。

第七，用long long存答案。虽然平衡数的个数不会超过R，但R可能到10^18，int会溢出。

第八，输入输出用scanf/printf或者关闭同步的cin/cout。如果T很大，cin/cout可能会慢。

5.5 性能优化技巧

如果T很大，比如10^5，那么每次solve都要重新计算，效率很低。优化方法是：把dp数组做成全局的，用pivot作为一维，这样只需要初始化一次。但要注意，solve(R)和solve(L-1)会共用dp数组，所以dp数组不能包含limit和lead的信息。

具体做法：dp[pos][pivot][sum]，初始化为-1。在dfs里，如果!limit && !lead，就记录dp[pos][pivot][sum]。这样无论solve多少次，dp数组只需要初始化一次。但内存会大一些，19 × 19 × 4000 × 8字节 ≈ 11.5MB，可以接受。

另外，可以把digit数组和len做成全局的，避免每次solve都重新计算。但要注意，solve(R)和solve(L-1)的digit数组不同，所以每次solve前要重新拆分。

还有一个优化：如果R = 0，直接返回1。如果L = 0，solve(L-1)返回0。这些边界情况可以提前判断，避免不必要的计算。

6. 从解题到实战：数位DP的应用场景

6.1 数位DP在竞赛中的常见题型

数位DP在算法竞赛中出现频率很高，常见的题型包括：统计区间内满足数位和条件的数、统计区间内包含某些数字的数、统计区间内数位乘积满足条件的数、统计区间内数位排列满足条件的数等。

平衡数这题属于“数位加权和”类型，特点是每一位的贡献与位置有关。类似的题目还有：统计区间内数位平方和满足条件的数、统计区间内数位立方和满足条件的数等。

6.2 数位DP在实际工程中的应用

虽然数位DP看起来像是竞赛专用，但它在实际工程中也有应用。比如：生成满足某些数位条件的ID、校验码的生成与验证、密码强度的统计等。

我做过一个项目，需要生成一批满足特定数位模式的序列号。用数位DP可以快速统计出满足条件的序列号有多少个，然后按需生成。比暴力枚举快了几个数量级。

6.3 学习数位DP的路线建议

如果你刚接触数位DP，我建议按这个顺序刷题：先做最简单的“统计区间内不含某些数字的数”，再做“统计区间内数位和能被整除的数”，然后做平衡数这题，最后做带模数或者多状态的数位DP。

每道题都要自己先想状态设计，想不出来再看题解。看完题解后，一定要自己手写一遍，不要复制粘贴。写完后，自己造几组测试数据，验证正确性。

6.4 个人体会

数位DP这玩意儿，说难不难，说简单也不简单。关键是要理解“逐位决策”和“记忆化”这两个核心思想。一旦理解了，大部分题都能套模板。

我当初学的时候，卡在前导零处理上很久。后来想明白了：前导零就是“还没开始填有效数字”的状态，在这个状态下，任何位都不贡献，支点也没确定。把这个状态单独处理，问题就迎刃而解了。

还有一点：不要怕写错。数位DP的代码虽然不长，但细节很多。多写几遍，多调试几次，自然就熟练了。我现在的习惯是，每道数位DP题都先写记忆化搜索，确保正确后再考虑优化。这样虽然代码长一点，但不容易出错。

最后分享一个小技巧：如果实在想不出状态怎么设计，就先写暴力，然后观察暴力过程中哪些状态是重复的，把这些状态提取出来，就是DP的状态。这个方法虽然笨，但很有效。