题解 P2602 【[ZJOI2010]数字计数】

· · 题解

听同机房的巨佬说，学会了数位dp就可以切掉好多好多的水紫题。

\mathbf{\boxed{\colorbox{black}{\color{white}{I was shaded. Everyone was shaded.}}}}

正题：

数位dp其实就是两个部分。初始化、求解。

初始化：

设f[i][j][k]表示第i位，最高位为j，k有多少个。

这里用到了前缀和的思想。比如f[2][1][1]就表示[0,19]有多少个1。

在求解的时候，我们就用solve(b + 1) - solve(a)。

首先我们可以得到一个粗略的方程：

这一个很玄学的数是指$k$在这一位上出现的次数。 那么在这一位上出现了多少次呢？ 如果``j <> k``，很明显，皮蛋。 那``j == k``呢？ - 比如$[10,19]$，$1$就出现了$10$次。 - $[100][199]$，$1$很明显出现了$100$次。 怎么来的？ - $10=10^1=10^{2-1}$。 - $100=10^2=10^{3-1}$。 即$f[i][j][j]+=10^{i-1}$。 代码： ```cpp void init() { for(int i = 0; i <= 9; i++) f[1][i][i] = 1; //初始化，0中有1个0，1中有1个1，...... for(int i = 2; i <= 13; i++) { //位数 for(int j = 0; j <= 9; j++) { //当前位 for(int k = 0; k <= 9; k++) { //上一位 for(int l = 0; l <= 9; l++) { //统计数 f[i][j][l] += f[i-1][k][l]; //抄方程 } } f[i][j][j] += x10(i-1); //加入10^(i-1) } } } ``` **求解：** 这个求解又被一些大佬称为“拆数”，可以递归和非递归实现。 求解过程一般有以下几步： - 首先把原数拆了，存入数组； - 统计位数比原数少，不含前导零的数字； - 统计位数与原数一样，但最高位较小的数，同样不能有前导零； - 统计一般情况。需要注意的是，如果当前位是要统计的数，结果要加$10^{i-1}$。 代码： ```cpp int solve(int x, int num) { //0~x中num出现了多少次 int digit[15]; //拆的数放这里 int len = 0, ans = 0; //数的长度、统计的结果 memset(digit, 0, sizeof(digit)); while( x ) { digit[++len] = x % 10; x /= 10; } //拆开 for(int i = 1; i < len; i++) { //统计位数比原数少，不含前导零的数字； for(int j = 1; j <=9; j++) { ans += f[i][j][num]; } } for(int i = 1; i < digit[len]; i++) { //统计位数与原数一样，但最高位较小的数，同样不能有前导零； ans += f[len][i][num]; } for(int i = len-1; i >= 1; i--) { //统计一般情况。枚举位数 for(int j = 0; j < digit[i]; j++) { //枚举这一位 ans += f[i][j][num]; //累加 } for(int j = len; j > i; j--) { //前几位需要加上的情况 if(digit[j] == num) ans += digit[i] * x10(i-1); } } return ans; } ``` **完整代码：** 注意：开``ULL``！！！不然``30pts``！！！ 蒟蒻的习惯不怎么好，马蜂清奇，用宏开``ULL`` 将就看把$QωQ 
#include<bits/stdc++.h>
#define int unsigned long long
#define x10(x) q_pow(10,x);
using namespace std;

const int MaxN = 15;
int f[MaxN][10][10];
int a,b;

int q_pow(int a, int b) {
    int res = 1;
    while(b) {
        if(b & 1) res *= a;
        b >>= 1;
        a *= a;
    }
    return res;
}

void init() {
    for(int i = 0; i <= 9; i++) f[1][i][i] = 1;
    for(int i = 2; i <= 13; i++) {
        for(int j = 0; j <= 9; j++) {
            for(int k = 0; k <= 9; k++) {
                for(int l = 0; l <= 9; l++) {
                    f[i][j][l] += f[i-1][k][l];
                }
            }
            f[i][j][j] += x10(i-1);
        }
    }
}

int solve(int x, int num) {
    int digit[15];
    int len = 0, ans = 0;
    memset(digit, 0, sizeof(digit));
    while( x ) { digit[++len] = x % 10; x /= 10; }
    for(int i = 1; i < len; i++) {
        for(int j = 1; j <=9; j++) {
            ans += f[i][j][num];
        }
    }
    for(int i = 1; i < digit[len]; i++) {
        ans += f[len][i][num];
    }
    for(int i = len-1; i >= 1; i--) {
        for(int j = 0; j < digit[i]; j++) {
            ans += f[i][j][num];
        }
        for(int j = len; j > i; j--) {
            if(digit[j] == num) ans += digit[i] * x10(i-1);
        }
    }
    return ans;
}

signed main() {
    scanf("%lld%lld", &a, &b);
    init();
    for(int i = 0; i <= 9; i++) {
        printf("%lld ", solve(b+1, i) - solve(a, i));
    }
    return 0;
}

其实这最多就一蓝题。