5.数位统计DP

AcWing 338. 计数问题

实现思路：

  • 定义函数：count(n,x)，其表示在1到n中，x出现的次数（x是0-9）

    那么，可以用类似前缀和的思想，来求解a到b中，x出现的次数：count(b,x) - count(a-1,x)

  • 以x = 1为例，如何计算count(n, 1)：分情况讨论。比如n是个7位的数字 abcdefg，我们可以分别求出1在每一位上出现的次数，然后做一个累加即可。比如求1在第4位上出现的次数，求有多少个形如xxx1yyy的数在1到abcdefg之间。分两种大情况

    • xxx = 000 ~ abc - 1, 中间d=1，yyy = 000 ~ 999，一共有abc * 1000(即左右两边数的大小相乘)种选法
    • 若xxx = abc
      1. d < 1，abc1yyy > adc0efg，超出n的范围，0种
      2. d = 1，yyy = 000 ~ efg，efg + 1种
      3. d > 1，yyy = 000 ~ 999，1000种

  • 把上面全部的情况，累加起来，就是1出现在第四位的次数。

    类似的，可以求解出1在任意一个位置上出现的次数，累加起来，就求出了1在每一位上出现的此时，即求解出了count(n,1)。

  • 注意：当x=0时，不能有前导0，所以当x=0时，形如xxx0yyy，前面的xxx是从001(不能从00开始，左边选法相比不是0的情况就少了一次)到999

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
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

//求n的位数
int get(int  n){
    int res=0;
    while(n) res++,n/10;
    return res;
}

//求从1到n中i出现的次数
int count(int n,int i){
    int res=0,dgt=get(n);
    
    //遍历每一位 求出每一位出现i的次数
    for(int j=1;j<=dgt;j++){
        /*利用位运算
        得到当前遍历位次(第j位)的数的大小p：10^(j右边的位数即dgt-j)
        得到第j位左边的数大小l
        得到第j位右边的数大小r
        得到第j位上的数dj
        */
        int p=pow(10,dgt-j),l=n/p/10,r=n%p,dj=n/p%10;
        
        //然后分情况讨论 用i所在的位置划分出左边、右边
        /* 一、xxx..i..yyy的选法 左边取小于n中实际的左边的数l
        1)当i不为0时：左边000...~xxx...-1，右边...yyy就任意取了，取法：左边的数大小l*10^右边位数=l*p
        2)当i=0时，排除前导0的情况：左边000..1~xxx...-1，右边和上面一样，取法:(l-1)*p
        */
        if(i) res+=l*p;
        else res+=(l-1)*p;
        
        /* 二、左边固定为n的左边的数l
         1)、i > dj时 0种选法
         2)、i == dj时 yyy : 0...0 ~ r 即 r + 1 种选法
         3)、i < dj时 yyy : 0...0 ~ 9...9 即 10^(右边的数的位数) == p 种选法
        */
        if(i==dj) res+=r+1;
        if(i<dj) res+=p;
    }
    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;
}

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。