小引 起因是bro在做“就要62”这道入门题，发现了它的好bro“不要62”，如你所见它没有几个人过并且还是一道“提高+/省选-”的题，so,我打算发一个题解 问题分析 这道题要求统计区间 [n, m] 内不包含数字 4 且不包含连续数字 62 的数的个数。直接暴力枚举每个数并检查会超时（因为 m 可以接近 10^7），所以需要用数位动态规划（数位 DP） 来高效解决。 数位 DP 的核心思想是：将数字按位分解，通过状态记录关键信息（如前一位是否是 6），递归 / 记忆化搜索所有合法的数字组合，避免重复计算。 完整代码 有注释版 无注释版 代码解释 1.核心函数 calc(x)：计算 0~x 中合法的数字个数，是数位 DP 的入口： * 将数字 x 分解为各位（如 123 分解为 [1,2,3]），存储到 digits 数组。 * 初始化 DP 数组，调用 dfs 进行记忆化搜索。 2.记忆化搜索 dfs(pos, pre, limit)： * 终止条件：pos == digits.size()，表示所有位处理完，返回 1（找到一个合法数）。 * 记忆化优化：如果当前状态（无限制）已计算过，直接返回结果，避免重复递归。 * 枚举当前位：遍历 0~up（up 是当前位的上界），跳过含 4 或 62 的情况。 * 递归下一位：传递新的状态（下一位、当前位数字、新的限制），累加合法数个数。 3.主函数： * 输入 n, m，直到 0 0 结束。 * 区间 [n, m] 的合法数 = calc(m) - calc(n-1)（容斥原理）。 测试用例验证 输入：1 100 * calc(100)：0~100 中合法数的个数是 81（包含 0）。 * calc(0)：0 是合法数，返回 1。 * 结果：81 - 1 = 80，与样例输出一致。 总结 1.核心思路：用数位 DP 避免暴力枚举，通过记忆化搜索统计合法数字个数，时间复杂度为 O (位数 × 10 × 2)，效率极高。 2.关键状态：记录当前处理的位数、前一位数字、是否有上界限制，确保不重复计算且不遗漏合法数字。 3.容斥原理：区间 [n, m] 的结果 = calc(m) - calc(n-1)，需注意边界（如 n=1 时，n-1=0）。 . . . . . . . . . . . . . . . . . . . . 你以为这就完了吗？ 别忘了为什么我要说这个题没几个人做过，因为我想拿那三颗宝石 要想拿到宝石，就必须控制内存和时间 极致优化版 带注释 不带注释 注释核心说明 1.分段注释：将代码分为「预处理初始化」「预处理递推」「主逻辑计算」三大块，逻辑边界清晰； 2.变量注释：每个全局 / 局部变量都标注用途，尤其是dp数组的状态定义（新手最难理解的部分）； 3.状态转移注释：详细解释dp[c][0]和dp[c][1]的递推逻辑，包括每一步的选择数来源； 4.边界处理注释：对ans++/ans--、break等关键边界修正逻辑标注原因； 5.逐位统计注释：解释 “枚举当前位 0~ 当前值 - 1” 的核心思想，以及不吉利数字的过滤逻辑。