1042 数字0-9的数量 51 Nod1042 数字0到9的数量-LMLPHP

基准时间限制:1 秒 空间限制:131072 KB 分值: 10 难度:2级算法题

给出一段区间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

一道很注重细节的题目。很容易出现0的数量不正确的情况,但排除困难终于ac后的喜悦也是很激励人心的。

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
ll sum_a[10];ll sum_b[10];
void dfs(ll n,ll cnt,ll *arr,string now)
{
ll digit=n%10;ll m=n/10;
if(m==0)//若digit为最高位
{
for(int i=1;i<digit;i++)arr[i]+=cnt;
if(now!="")arr[digit]+=stoll(now)+1;
else arr[digit]+=1;
if(digit!=0)arr[0]++;
return;
}
for(int i=0;i<digit;i++)//当高位都取可以达到的最大数时且本位小于最高取值时可任意填
arr[i]+=cnt;
if(now!="")arr[digit]+=stoll(now)+1;
else arr[digit]++;
for(int i=0;i<10;i++)//当高位组成小于可以达到的最大数时可任意填
arr[i]+=(m-1)*cnt;
for(int i=1;i<10;i++)arr[i]+=cnt;//当高位全0时
string next="";next+=('0'+digit);next+=now;
dfs(m,cnt*10,arr,next);
}
int main()
{
ll a,b;
scanf("%lld%lld",&a,&b);
dfs(a-1,1,sum_a,"");dfs(b,1,sum_b,"");
for(int i=0;i<10;i++)
printf("%lld\n",sum_b[i]-sum_a[i]);
}
05-11 21:45