• 动态规划 --- 数位统计DP

    计数问题

    给我们两个整数 a 和 b，让我们求出来 a 和 b 之间所有数字中 0 ~ 9 出现的次数

    例如 1 ~ 12 中 1 出现的次数为 5 次，如果一个数中出现两个 1 的话要统计两次，出现三个 1 的话要统计三次，a 和 b 的范围是从 0 到 10^8，而且有多组测试数据，因此不能用暴力计算，暴力计算的最坏的时间复杂度为 10^8× 枚举每一位的时间复杂度 8，一个测试数据就已经导致超时了，而且这里有多组测试数据，因此这种暴力做法是不可取的

    接下来看一下有没有更快的算法：解决这道题目的做法中最重要的一步就是分情况讨论，我们的目标是求出来从 a 到 b 之间每个数字 0 ~ 9 出现的次数，如果直接求 a ~ b 之间出现的次数不是很好算，因此我们可以把问题转换成实现一个 count 函数，它可以求出来 x 从 1 ~ n 当中每个数字 x 出现的次数，当我们实现 count(n，x) 之后，如何求 a 到 b 之间 x 出现的次数呢？与前缀和的思想类似，从 a 到 b 之间 x 出现的次数就是 count(b，x)【1 到 b 中 x 出现的次数】 减去 count(a - 1，x)【1 到 a - 1 中 x 出现的次数】，就可以得到【从 a 到 b 中 x 出现的次数】

    当我们要求一个区间当中的答案的时候，如果不是很好计算，可以转换成：求一个前缀的答案，然后相减就可以了

    接下来的目标就是实现一个函数，这个函数的目标是：求出来从 1 到 n 当中 x 出现的次数，x 取 0 到 9

    如果我们能求出来 1 出现的次数，用类似的方式就可以求出来 2 出现的次数，下面举一个例子，以 x 等于 1 为例，看一下怎么求

    从 1 到 n 当中 1 出现的次数应该怎么求呢？

    假设当前的数字是 abcdefg，一共七位数字，我们的想法是：只要分别求出来 1 在每一位当中出现的次数累加起来就是【1 在整个 1 到 n 中出现的次数】，从第一位到第七位枚举一遍就可以了，假设现在想求 1 在第四位上出现的次数应该怎么求呢？有多少个形如 xxx1yyy 的数字在 abcdefg 之间的呢？

    这个我们只需要分情况讨论就可以了：
    ①前三位 xxx 从 000 取到 abc - 1 的话，当前位【第四位】取 1 的话，后三位 yyy 可以随便取 000 ~ 999，因为前三位已经小于 abc 了，当前位取 1 的话，后面三位随便取一定在 abcdefg 的范围内，一共有 abc × 1000 种情况

    ②第二种情况，前三位恰好等于 abc，当前位【第四位】取 1 的话，这种情况需要再次分情况讨论：

            1.如果给定的 d＜1，也就是 d 如果等于 0 的话，前三位取 abc，当前位【第四位】取 1【求第四位 1 出现的次数】，后面不管怎么取 abc1yyy 一定是大于 abc0efg，也就是说在前三位取 abc 的 情况下，只要第四位取 1，这个数就一定不在范围内，所以这种情况的方案数是 0

            2.当给定的 d 恰好等于 1 的时候，前三位取 abc，当前位【第四位】取 1【求第四位 1 出现的次数】，后四位只能取从 000 ~ efg，因为前三位是 abc，第四位是 1，也就是说前四位已经达到我们的上限了，那么我们的后三位不能超过我们的上限，只能是从 000 ~ efg，一共有 efg + 1 种情况

            3.当给定的 d 大于 1 的时候，前三位取 abc，第四位取 1【求第四位 1 出现的次数】，范围的上限是 abcdefg，d 是大于 1 的，前四位取 abc1，由于 d 是大于 1 的，所以说后三位可以取任意值，从 000 ~ 999 都可以取，一定是在这个范围内的，一定是小于 abcdefg 的，一共有 1000 种情况

    这样所有的情况都枚举完了，前三位只有两种情况：000 ~ abc - 1 或者取 abc，前三位不可能大于 abc，如果大于 abc 的话就超过了 abcdefg 的范围

    把以上所有的情况加到一块，就是 1 出现在第四位上的次数，总共的方案数就是 abc × 1000，然后看一下是哪种情况，是哪种情况就把第二种情况的方案数加上就可以了。通过这种方式，就可以求出来 1 在任意一位上出现的次数，求出 1 在每一位上出现的次数，累加起来就可以得到 1 在 1 ~ n 当中整个出现的次数了。循环一下其他数，用同样的方式就可以求出来 2 出现的次数、3 出现的次数，. . . 从 0 ~ 9 之间每一个数出现的次数，求完 1 ~ n 出现的次数之后，就可以用类似前缀和的思想，求出来从 a 到 b 当中每个数出现的次数了

    时间复杂度非常低，首先枚举每一个数字 10 × 2(算两次，两个区间分别算一次) × 8(每次算的时候分别枚举一下每一位 8位) × 10(循环每一位abc、efg) = 1600

    讨论边界情况

    ①当我们枚举的这个数字出现在最高位的时候，也就是枚举 1 出现在第一位的时候，第一种情况是不存在的，只需要计算第二种情况就可以了

    ②当我们枚举数字 0 的时候，例如我们枚举数字 0 出现在第四位的时候，那么在第一种情况里面，前三位不能从 000 取到 abc - 1，数字不能有前导 0，前三位是 000，当前位也取 0，意味着前四位有四个 0 属于不合法的情况，如果出现这样的情况，需要把前四位删掉。由此，我们思考一下：第一种情况应该是从哪个数取到 abc - 1 呢？前三位是从 100 开始取呢还是从 001 开始取呢？

    首先暴力统计 1 到 n 当中 x 出现的次数

    1. #include 
    2.  
    3. using namespace std;
    4.  
    5. //统计1到n当中x出现的次数
    6. int force_count(int n, int x)
    7. {
    8.     //res表示答案
    9.     int res = 0;
    10.     //从1到n枚举n的每一位
    11.     for(int i = 1;i <= n;i++ )
    12.     {
    13.         for(int j = i; j;j /= 10)
    14.             if(j % 10 == x)
    15.                 res ++;
    16.     }
    17.     return res;
    18. }
    19.  
    20. int main()
    21. {
    22.     cout << force_count(111, 0);
    23. }
    24. 21

    从 1 ~ 111 以内个位出现 0 的次数个数一共有 11 种选法，百位可以取 1，十位取 0，个位从 0 ~ 9 一共 10 种选法，总计 11 + 10 = 21 种选法

        1         2         3         4         5         6         7         8         9        10
      11       12       13       14       15       16       17       18       19        20
      21       22       23       24       25       26       27       28       29        30
      31       32       33       34       35       36       37       38       39        40
      41       42       43       44       45       46       47       48       49        50
      51       52       53       54       55       56       57       58       59        60
      61       62       63       64       65       66       67       68       69        70
      71       72       73       74       75       76       77       78       79        80
      81       82       83       84       85       86       87       88       89        90
      91       92       93       94       95       96       97       98       99      100
    101     102     103     104     105     106     107     108     109      110
    111

    接下来重点把 x = 0 的求法解决一下：

    n = abcdefg，枚举某一位是 0 的情况，例如枚举 d 这一位是 0 的时候，注意前导 0 的情况，如果枚举 d 等于 0 的话，那么 a、b、c 不能取 0，如果 d 取 0，a、b、c 也取 0，例如 000123 并不是一个合法的表示，前面四个 0 是不会写出来的，所以前面枚举的时候只能从 001 开始枚举

    ①第一种情况是从 001 ~ abc - 1，d 取 0，后面三位可以取 000 ~ 999

    ②第二种情况是前面这几位等于 abc 的时候，d 取 0，当然这种情况在首位是不存在的，0 一定不会出现在最高位，当 x 等于 0 的时候，从 n - 2 开始循环

    当读入一行为 0 的时候，表示输入终止，且该行不作处理

    注意 vector 的尾插，枚举的时候需要从最高位开始枚举 当 x = 0 的时候从次高位开始枚举

    1. #include 
    2. #include 
    3.  
    4. using namespace std;
    5.  
    6. int main()
    7. {
    8.     vector<int> num;
    9.     int n = 12345;
    10.     while (n)
    11.     {
    12.         num.push_back(n % 10);
    13.         cout << n % 10;
    14.         n /= 10;
    15.     }   
    16. }
    17. 54321
    18.  
    19. int main()
    20. {
    21.     vector<int> num;
    22.     int n = 12345;
    23.     while (n)
    24.     {
    25.         num.push_back(n % 10);
    26.         n /= 10;
    27.     }
    28.     n = num.size();
    29.     for (int i = 0; i < n; i++)
    30.     {
    31.         cout << num[i];
    32.     }
    33.  
    34. }
    35. 54321
    36.  
    37. int main()
    38. {
    39.     vector<int> num;
    40.     int n = 12345;
    41.     while (n)
    42.     {
    43.         num.push_back(n % 10);
    44.         n /= 10;
    45.     }
    46.     n = num.size();
    47.     for (int i = n - 1; i >= 0; i--)
    48.     {
    49.         cout << i;
    50.     }
    51. }
    52. [4][3][2][1][0]
    53.  
    54. int main()
    55. {
    56.     vector<int> num;
    57.     int n = 12345;
    58.     while (n)
    59.     {
    60.         num.push_back(n % 10);
    61.         n /= 10;
    62.     }
    63.     n = num.size();
    64.     for (int i = n - 1; i >= 0; i--)
    65.     {
    66.         cout << num[i];
    67.     }
    68. }
    69. 12345

    求前面这些位构成的数字是多少，从第 l 位求到第 r 位，从高位到低位 

    1. #include 
    2. #include 
    3.  
    4. using namespace std;
    5.  
    6. int get(vector<int> num, int l, int r)
    7. {
    8.     //存储结果
    9.     int res = 0;
    10.     //i从l开始
    11.     for (int i = l; i >= r; i--)
    12.         res = res * 10 + num[i];
    13.     return res;
    14. }
    15. int main()
    16. {
    17.     vector<int> num;
    18.     int n = 12345;
    19.     while (n)
    20.     {
    21.         num.push_back(n % 10);
    22.         n /= 10;
    23.     }
    24.     cout << get(num, 4, 0);
    25. }
    26. 12345
    1. #include 
    2. #include 
    3. #include 
    4. using namespace std;
    5.  
    6. //求前面这些位构成的数字是多少 从第l位求到第r位 从高位到低位
    7. int get(vector<int> num, int l,int r)
    8. {
    9.     //存储结果
    10.     int res = 0;
    11.     //i从l开始
    12.     for(int i = l;i >= r;i-- )
    13.         res = res * 10 + num[i];
    14.     return res;
    15. }
    16. //求10的i次方
    17. int power10(int x)
    18. {
    19.     int res = 1;
    20.     while(x-- ) res *= 10;
    21.     return res;
    22. }
    23.  
    24. //实现count函数 从1到n当中统计x出现的次数
    25. int count(int n, int x)
    26. {
    27.     //边界->由于统计的是从1到n当中每个数出现的次数,当n等于0的时候一个数都没有直接返回0就可以了 
    28.     if(!n) return 0;
    29.  
    30.     vector<int> num;
    31.     //把n的每一位扣出来
    32.     while(n)
    33.     {
    34.         num.push_back(n % 10);
    35.         n /= 10;
    36.     }
    37.     //让n等于num的位数
    38.     n = num.size(); 
    39.     //res表示答案 也就是总共出现的次数
    40.     int res = 0;
    41.     
    42.     //枚举的时候从最高位开始枚举 当 x = 0 的时候从次高位开始枚举
    43.     for(int i = n - 1 - !x;i >= 0;i-- )
    44.     {
    45.         //特判:枚举最高位的时候这一类其实是不存在的,只有当i
    46.         if(i < n - 1)
    47.         {    
    48.             //从n-1到i+1也就是当前枚举的这一位->第i位前面这些位构成的数字abc乘上10^i
    49.             res += get(num, n - 1, i + 1) * power10(i);
    50.             //特判:当x=0的时候 需要从001开始枚举 (get(num, n - 1, i + 1) - 1)* power10(i)
    51.             if(!x) res -= power10(i);
    52.         }
    53.         //d
    54.         if(num[i] == x) res += get(num, i - 1, 0) + 1;
    55.         //否则num[i]>x的话 加上的应该是10^i
    56.         else if(num[i] > x) res += power10(i);
    57.     }
    58.     return res;
    59. }
    60.  
    61. int main()
    62. {
    63.     //定义a、b,输入a、b,如果读入一行为0 0表示输入终止
    64.     while(cin >> a >> b, a || b)
    65.     {
    66.         //a、b不一定是小数在前 需要先交换一下
    67.         if(a > b) swap(a, b);
    68.         //统计每个数出现的次数
    69.         for(int i = 0;i < 10;i++ )
    70.             //1~b中i出现的次数减去1~a-1中i出现的次数
    71.             cout << count(b, i) - count(a - 1, i) << ' ';
    72.         cout << endl;
    73.     }
    74.     return 0;
    75. }
  • 相关阅读:
    【STM32笔记】HAL库定时器捕获配置、操作及通用函数定义
    MyBatis-Plus
    如何处理前端响应式图片？
    YOLOv5算法改进（11）— 在C3模块中添加注意力机制（包括代码+添加步骤+网络结构图）
    多御安全浏览器锁屏功能上线，详解设置浏览器锁屏的方法
    代码行统计工具---cloc（Count Lines of Code）
    【手把手反内卷】开创全新AI多模态任务一视听分割：代码实践、优化教程（二）
    hiredis笔记
    深入理解联邦学习——联邦学习与现有理论的区别与联系
    Bytebase 2023 第三季度回顾
  • 原文地址：https://blog.csdn.net/weixin_60569662/article/details/126010114