首页 > 代码库 > 51nod 1042 数字0-9的数量 (数位dp、dfs、前导0)

51nod 1042 数字0-9的数量 (数位dp、dfs、前导0)

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


终于过了,前导零太烦了。
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
ll ten[20]={1},a[20],dp[20];
void init()
{
    for(ll i=1;i<20;i++)
        ten[i]=ten[i-1]*10;
}
ll dfs(ll pos,ll num,ll lead,ll limit,ll who)
{
    if(pos==-1) return num;
    if(!limit&&dp[pos]!=-1&&!lead) return num*ten[pos+1]+dp[pos];
    ll up=limit?a[pos]:9;
    ll tmp=0;
    if(who!=0)
        for(int i=0;i<=up;i++)
        tmp+=dfs(pos-1,num+(who==i),0,limit&&a[pos]==i,who);
    else
        for(int i=0;i<=up;i++)
        tmp+=dfs(pos-1,num+(who==i&&!lead),lead&&i==0,limit&&a[pos]==i,who);
    if(!limit&&!lead) dp[pos]=tmp;
    return tmp;
}
ll solve(ll n,ll m)
{
    ll pos=0;
    while(n)
    {
        a[pos++]=n%10;
        n/=10;
    }
    return dfs(pos-1,0,1,1,m);
}
int main()
{
    ll x,y;
    ios::sync_with_stdio(false);
    init();
    cin>>x>>y;
    for(ll i=0;i<=9;i++)
    {
        memset(dp,-1,sizeof(dp));
        cout<<solve(y,i)-solve(x-1,i)<<endl;
    }
    return 0;
}

  

  

51nod 1042 数字0-9的数量 (数位dp、dfs、前导0)