欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

C++数位DP复杂度统计数字问题示例详解

程序员文章站 2022-04-30 11:21:44
目录一、问题描述:二、问题分析:1. 抽取题意:2. 初步思考:3. 示例分析:4. 总结规律:5. 解除约定:三、 编写代码:四、 相关例题:tips:如果你是真的不理解,不要只看,拿出笔来跟着步骤...

tips:如果你是真的不理解,不要只看,拿出笔来跟着步骤自己分析。

一、问题描述:

一本书的页码从自然数 1 开始顺序编码直到自然数 n 。书的页码按照通常的习惯编排, 每个页码不含多余的前导数字 0。 例如, 第 6 页用数字 6 表示而不是 06 或 006等。 数字计数问题要求对给定书的总页码 n,计算书的全部页码分别用到多少次数字 0、 1、... 、9。

二、问题分析:

1. 抽取题意:

简单来说就是就是给定一个数字 n,统计 1~n 中用到了多少次数字0~9。

2. 初步思考:

很容易想到要分数位(如个位、十位、百位)来考虑。

为了方便思考,我们做一些约定:

从 0 开始考虑,即考虑0~n中用到了多少次数字0~9,同时计算前导0。

用一个长度为10的数组ans[10] 来存储各个数字的数量。

从最低位开始分析还是最高位开始分析?

应该从最高位开始分析。为什么不先从个位开始考虑呢?因为数字在有除个位外高位(如十位、百位)的情况下,低位是作用于高位的,低位是高位的补充。在这个问题中,单纯的低位并不能说明什么。

3. 示例分析:

① 对于一位数 d 来说,0~d 中用到的数字个数即 0~d 各一次。

② 对于两位数 cd 来说,我们先考虑c,即c0,先不管c有多大,当c可以为0时,有00,01, 02, ... , 09 这样的数字,则我们知道,c在为0的时候个位0~9的数字各用了一次,同时c本身被用到了10次;当c为1时,有这样的数字10,11,12, ..., 19 ,我们知道 c 为1的时候个位0~9的数字各用了一次,同时c 被用了10次。

以此类推我们知道,c每大一,个位数字0~9就都会被用到1 次。并且本身作为十位的c,c每大一,当前c表示的数字就会被用到10次。

注意此时c不能为最大值,因为c为最大值的话按照上述方法考虑,可能超过cd本来的值。

再来考虑d,

当c为最大值的时候,用到的数字即c0,c1,...,cd ,由此我们知道c为最大值时c会被用d+1次,0~d各用了一次。

经过总结得到,在考虑前导0的情况下,一个十位数字cd 0~9的数字用到的情况如下:

考虑十位得到的 
ans [ 0~9 ] + 1*c  (虽然此时不能考虑十位最大值,但是有0啊) 
ans [ 0~c-1 ] + 10^1   
ans [c] + (d+1)  (此时十位取最大值)
 
考虑个位得到的
ans[ 0~d ] + 1

③ 有了上面的经验,我们来考虑三位数 abc

首先对于百位a,即a00, a01, ... , a99

我们来统计一下个位和十位上的数字即 00,01,...,99加起来一共用了多少次0~9

按照上面的想法我们很容易知道,十位从0开始每加一,个位0~9就都会被用 1 次,同时十位本身,会被用到10次。这样我们知道每个数字都被用了 10*1 + 10 次,即20次。

同理并根据上面的结论,对于 000,001,...,999 ,我们知道,如果百位从0开始每加一,个位和十位的数字组合在一次0~9各会被用到 20次,同时作为百位本身,会被用到100次。这样我们知道每个数字都被用了 10*20 + 10^2 次,即300次。

根据这个思想很容易发现规律,对于n 位的数字 0 到 n 位的数字9,设 0~9 各数字会被用到的次数为f(n),则有 f(n) = 10 * f(n-1) + 10^(n-1),其中f(1)= 1

我们把结果记入一个名为dp 的数组:dp[0] = 0, dp[1]=1, dp[2]=20, dp[3]=300 , ....

这样我们可以知道

仅考虑百位a,有 
ans [ 0~9 ] + 20*a 
ans [0~a-1] + 10^2 
ans [ a ] + (bc + 1)
 
仅考虑十位,有
ans[ 0~9] + 1*b 
ans[ 0~b-1] + 10^1 
ans[ b ] + (c+1)
 
仅考虑个位 
ans[ 0~c ] +1
 

4. 总结规律:

总结上方的规律可知,

在计入前导0的情况下,要考虑0~n 的数用到了多少各0~9的数字,应该自高向低逐次取出每一位分析

设取出的一位为数字为 x,同时其位于从个位数起的第 y 位,剩余的低位构成的数字为 z ,

则答案计算方法为:

ans[0~9] + dp[y-1]*x   (当x < max 时考虑低位) 
ans[0~x-1] + 10^(y-1)  (当x < max 时考虑x) 
ans[x] + (z+1)    (当 x = max 时考虑 x)
 
 
 

经检查,该方法适用于个位及特殊情况。

5. 解除约定:

我们来考虑如何除去前导0

首先要明白一件事,前导0只对0的计数产生影响。

那么前导0是在哪里产生的呢?

如果上面说的你都明白了,那么很容易知道就在计算最高位时的这两步

ans[0~9] + dp[y-1]*x   (当x < max 时考虑低位)
ans[0~x-1] + 10^(y-1)  (当x < max 时考虑x)

在最高位为0的时候多余出来的

按照上述方法考虑,设 n 位数多余出来的0的个数为 g(n)

① 你可以想象把所有数字都右对齐,得到:

g (1) = 0

g (2) = 10

g (3) = 10 + 100

......

g (n) = 10^1 + 10^2 + ... + 10^(n-1) ,其中 n>2

② 或者这样想:

两位数可以对所有个位数在十位补0,三位数可以在两位数的基础上再在百位上对所有两位数再补一个0,以此类推,易知这也是一个dp

得到 g (n) = g(n-1) + 10^(n-1),其中 g(1) = 0,n>2

至此,思考部分完成。

三、 编写代码:

算法时间复杂度仅为 o ( log10(n) ) ,接近 o (1) ,吊打暴力 o (nlog10n) 的算法。

#include <bits/stdc++.h> 
using namespace std; 
typedef long long ll; 
ll n;
ll dp[20], ans[20],zeronum[20];  //zeronum 用于记录 n 位数的前导 0 个数
ll pow10[20];  //pow10 用于记录 10 的次方数
void makedp(){
    pow10[0]=1;
    for(int i=1;i<15;i++) pow10[i] = pow10[i-1]*10;
    dp[0]=0,dp[1]=1;
    zeronum[0]=zeronum[1]=0;
    for(int i=2;i<15;i++){
        pow10[i]=pow10[i-1]*10;
        zeronum[i]=zeronum[i-1] + pow10[i-1];
        dp[i]=10*dp[i-1] + pow10[i-1];
    } 
} 
void solve(ll n,ll ans[]){
    if(n==0){
        ans[0]=1;
        return;
    }
    ll bitnum = log10(n) + 1;
    ll num[20];
    ll ntmp = n;
    for(int i=1;i<=bitnum;i++){
        num[i] = ntmp%10;
        ntmp/=10;
    }
    for(int i=bitnum;i>=1;i--){
        ll x = num[i];
        ll y = i;
        n -= x*pow10[y-1];
        ll z = n;
        for(int j=0;j<10;j++){
            ans[j] += dp[y-1]*x;
        }
        for(int j=0;j<x;j++){
            ans[j]+=pow10[y-1];
        }
        ans[x] += z+1;
    }
    ans[0]-=zeronum[bitnum];
} 
int main(){
    cin>>n;  
    makedp();   
    solve(n,ans);
    for(int i=0;i<10;i++){
        if(i==0) printf("%lld\n", ans[i]-1);
        else printf("%lld\n",ans[i]);
    }
}

四、 相关例题:

洛谷p2602:https://www.luogu.com.cn/problem/p2602

题目描述

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

输入格式

仅包含一行两个整数 a,ba,b,含义如上所述。

输出格式

包含一行十个整数,分别表示 0\sim 90∼9 在 [a,b][a,b] 中出现了多少次。

输入输出样例

输入

1  99

输出

9 20 20 20 20 20 20 20 20 20

说明/提示

数据规模与约定

对于 30% 的数据,保证 a≤ b ≤ 10^6;

对于 100% 的数据,保证 1≤a≤b≤10^12。

改改代码直接交:

#include <bits/stdc++.h>
using namespace std; 
typedef long long ll; 
ll a,b;
ll dp[20], ans1[20],ans2[20],zeronum[20];
ll pow10[20]; 
void makedp(){
    pow10[0]=1;
    for(int i=1;i<15;i++) pow10[i] = pow10[i-1]*10;
    dp[0]=0,dp[1]=1;
    zeronum[0]=zeronum[1]=0;
    for(int i=2;i<15;i++){
        pow10[i]=pow10[i-1]*10;
        zeronum[i]=zeronum[i-1] + pow10[i-1];
        dp[i]=10*dp[i-1] + pow10[i-1];
    } 
} 
void solve(ll n,ll ans[]){
    if(n==0){
        ans[0]=1;
        return;
    }
    ll bitnum = log10(n) + 1;
    ll num[20];
    ll ntmp = n;
    for(int i=1;i<=bitnum;i++){
        num[i] = ntmp%10;
        ntmp/=10;
    }
    for(int i=bitnum;i>=1;i--){
        ll x = num[i];
        ll y = i;
        n -= x*pow10[y-1];
        ll z = n;
        for(int j=0;j<10;j++){
            ans[j] += dp[y-1]*x;
        }
        for(int j=0;j<x;j++){
            ans[j]+=pow10[y-1];
        }
        ans[x] += z+1;
    }
    ans[0]-=zeronum[bitnum];
}
 
int main(){
    cin>>a>>b;
    makedp();
    solve(a-1,ans1);
    solve(b,ans2);
    for(int i=0;i<10;i++){
        printf("%lld ",ans2[i]-ans1[i]);
    }
}

以上就是c++数位dp统计数字问题示例详解的详细内容,更多关于c++数位dp统计数字的资料请关注其它相关文章!