数位DP

感觉是一种出现很多次的题然而我一次都不会（（

数位DP的核心是分情况讨论，找到一个第j位，表示第j位上数字i出现了多少次，最后将每个位数上数字i的出现次数相加即是总和。

对于一个数abcdefg，假定第j位是d，那么有如下可能：

（1）首先对于枚举的数i，如果这个数不是0，那么对于前三位abc，从0到abc，一定会有（0~999）种情况，让d为i，因此

res += l * p;

（2）对于d，我们可以分成三种情况

1.d>i d大于i这个数，则一定有一刻d等于i，则共有efg +1种情况

2.d=i d=i时，后三位可以为任意，则共有000~999种情况

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

int dgt(int n)
{
    int res = 0;
    while (n)
    {
        n /= 10;
        res++;
    }
    return res;
}

int cnt(int n, int i)
{
    int res = 0, d = dgt(n);
    for (int j = 1; j <= d; j ++ ){ // 分别枚举每一位上的数
        int p = pow(10, j - 1), l = n / p / 10, r = n % p, dj = n / p % 10;
        if (i) res += l * p;
        if (!i && l) res += (l - 1) * p;
        if ((dj > i) && (i || l)) res += p;
        if ((dj == i) && (i || l)) res += r + 1;
    }
    return res;
}

int main()
{
    int a, b;
    while (cin >> a >> b, a)
    {
        if (a > b)
            swap(a, b);
        for (int i = 0; i <= 9; i ++ )
        {
            cout << cnt(b, i) - cnt(a - 1, i) << ' ';
        }
        cout << endl;
    }

    return 0;
}