[ZJOI2010]COUNT 数字计数

[编程题][ZJOI2010]COUNT 数字计数

热度指数：1926 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定两个正整数a和b，求在[a,b]中的所有整数中，每个数码(digit)各出现了多少次。

输入描述:

输入文件中仅包含一行两个整数a、b，含义如上所述。

输出描述:

输出文件中包含一行10个整数，分别表示0-9在[a,b]中出现了多少次。

示例1

输入

1 99

输出

9 20 20 20 20 20 20 20 20 20

备注:

对于30%的数据，保证；
对于100%的数据，保证 。

算法知识视频讲解

Python 3

pein531

数位DP模板题，可以参考灵茶山艾府的模板“https://leetcode.cn/problems/count-special-integers/solution/shu-wei-dp-mo-ban-by-endlesscheng-xtgx/”，例题是力扣周赛第306场的压轴题，对模板稍作修改即可通过本题。

from functools import lru_cache

a, b = map(int, input().split())

@lru_cache(None)
def dfs(i: int, tot: int, is_limit: bool, is_num: bool) -> int:
    if i == n:
        return tot
    cnt = dfs(i + 1, tot, False, is_num) if not is_num else 0
    ub = int(s[i]) if is_limit else 9
    # 当前位置的数可以是[1-is_num, ub]
    for d in range(1 - int(is_num), ub + 1):
        cnt += dfs(i + 1, tot + int(digit == d), is_limit and d == int(s[i]), True)
    return cnt

for digit in range(0, 10):
    s = str(a - 1)
    n = len(s)
    lb = dfs(0, 0, True, False)
    dfs.cache_clear()
    s = str(b)
    n = len(s)
    ub = dfs(0, 0, True, False)
    dfs.cache_clear()
    print(ub - lb, end=' ')

发表于 2023-02-10 17:39:19 回复(0)