不要 62

题目描述

杭州人称那些傻乎乎粘嗒嗒的人为 62（音：laoer）。杭州交通管理局以后发放的士牌照不再含有不吉利的数字：一个号码是不吉利的，当且仅当它含有数字 $4$ ，或含有相邻子串 $62$ 。例如 $62315, 73418, 88914$ 都不吉利；而 $61152$ 虽含 $6$ 和 $2$ 但不相邻，属于吉利号码。你的任务是，对每次给出的牌照区间 $[n, m]$ ，输出其中吉利号码的个数，每个数占一行；输入为多组整数对 $n, m$ ，遇到 $n = m = 0$ 时输入结束。样例中区间 $[1, 100]$ 内不吉利的数共 $20$ 个（含 $4$ 的 $19$ 个，加上 $62$ ），故答案为 $101 - 1 - 20 = 80$ 。

text

1
21 100
0 0

text

思路

区间计数先化成前缀相减：答案 $= f(m) - f(n-1)$ ，其中 $f(x)$ 是 $[0, x]$ 内不含 $4$ 和 $62$ 的数的个数。求 $f(x)$ 用数位 DP：从高到低逐位填数，状态记（当前位、是否贴着上界、上一位是否为 $6$ ），当前位填 $4$ 、或上一位是 $6$ 而本位填 $2$ 时剪掉；只有贴上界走到位值才保持 tight，前导零无需特判。状态数只有位数 $\times 2 \times 2$ ，每个询问调用两次即可。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 20:30
# update_at: 2026-09-30 20:30

import sys
from functools import cache


def count_upto(x: int) -> int:
    """数位 DP：[0, x] 里不含数字 4、也不含子串 62 的数有多少个。"""
    if x < 0:
        return 0                                  # n 可能为 0，此时区间下界比 0 还小
    digits = list(map(int, str(x)))

    @cache
    def dfs(pos: int, tight: bool, prev6: bool) -> int:
        """从高位 pos 起往低位填：前一位是否为 6、当前是否被上界掐住时，合法后缀的个数。

        前导零无需单独记录：0 既不是 4 也不会和 6 拼出 62，而真正的 6 只会
        出现在首位之后，所以只记"前一位是不是 6"就足以排除 62。
        """
        if pos == len(digits):
            return 1                              # 整数构造完成（含 0 本身）
        up = digits[pos] if tight else 9
        return sum(
            dfs(pos + 1, tight and d == up, d == 6)   # 只有贴着上界走才继续保持 tight
            for d in range(up + 1)
            if d != 4 and not (prev6 and d == 2)      # 跳过 4 与 62 的第二个 2
        )

    return dfs(0, True, False)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    for low in data:                              # 每次取一对 (n, m)，读到 0 0 结束
        high = next(data)
        if low == 0 and high == 0:
            break
        # [n, m] 的个数 = [0, m] 的个数 − [0, n-1] 的个数
        out.append(str(count_upto(high) - count_upto(low - 1)))
    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 00:55
 * update_at: 2026-10-06 00:55
 */

// 不要 62：数位 DP，统计区间内不含数字 4 且不含子串 62 的数的个数。

#include <cstdio>

typedef long long ll;

const int LEN = 12; // 上界 x 最多约 10 位，开 12 位够用

ll digits[LEN]; // digits[1..len] 保存上界 x 从高到低的每一位
ll len;         // 上界 x 的位数
ll memo[LEN][2][2]; // memo[pos][tight][prev6]：已算过的状态直接返回，-1 表示没算过

// 从第 pos 位开始填（pos 从 1 到 len），返回合法后缀的个数。
// tight   = 1 表示前面每位都贴着 x 的上界，当前位最多取 x 的对应位；
// prev6   = 1 表示上一位填的是 6，当前位再填 2 就会拼出 62。
// 前导零不用特判：0 不是 4，也不会让 prev6 变成 1。
ll dfs(ll pos, ll tight, ll prev6) {
    if (pos > len)
        return 1; // 整数构造完成（0 本身也算一个，前缀相减时会消去）
    if (memo[pos][tight][prev6] != -1)
        return memo[pos][tight][prev6];
    ll up = 9; // 不贴上界时当前位可以随便取 0~9
    if (tight)
        up = digits[pos]; // 贴上界时最多取 x 的对应位
    ll res = 0;
    for (ll d = 0; d <= up; d++) {
        if (d == 4)                 // 含数字 4，直接剪掉
            continue;
        if (prev6 == 1 && d == 2)   // 上一位是 6，这一位填 2 会拼出 62
            continue;
        // 只有每一位都贴着上界才保持 tight；本位填 6 才把 prev6 置 1
        res += dfs(pos + 1, tight && (d == up), (d == 6) ? 1 : 0);
    }
    memo[pos][tight][prev6] = res;
    return res;
}

// [0, x] 里吉利数（不含 4、不含 62）的个数；x < 0 时为 0。
ll count_upto(ll x) {
    if (x < 0)
        return 0;
    // 把 x 拆成十进制位，digits[1] 是最高位
    ll t = x;
    len = 0;
    while (t > 0) {
        len++;
        digits[len] = t % 10;
        t /= 10;
    }
    for (ll i = 1; i * 2 <= len; i++) { // 反转成从高到低
        ll swap_tmp = digits[i];
        digits[i] = digits[len + 1 - i];
        digits[len + 1 - i] = swap_tmp;
    }
    // 记忆化数组只清会用到的范围
    for (ll i = 1; i <= len + 1; i++)
        for (ll j = 0; j < 2; j++)
            for (ll k = 0; k < 2; k++)
                memo[i][j][k] = -1;
    return dfs(1, 1, 0);
}

int main() {
    ll n, m;
    while (scanf("%lld %lld", &n, &m) == 2) {
        if (n == 0 && m == 0)
            break; // 0 0 结束输入
        // 区间 [n, m] 的答案 = 前缀相减 f(m) - f(n-1)
        printf("%lld\n", count_upto(m) - count_upto(n - 1));
    }
    return 0;
}

目录

题目描述

思路

参考代码