数位统计DP

文章目录

前言

一、动态规划

二、AcWing 338. 计数问题

本题解析

AC代码

三、时间复杂度

前言

复习acwing算法基础课的内容，本篇为讲解基础算法：动态规划——数位统计DP，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上。

一、动态规划

动态规划（Dynamic Programming，DP）是求解决策过程最优化的过程，个人认为是目前接触的所有算法里最绕的…

这里的题目的解题方法来自于：y总的闫氏dp分析法

二、AcWing 338. 计数问题

本题链接：AcWing 338. 计数问题

本博客提供本题截图：

本题解析

介绍一下代码中出现的函数的用途：

int count(int n, int x)：返回在1 ~ n中x出现的次数

int get(vector<int> num, int l, int r)：返回num数组中从r位到l位的数是多少

int power10(int x)：返回10的x次方

下面来看分析过程：

如何求a ~ b 中i出现的次数：利用前缀和的思路，即count(b, i) - count(a - 1, i)

下面开始说明如何实现count函数：

假设我们需要去求 1 ~ n中，1出现的次数，n = abcdefg

我们的思路为：分别求出1在每一位上出现的次数，那么这里我们假设求出1在第四位上出现的次数，即1 <= xxx1yyy <= abcdefg

按照两个总方向去分析：

(1) xxx = 000 ~ abc - 1：对于这种情况的话yyy的取值为：000 ~ 999，故这种的总情况数为：abc * 1000

(2) xxx = abc：

                (2.1) d < 1，那么abc1yyy > abc0efg，故这种没有符合情况的数

                (2.2) d = 1，yyy的取值可为000 ~ efg，故这种的总情况数为：efg + 1

               (2.3) d > 1，yyy的取值可为000 ~ 999，故这种的总情况数为：1000

下面开始 特判：

上述例子中，我们用的是1去举例，那么我们接下来去考虑最特殊的数字：0

0不会影响上述count函数实现中的 (2) 部分，只会对 (1) 部分产生影响：因为不可以出现形如0123这种数字

还是上述案例，我们对于 (1) xxx的取值范应为001 ~ abc - 1，这样做就可以防止出现前导0，我们在依次遍历每一位上0出现的个数的时候，因为首位不能为0，故for循环可以写成：for (int i = n - 1 - !x; i >= 0; i -- )

AC代码

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 10;
int get(vector<int> 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 count(int n, int x)
{
    if (!n) return 0;
    vector<int> 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);       //对 0 的特判，即减去 001 的那一种情况
        }
        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)
    {
        if (a > b) swap(a, b);    //题目中数据比较狗，可能出现 a > b 的情况，故需要特判一下
        for (int i = 0; i <= 9; i ++ )
            cout << count(b, i) - count(a - 1, i) << ' ';
        cout << endl;
    }
    return 0;
}

三、时间复杂度

关于动态规划——数位统计DP的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。