’‘’
/

数位DP：核心是分类讨论

给定两个整数 a 和 b，求 a 和 b 之间的所有数字中 0∼9 的出现次数。
1—n
例
* 若n=abcdefg
*
* 求1出现在第四位的个数
* 分情况讨论
*
* 1<=xxx1yyy<=abcdefg
* (1) xxx=001—abc-1， yyy=000—999 即abc1000种
* (2) xxx=abc
* (2.1) d<1 abc1yyy>abc0efg 0种
* (2.2) d=1 yyy=000—efg efg+1 种
* (2.3) d>1 yyy=000—999 1000种
*

实现函数 dpcount(n,x) 表示1—n种x出现的次数
则从a—b的x出现的次数= dpcount(b,x)-dpcount(a-1,x) 前缀和思想

*/

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

int get(vector[HTML_REMOVED] num, int l, int r) //获取位数
{
int res = 0;
for (int i = l; i >= r; i–)
{
res = res * 10 + num[i];
}
return res;
}

int power10(int x)
{
int res = 1;
while (x–)res *= 10;
return res;
}

int dpcount(int n, int x)
{
if (!n) return 0;
vector[HTML_REMOVED]num;
while (n)
{
num.push_back(n % 10);
n /= 10;
}
n = num.size();

int res = 0;
for (int i = n - 1-!x; i >= 0; i--)
{
    if (i < n - 1)
    {
        res += get(num, n - 1, i + 1) * power10(i);
        if(!x) res-=power10(i);
    }
    if (num[i] == x) res += get(num, i - 1, 0)+1;
    else if (num[i] > x) res += power10(i);
}
return res;

}

int main()
{
int a, b;
while (cin >> a >> b, a || b)
{
if (a > b)swap(a, b);
for (int i = 0; i < 10; i++)
cout << dpcount(b, i) - dpcount(a - 1, i) << ” “;
cout << endl;
}
return 0;
}
‘’‘