[动态规划](5)数位统计DP

数位统计DP

模板题:338. 计数问题 - AcWing题库

image-20210707154718146

思路:枚举每一位上 [ 0 ~ 9 ] 出现的次数,例如:

  • n = abcdefg (一个七位数) 求 在 1~n 中 1在第四位上出现的次数

    • 当 1 <= xxx1yyy <= abcdefg

      1. xxx = 000 ~ abc - 1 ,yyy = 000~999 次数 = abc * 1000
      2. xxx = abc

        1. d < 1 , abc1yyy > abc0efg,次数为0
        2. d = 1 , yyy=000~efg,次数为efg+1
        3. d > 1 , yyy = 000 ~ 999 , 次数为1000

代码:

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int get_num(int x) {//返回x的位数
    int res = 0;
    while (x) {
        res++;
        x /= 10;
    }
    return res;
}
int dp(int x,int n) {//返回x在1-n中出现的次数
    int res = 0;
    int d = get_num(n);
    for (int i = 1; i <= d; i++) {//从第一位开始枚举
        //l和r是第i位左边和右边的整数(例如n=abcdefg,i=4,则l为abc,r为efg)
        int p = pow(10,i-1);//计算第i位处于10的多少次方,用于计算abc和efg
        int l = n / p / 10, r = n % p, di = n / p % 10;

        //计算第i位左边的整数小于1(视频中xxx=000 到 abc-1)的情况
        if (x) res += l * p;
        if (!x && l)res += (l - 1) * p;//如果 x = 0,左边高位不能全为0(视频中xxx = 001 到 abc - 1)
        //计算第j位左边的整数等于1(视频中xxx = abc)的情况
        if ((di > x) && (x || l)) res += p;
        //如果当前第i位的数大于x,且x大于0或左边的abc大于0的话,方案即等于第i位位数的值
        if ((di == x) && (x || l)) res += r + 1;
        //如果当前第i位的数等于x的话,且在x与左边的整数abc不为0的情况,方案数只等于右边的数加1
    }
    return res;
}
int main() {
    int a, b;
    while (cin >> a >> b, a || b) {
        if (a > b) swap(a, b);//注意输入有可能不是按递增输入
        for (int i = 0; i <= 9; i++) 
            cout << dp(i, b) - dp(i, a - 1) << " ";
            //枚举每一位的出现次数,利用求区间和的思想计算出a-b中i出现的次数
        cout << endl;
    }

    return 0;
}

a

本文链接:

https://nullcode.fun/154.html
1 + 5 =
快来做第一个评论的人吧~