51 Nod1042 数字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示例

一道很注重细节的题目。很容易出现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
",sum_b[i]-sum_a[i]);
}