【数位dp】bzoj1833: [ZJOI2010]count 数字计数

数位dp姿势一直很差啊；顺便庆祝一下1A

Description

给定两个正整数a和b，求在[a,b]中的所有整数中，每个数码(digit)各出现了多少次。

Input

输入文件中仅包含一行两个整数a、b，含义如上所述。

Output

输出文件中包含一行10个整数，分别表示0-9在[a,b]中出现了多少次。

Sample Input

1 99

Sample Output

9 20 20 20 20 20 20 20 20 20

HINT

30%的数据中，a<=b<=10^6；
100%的数据中，a<=b<=10^12。

题目分析

数位dp经典入门题

说到底，数位dp快就快在按位计算答案，而不是按数计算答案。

这个有些抽象，所以还是看代码吧。

 #include<bits/stdc++.h>

 typedef long long ll;

 ll a,b,ans[];

 ll digit[];

 ll base[];

 ll read()

 {

     char ch = getchar();

     ll num = ;

     bool fl = ;

     for (; !isdigit(ch); ch = getchar())

         if (ch=='-') fl = ;

     for (; isdigit(ch); ch = getchar())

         num = (num<<)+(num<<)+ch-;

     if (fl) num = -num;

     return num;

 }

 void work(ll num, ll c)

 {

     for (digit[]=; num; num/=)

         digit[++digit[]] = num%;

     for (int i=digit[]; i; i--)

     {

         for (int j=digit[]; j>i; j--)

             ans[digit[j]] += c*(digit[i]*base[i]);

         for (int j=; j<digit[i]; j++)

         {

             for (int k=; k<=; k++)

                 ans[k] += c*base[i-]*(i-);

             ans[j] += c*(base[i]);

         }

         if (i==digit[]){

             ans[] -= c*digit[];

             for (int j=; j<digit[]; j++)

                 ans[] -= c*j*base[digit[]-j]*;

         }

     }

 }

 int main()

 {

     base[] = ;

     for (int i=; i<=; i++) base[i] = base[i-]*10ll;

     a = read(), b = read()+;

     work(a, -);

     work(b, );

     for (int i=; i<=; i++)

         printf("%lld ",ans[i]);

     return ;

 }

END

巴特西