洛谷P1980

题目描述

试计算在区间 1 到 n的所有整数中,数字x(0 ≤ x ≤ 9)共出现了多少次?例如,在 111中,即在 1,2,3,4,5,6,7,8,9,10,11 中,数字 1 出现了 4 次。

输入格式

2个整数n,x,之间用一个空格隔开。

输出格式

1个整数,表示x出现的次数。

输入输出样例

输入

11 1

输出

4

说明/提示

对于 的数据,1≤ n ≤ 1,000,000,0 ≤ x ≤ 9

正常思路

0-9里面有1个单位x的数字有C(1,1)*1*9^0个

0-99里面有1个单位x的数字有C(2,1)*1*9^1个,有2个单位x的数字有C(2,2)*2*9^0个

0-999里面有1个单位x的数字有C(3,1)*1*9^2,有两个单位x的数字有C(3,2)*2*9^1个,有3个单位的数字x有C(3,3)*3*9^0个

变通一下就可以求0-1000的有多少个x
再变通一下就可以求0-2000,0-3000,0-4000……0-9000有多少个x
再变通一下就可以求0-n有多少个x
例如12345=10000+2000+300+40+5
最后就可以求1-n有多少个数字x了

另一种思路

x=input().split()
lt=[] for i in range(1,int(x[0])+1):
	lt.extend(list(str(i)))
print(lt.count(x[1])

    发表评论

    电子邮件地址不会被公开。必填项已用 * 标注