51nod 1042 数字0-9的数量 （数位dp）

Description

给出一段区间 a-b ，统计这个区间内 0-9 出现的次数。

比如 10-19，1 出现 11 次（10, 11, 12, 13, 14, 15, 16, 17, 18, 19，其中 11 包括 2 个 1 )，其余数字各出现 1 次。

Input

两个数 a,b（1 <= a <= b <= 10^18)

Output

输出共 10 行，分别是 0-9 出现的次数

Input示例

10 19

Output示例

1
11
1
1
1
1
1
1
1
1

思路

很容易想到该题的结论满足区间减法，于是我们只需要分别计算 $[0,a-1]$ 以及 $[0,b]$ 的结果，相减既是答案。

我们考虑从一个数 $x$ 的低位往高位开始枚举，对于第 $k$ 位我们分情况进行讨论。

假设 $x=12345$ ，$k$ 指向数字 $3$ 的位置，则此时 $pre = 12, after=45,tmp=100$ 。

我们枚举 $i$ 从 $0-9$：

• 当前数字小于 $i$ ，即 $i\in[4,9]$ ，此时高位的变化范围可以是 $[0,11]$ ，共 $pre \times tmp$ 种方案
• 当前数字大于 $i$ ，即 $i\in[0,2]$ ，此时高位的变化范围可以是 $[0,12]$ ，共 $(pre+1)\times tmp$ 种方案
• 当前数字等于 $i$ ，即 $i=3$ ，此时高位的变化范围可以是 $[0,12]$ ，当且仅当高位等于 $12$ 时低位最多取到 $45$ ，因此共有 $pre \times tmp + after + 1$ 种方案

特殊的当 $i=0$ 时且高位为 $0$ 时，显然这种情况是不允许的，因此我们需要减去一个 $tmp$ 。

AC 代码

#include <bits/stdc++.h>
#define IO                       \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 10;

LL ans[10];
void solve(LL n, int sign) {
    LL cur, pre, after, tmp = 1, tn = n;
    while (n) {
        cur = n % 10;
        pre = n / 10;
        after = tn - n * tmp;
        for (int i = 0; i < 10; i++) {
            if (cur > i)
                ans[i] += (pre + 1) * tmp * sign;
            else if (cur < i)
                ans[i] += pre * tmp * sign;
            else
                ans[i] += (pre * tmp + after + 1) * sign;
        }
        ans[0] -= tmp * sign;
        tmp *= 10;
        n /= 10;
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#else
    IO;
#endif // ONLINE_JUDGE
    LL l, r;
    cin >> l >> r;
    solve(l - 1, -1);
    solve(r, 1);
    for (int i = 0; i < 10; i++) {
        cout << ans[i] << endl;
    }
    return 0;
}