51 Nod1042 数字0到9的数量

1042 数字0-9的数量 

基准时间限制：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]);

}