BZOJ 1833 [ZJOI2010]count 数字计数(数位dp)

题目链接：[kuangbin带你飞]专题十五 数位DP D - Bomb

题意

输入n,m，求n～m范围内的所有数字中，分别输出0～9出现的总数是多少。

思路

和 POJ 3286 How many 0’s? (数位dp)的思路基本是一样的，只是略有区别。
0和1～9要分开处理，是因为前缀0的问题。因为当某一位取0时，前面部分的数是不能为0的，而取1～9是可以前面为0的。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cmath>
#include <map>

using namespace std;

#define LL long long
LL p[20];
LL ans[10] = {};

void init()
{
    p[0] = 1;
    for(int i=1; i<18; i++)
        p[i] = p[i-1]*10;
}

void solve(LL x, int f)
{
    if(x == -1)
    {
        ans[0]++;
        return;
    }
    for(int k=1; k<10; k++)
    {
        for(int i=1; ; i++)
        {
            LL l = x/p[i];
            LL r = x%p[i-1];
            LL now = x%p[i]/p[i-1];
            if(now > k)
                ans[k] += (l+1)*p[i-1]*f;
            else if(now == k)
                ans[k] += (l*p[i-1]+r+1)*f;
            else
                ans[k] += l*p[i-1]*f;
            if(p[i] > x)
                break;
        }
    }
    for(int i=1; ; i++)
    {
        LL l = x/p[i];
        LL r = x%p[i-1];
        LL now = x%p[i]/p[i-1];
        if(now > 0)
            ans[0] += l*p[i-1]*f;
        else
            ans[0] += ((l-1)*p[i-1]+r+1)*f;
        if(p[i] > x)
            break;
    }
}

int main()
{
    LL n, m;
    init();
    cin>>n>>m;
    solve(m, 1);
    solve(n-1, -1);
    for(int i=0; i<9; i++)
        printf("%lld ", ans[i]);
    printf("%lld\n", ans[9]);
    return 0;
}