数位统计DP

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

#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;
}