1085 不要62（数位dp）

墨蓝 2022-09-14 09:20 150阅读 0赞

**1. 问题描述：**

杭州人称那些傻乎乎粘嗒嗒的人为 62（音：laoer）。杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。不吉利的数字为所有含有 4 或 62 的号码。例如：62315，73418，88914 都属于不吉利号码。但是，61152 虽然含有 6 和 2，但不是连号，所以不属于不吉利数字之列。你的任务是，对于每次给出的一个牌照号区间 \[n，m\]，推断出交管局今后又要实际上给多少辆新的士车上牌照了。

**输入格式**

输入包含多组测试数据，每组数据占一行。每组数据包含一个整数对 n 和 m。  
当输入一行为“0 0”时，表示输入结束。

**输出格式**

对于每个整数对，输出一个不含有不吉利数字的统计个数，该数值占一行位置。

**数据范围**

1 ≤ n ≤ m ≤ 10 ^ 9

**输入样例：**

1 100  
0 0

**输出样例：**

80  
来源：[https://www.acwing.com/problem/content/description/1087/][https_www.acwing.com_problem_content_description_1087]

**2. 思路分析：**

分析题目可以知道，我们需要求解出区间\[n，m\]中的数字的位中不包含数字4和不包含连续的62的方案数目，由这个特点可以知道这道题目属于**数位dp**的题目，对于数位dp的题目都有固定的套路，一般采用树的形式来分析，并且对于数位dp的问题一般难点在于预处理，所以关键是预处理的过程，可以发现这道题目与之前做的[数字游戏][Link 1]，[Windy数][Windy]的题目是很像的，我们可以使用类似的状态表示和状态计算的方法预处理得到数组f（预处理的目的是为了后面枚举第i位填0~x-1的时候可以直接算出来），可以发现对于这道题目来说声明一个二维数组f即可表示所有的状态，其中f\[i\]\[j\]表示总共有i位且最高位为j的方案数目，在状态计算的时候也是类似的，因为当前填的这一位数字只与上一位数字有关系，所以可以使用三层循环枚举，第一层循环枚举总共有i位数字，第二层循环枚举i位数字的最高位填j，第三层循环枚举i位数字次高位填k，因为不包含4或者是62所以在枚举的时候跳过这些不合法的状态即可，最终预处理之后就可以得到数组f；接下来就是数位dp的常规步骤了，以区间其中一个端点为y例，我们需要将y的每一位抠出来储存到nums中，然后逆序枚举nums中的每一位数字，对于第i位数字x= nums\[i\]，我们可以考虑填0 ~ x-1的情况，填0 ~ x-1的情况属于左边的分支，可以将预处理的结果累加到res中即可，当进入到循环的下一位的时候第i位填就是x，并且我们需要使用last来记录前缀信息，对于这道题目来说则需要记录上一位填的数字是什么，这样可以跳过那些不合法的状态。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_9_color_FFFFFF_t_70_g_se_x_16][]

**3. 代码如下：**

from typing import List
    
    
    class Solution:
        def init(self, N: int, f: List[List[int]]):
            # 只有一位数字的方案
            for i in range(10):
                # 主要是不是4说明就是满足要求
                if i != 4:
                    f[1][i] = 1
            for i in range(2, N):
                # 枚举总共有i位数字最高位填j
                for j in range(10):
                    # 最高位为4的那么直接跳过
                    if j == 4: continue
                    # 枚举次高位填k
                    for k in range(10):
                        # 筛选掉不满足方案次高位为4或者是上一位与当前这一位构成了62说明不满足条件跳过
                        if j == 4 or (j == 6 and k == 2): continue
                        # 方案合法累加到结果即可
                        f[i][j] += f[i - 1][k]
    
        # 求解区间[0, n]中满足题目要求的方案数目
        def dp(self, n: int, f: List[List[int]]):
            # 特判一下n = 0的情况
            if n == 0: return 1
            nums = list()
            while n > 0:
                nums.append(n % 10)
                n //= 10
            # last记录前缀信息, 因为下一位只与上一位是有关系的所以使用last记录上一位数字是什么
            res, last = 0, 0
            for i in range(len(nums) - 1, -1, -1):
                x = nums[i]
                # 枚举最高位填0~x-1的情况
                for k in range(x):
                    # 当前这一位是4或者与上一位构成了62那么直接跳过
                    if k == 4 or (last == 6 and k == 2): continue
                    res += f[i + 1][k]
                # 判断这一位是否是4或者构成了62如果是说明进入循环的下一位的时候右边的分支是不合法的
                if x == 4 or (last == 6 and x == 2):
                    break
                else:
                    # 更新当前的last进入循环的下一位的时候表示上一位数字填x
                    last = x
                # 最右边的那个分支
                if i == 0: res += 1
            return res
    
        def process(self):
            # 预处理列表f
            N = 11
            f = [[0] * 10 for i in range(N)]
            self.init(N, f)
            while True:
                n, m = map(int, input().split())
                if n == 0 and m == 0: break
                print(self.dp(m, f) - self.dp(n - 1, f))
    
    
    if __name__ == "__main__":
        Solution().process()

[https_www.acwing.com_problem_content_description_1087]: https://www.acwing.com/problem/content/description/1087/
[Link 1]: https://blog.csdn.net/qq_39445165/article/details/120578154
[Windy]: https://blog.csdn.net/qq_39445165/article/details/120579239
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_9_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/faa95538c3f64437b746f0391e41e6ba.png