【数位DP】数字统计

题目

给定两个正整数a和b，求在[a,b]中的所有整数中，每个数码(digit)各出现了多少次。

数位DP

（1）分情况，逐位讨论。

（2）模型：计算在[L,R]中有多少个数满足条件。

（3）套路：将问题转化为[1,R]-[1,L-1]，只需回答[1,X]的询问即可。

思路

1.算出[1,X]：

（1）按位拆分，为后面做铺垫

（2）预处理：

	 1）pow[]表示10的次幂

	 2）f[]表示：后i位自由的话每个数字出现的次数

ps:有一个规律。0~9每个数字出现1次，10~99出现20次，100~999出现300次。出现次数为：n*10^(n-1)(n为位数）

（3）处理比X少一位的情况

 从0~9共10个数。同位数计算10次，加上pow[i-1]即可。

（4）处理全部位数

	从最高位到最低位。比如ABCDE，A会出现BCDE+1次，以此类推。

2.将第一遍算出的答案全部*(-1)，就相当于减去。

#include<iostream>

using namespace std;

long long ans[10],f[20],pow[20];

int p[20],l;

void deal(long long x, long long y){ // 统计固定位是x，自由位有y个的情况

    for(long long i=0;i<10;i++) ans[i]+=f[y]; // 算后面的

    for(long long p=x;p;p/=10) ans[p%10]+=pow[y]; // 算前面的

}

void calc(long long x){

    if(!x) return;

    l=0,pow[0]=1;

    for(long long tp=x;tp;tp/=10) p[++l]=tp%10; // 一位一位拆分

    for(int i=1;i<=l;i++) pow[i]=pow[i-1]*10; // 10的次幂

    for(int i=1;i<=l;i++) f[i]=pow[i-1]*i; // 后i位是自由的话，每个数字出现多少次

    // 处理比l小位数的情况

    for(int i=1;i<l;i++) // 枚举，当前是i位数

        for(int k=1;k<10;k++) deal(k,i-1); // 枚举这个i位数，是以k开头的

    // 处理l位数的情况

    // i : 当前算到哪个位置

    // lst : 当前前面的数是多少

    // st,en : 数字的枚举范围

    for(long long i=l,lst=0,st,en;i;lst+=p[i--]){

        st=(i==l)? 1:0;//如果i==l，则这是最高位，不能是0

        en=(i==1)? p[i]:p[i]-1;//

        lst *= 10;

        for(int k = st; k <= en;k++) deal(lst+k, i-1);

    }

}

int main(){

    long long a,b;

    cin>>a>>b;

    calc(a-1);

    for(int i=0;i<10;i++) ans[i]*=-1;

    calc(b);

    for(int i=0;i<10;i++) cout<<ans[i]<<" ";

    return 0;

}

欢迎指正评论O(∩_∩)O~~

巴特西

【数位DP】数字统计

最新文章

热门文章