[AcWing] 338. 计数问题 （C++实现）数位统计dp例题

[AcWing] 338. 计数问题 （C++实现）数位统计dp例题

[AcWing] 338. 计数问题 （C++实现）数位统计dp例题

• 1. 题目
• 2. 读题（需要重点注意的东西）
• 3. 解法
• 4. 可能有帮助的前置习题
• 5. 所用到的数据结构与算法思想
• 6. 总结

1. 题目

2. 读题（需要重点注意的东西）

思路：
本题思路不难，主要还是需要分情况讨论清楚，此外，代码实现有边界情况，将思路转换成代码有点复杂。
主要的思路如下：
1、首先计数得分为计0的数和计除0外的其他数两种情况；
2、再而，又得针对前三位的取法分为恰好① 取abc和② 取abc-1 ~ 001（计0时）or000 （计除0外的数）

具体的分类情况如下图所示：

3. 解法

---------------------------------------------------解法---------------------------------------------------

#include 
#include 
#include 

using namespace std;

const int N = 10;



// 获取num中以l开头，r结尾组成的数是多少，就是求思路中的“abc”
int get(vector num, int l, int r)
{
    int res = 0;
    for (int i = l; i >= r; i -- ) res = res * 10 + num[i];
    return res;
}

// 求10的x次方
int power10(int x)
{
    int res = 1;
    while (x -- ) res *= 10;
    return res;
}

// count函数用于计数 1 ~ n 中，x出现的次数
int count(int n, int x)
{
    if (!n) return 0; // 如果n为0，返回0；因为我们统计的是从1~n中每个数出现的次数（注意数据范围取不到0的）

    // num数组用于存储每一位上的数是多少（注意是倒着的，因此在下面for循环时，也是倒着遍历的）
    vector num; 
    // 如 n = 12345
    // 则 num = {5,4,3,2,1}
    while (n)
    {
        num.push_back(n % 10);
        n /= 10;
    }
    // n此时表示原来n有多少位，然后用于计算i在每一位上的数有多少个
    n = num.size();
    
    // 计算i在每一位上的数有多少个
    int res = 0;
    // - !x的作用是，当x = 0时，要统计0在每一位上的数的个数，因为0不能在首位，所以此时 - !x = -1 ，即从第二位开始枚举
    for (int i = n - 1 - !x; i >= 0; i -- )
    {
        // ---------------------------第 ① 种情况---------------------------
        if (i < n - 1) // 枚举到最高位时，第①种情况是不存在的，因此需要i < n - 1特判一下
        {
            res += get(num, n - 1, i + 1) * power10(i); 
            if (!x) res -= power10(i); // 如果 x == 0,要减去在首位的计数
        }
        // ---------------------------第 ② 种情况---------------------------
        // ② 中 第 Ⅰ 种情况，为0，不用写
        if (num[i] == x) res += get(num, i - 1, 0) + 1; // 即 ② 中的第 Ⅱ 种情况 (d = x)
        else if (num[i] > x) res += power10(i); // 即 ② 中的第 Ⅲ 种情况  （d > x）
    }

    return res;
}

int main()
{
    int a, b;
    while (cin >> a >> b , a)
    {
        if (a > b) swap(a, b); // 保证 b 是始终大于 a 的（因为题目中输入的第一个数 a 有可能大于第二个数 b ）

        // 计算的是b和a中i出现的次数
        // 要求的是b到a之间的数的数，因此采用前缀和的思想，用b的计数-a的计数
        for (int i = 0; i <= 9; i ++ )
            cout << count(b, i) - count(a - 1, i) << ' ';
        cout << endl;
    }

    return 0;
}

---

可能存在的问题

4. 可能有帮助的前置习题 5. 所用到的数据结构与算法思想

• 动态规划
• 数位统计dp

6. 总结

线性dp的例题，理解思想并自行推导出代码。