「BZOJ 1833」「ZJOI2010」count 数字计数

Description

给定两个正整数 $l,r\ (1 \leq l \leq r \leq 10^{12})$，求区间 $[l,r]$ 里的所有整数中，每个数码 $0 \sim 9$ 各出现了几次。

Source

[BZOJ]1833

Solution

考虑 数位DP 。

用 $f_{pos,cnt}$ 表示当前到了第 $len - pos + 1$ 位，有 $cnt$ 个数码 $digit$ 的数中，共有多少个数码 $digit$ 。

分别计算 $0 \sim 9$ 每一个数码，注意判前导零（前导零不算数码 $0$），具体实现详见代码。时间复杂度为 $O(10\lg^2n)$ 。

Code

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

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
	int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 12;
LL l, r, f[MAXN + 5][MAXN + 5];

LL dfs(int *num, int pos, LL cnt, int digit, bool lead, bool lim) {
    //pos 表示当前是第 len - pos + 1 位，cnt 表示前 len - pos + 1 位中数码 digit 的数量， 
    //digit 表示当前要求的数码，lead 表示是否有前导零，lim 表示当前数位是否受到限制 
    if (!pos) return cnt;//若搜完最后一位，则返回数码数量 
    if (!lead && !lim && ~f[pos][cnt]) return f[pos][cnt];//返回已记录的值
    LL res = 0;
    int maxNum = lim ? num[pos] : 9;//当前数位最大值 
    for (int i = 0; i <= maxNum; ++i)
        res += dfs(num, pos - 1, cnt + ((i == digit) && !(lead && !i)), digit, lead && !i, lim && i == maxNum);
    //查找下一位。如果第 i 位的数码是所要求的数码，且该数码不是前导零，那么统计数量 + 1
    if (!lead && !lim) f[pos][cnt] = res;//记录该状态的值  
    return res;
}

inline LL solve(LL x, int digit) {
    if (x < 0) return 0;//l = 0 时 x = -1，特判 
    int len = 0, num[MAXN + 5];
    for (; x; x /= 10) num[++len] = x % 10;
    memset(f, -1, sizeof (f));//初始化 
    return dfs(num, len, 0, digit, 1, 1);//注意第一位算 有前导零 且 数位受限制 
}

int main() {
    read(l), read(r);
    for (int i = 0; i <= 9; ++i) {
        write(solve(r, i) - solve(l - 1, i));
        putchar(' ');
    }
    putchar('\n');
    return 0;
}