BZOJ 1833 [ZJOI2010]count 數字計數(數位dp)

題意

輸入n,m，求n～m范圍內的所有數字中，分別輸出0～9出現的總數是多少。

思路

和 POJ 3286 How many 0’s? (數位dp)的思路基本是一樣的，只是略有區別。
0和1～9要分開處理，是因為前綴0的問題。因為當某一位取0時，前面部分的數是不能為0的，而取1～9是可以前面為0的。

代碼

<code class="hljs perl">#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;
}</map></cmath></vector></cstdlib></cstdio></cstring></algorithm></iostream></code>