POJ 3286 How many 0's?(数位dp)

** 题目链接 ** : POJ 3286 How many 0’s?

题意

输入n,m,求n~m范围内的所有数字中,0出现的总数是多少。

思路

用2034做个例子。
枚举0在个十百千位上出现的次数
个:个位为0时,后面不需要考虑,只需考虑前面,因为0比4小,所以前面即使取到最大也不会过限,所以前面可以是1~203(因为当前位是0,所以前面不能是0)。一
共203种。
十:十位为0时,前面取1~20,后面取0~9。一共123*10种。
百:百位为0时,因为0与当前位上限0相等,所以前面取1时,后面可以取0~99,前面取2时,后面只能取0~34。一共1*100+35种。
千位显然不能为0,所以总数为0。
把上述思想转化为代码即可。

代码

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

using namespace std;

const int N = 10009;
#define LL long long
LL p[20];

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

LL solve(LL x)
{
    if(x == -1)
        return -1;
    LL ans = 0;
    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 += l*p[i-1];
        else
            ans += (l-1)*p[i-1] + r+1;
        if(p[i] > x)
            break;
    }
    return ans;
}

int main()
{
    LL n, m;
    init();
    while(cin>>n>>m && (n!=-1 || m!=-1))
        printf("%lld\n", solve(m) - solve(n-1));
    return 0;
}