数字0-9的数量（51Nod 1042）

╰+哭是因爲堅強的太久メ 2022-05-14 10:37 137阅读 0赞

[原题链接][Link 1]  
**题目描述：**  
给出一段区间a-b，统计这个区间内0-9出现的次数。  
比如 10-19，1出现11次（10,11,12,13,14,15,16,17,18,19,其中11包括2个1)，其余数字各出现1次。

**Input：**  
两个数a,b（1 <= a <= b <= 10^18)

**Output：**  
输出共10行，分别是0-9出现的次数

**Input示例**  
10 19  
**Output示例**  
1  
11  
1  
1  
1  
1  
1  
1  
1  
1

**分析**  
用递归来计算每一位。每一位可为计算过的低位，当前位，未计算的高位。  
则处理当前位有：  
1、当前位与低位的关系  
2、高位与低位的关系  
3、当前为与高位的关系  
对三种情况进行处理即可。要注意0除外。

**代码如下**
    #include<iostream> 
    using namespace std;
    typedef long long ll;
    void dfs(ll a,ll b,ll c[]){ 
    	ll n=a/10,m=a%10,t=n;
    	for(int i=0;i<=m;i++) c[i]+=b; //当前位对低位的影响
    	for(int i=0;i<10;i++) c[i]+=b*n; //高位对地位的影响。
    	c[0]-=b;    //将多算的0减去
    	while(t) {   //当前位对高位的影响 
    		c[t%10]+=b*(m+1);  //加上0 
    		t/=10;
    	}
    	if(n) dfs(n-1,b*10,c); //n已经处理过，处理n-1 
    }
    ll x[20],y[20];
    int main(){ 
    	ll a,b;
    	cin>>a>>b;
    	dfs(a-1,1,x);
    	dfs(b,1,y);
    	for(int i=0;i<10;i++) cout<<y[i]-x[i]<<endl;
    	return 0;
    }

[Link 1]: https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1042

发表评论取消回复

表情：

评论列表（有 0 条评论，137人围观）

还没有评论，来说两句吧...

相关阅读

相关 51nod1009 数字1的数量

[1009 数字1的数量][1009 _1] ![ok.png][] 基准时间限制：1 秒空间限制：131072 KB 分值: 5 [1009 _1]: http://

逃离我推掉我的手/ 2024年02月17日 22:56/ 0 赞/ 49 阅读

相关 51nod1003 阶乘后面0的数量

[1003 阶乘后面0的数量][1003 _0] ![ok.png][] 基准时间限制：1 秒空间限制：131072 KB 分值: 5 [1003 _0]: http:

落日映苍穹つ/ 2024年02月17日 22:56/ 0 赞/ 50 阅读

相关 51nod 1043

题意：求在2\n位的数字中，前n位的和等于后n位的和的个数，比喻n=1的时候，11,22,33...99等数字都是的，还有1102，2121等都是满足要求的数字。n<=10

灰太狼/ 2022年08月21日 03:14/ 0 赞/ 216 阅读

相关 51nod-加农炮

一个长度为M的正整数数组A，表示从左向右的地形高度。测试一种加农炮，炮弹平行于地面从左向右飞行，高度为H，如果某处地形的高度大于等于炮弹飞行的高度H（A\[i\] >= H），

男娘i/ 2022年06月17日 14:08/ 0 赞/ 226 阅读

相关 51Nod--1004 n^n的末位数字

题目链接：[http://www.51nod.com/onlineJudge/questionCode.html\!problemId=1004][http_www.51nod

古城微笑少年丶/ 2022年06月15日 12:22/ 0 赞/ 132 阅读

相关 51Nod--1003 阶乘后面0的数量

题目链接：[http://www.51nod.com/onlineJudge/questionCode.html\!problemId=1003][http_www.51nod

「爱情、让人受尽委屈。」/ 2022年06月15日 11:45/ 0 赞/ 160 阅读

相关 51nod--1284

[1284 2 3 5 7的倍数][1284_2_3_5_7] ![ok.png][] 基准时间限制：1 秒空间限制：131072 KB 分值: 5 [难度：1级算法题][

分手后的思念是犯贱/ 2022年05月27日 11:22/ 0 赞/ 206 阅读

相关数字0-9的数量（51Nod 1042）

[原题链接][Link 1] 题目描述：给出一段区间a-b，统计这个区间内0-9出现的次数。比如 10-19，1出现11次（10,11,12,13,14,15,

╰+哭是因爲堅強的太久メ/ 2022年05月14日 10:37/ 0 赞/ 138 阅读

相关 51nod 1009：数字1的数量

[1009 数字1的数量][1009 _1] ![ok.png][] 基准时间限制：1 秒空间限制：131072 KB 分值: 5 [难度：1级算法题][1] ![sta

不念不忘少年蓝@/ 2021年12月21日 00:25/ 0 赞/ 207 阅读

相关 51nod 2499 不降的数字

小b有一个非负整数 `N`，她想请你找出 ≤N≤N 的最大整数x，满足x各个位数上的数字是不降的。也就是说，设x的十进制表示为 a1,a2,…,ama1,a2,…,am，则对于

落日映苍穹つ/ 2021年12月10日 03:19/ 0 赞/ 173 阅读