51nod 1042 数字0-9的数量【数位dp】

时间:2022-12-15 23:01:05

题目:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1042

题意:

51nod 1042 数字0-9的数量【数位dp】

分析:

做了一会儿没刚出来,囧 /\
这题和1009差不多
1009看这篇博客写得很清楚,会了这题再来写这题就容易了。
http://blog.csdn.net/wyg1997/article/details/52169036

假设现在求21905内数字1的个数:
个位:它出现1的数为:1 ~ 21901,一共 2190 - 0 + 1 = 2191
十位:它出现1的数为:1x ~ 2181x (x 从0到9)一共:(218 - 0 + 1)*10 = 2190
百位:它出现1的数为:1xx ~ 211xx ,一共:(21 - 0 + 1)* 100 = 2200
千位:它出现1的数为:1xxx ~ 11xxx 和 21000 ~ 21905 ,那么很明显,这个情况就比较特殊了,为什么呢?下面再说,我们先计数,一共:(1 - 0 + 1)*1000 + (905 - 0 + 1)= 2000 + 906 = 2906
万位:它出现1的数为:1xxxx ~ 1xxxx,一共:10000

为什么计算千位的时候特殊呢?因为这个时候千位是1,那么21905中,905是确定的,而不是像之前那样任意取xxx。

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

void dfs(LL n,LL m,LL *c)
{
    LL x=n%10,y=n/10;
    for(int i=1;i<=x;i++)
        c[i]+=m; //当前位是最高位(0除外),可以得到的个数
    for(int i=0;i<=9;i++)
        c[i]+=m*y; //当前位不是最高位,前面还有y个数,所以可得到m*y个数
    LL t=y;
    while(t){ //当前位只可以是0~x,计算对高位的影响。
        c[t%10]+=(x+1)*m;
        t/=10;
    }
    if(y)dfs(y-1,m*10,c);
}
LL x[22],y[22];
int main()
{
    long long a,b;
    scanf("%lld%lld",&a,&b);
    dfs(b,1,x);
    dfs(a-1,1,y);
    for(LL i=0;i<=9;i++)
        printf("%lld\n",x[i]-y[i]);
    return 0;
}