338. 计数问题
摘要
Title: 338. 计数问题
Tag: 数位dp
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
338. 计数问题
-
题意
给定两个整数 a 和 b，求 a 和 b 之间的所有数字中 0∼9 的出现次数。
例如，a=1024，b=1032，则 a 和 b 之间共有 9 个数如下：
1024 1025 1026 1027 1028 1029 1030 1031 1032
其中 0 出现 10 次，1 出现 10 次，2 出现 7 次，3 出现 3 次等等… -
思路
可以再参照这篇博客 link
-
代码
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
38from math import log10
def count(n, d): #求从1到数n中数d出现的次数
len = int(log10(n) + 1) if n > 0 else 0
res = 0
for i in range(1, len + 1): #高位到低位
# 求 1 <= xxxdyyy <= opqrstu 多少个xxxdyyy
# opqrstu ex: i = 4, l = opq, r = stu, di = r
# xxxdyyy
p = 10 ** (len - i)
l = n // p // 10
r = n % p
di = n // p % 10
# xxx < opq
if d:
res += l * p
else:
res += (l - 1) * p
# xxx = opq
if di == d:
res += r + 1
if di > d:
res += p
return res
while True:
try:
a, b = map(int, input().split())
if a == 0 and b == 0:
break
if a > b:
a, b = b, a
for i in range(10):
print(count(b, i) - count(a - 1, i), end = " ")
print()
except:
break
