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

目录
  • 一、问题描述:
  • 二、问题分析:
    • 1. 抽取题意:
    • 2. 初步思考:
    • 3. 示例分析:
    • 4. 总结规律:
    • 5. 解除约定:
  • 三、 编写代码:
  • 四、 相关例题:

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统计数字的资料请关注我们其它相关文章!

(0)

相关推荐

  • C语言实现大整数加减运算详解

    前言 我们知道,在数学中,数值的大小是没有上限的,但是在计算机中,由于字长的限制,计算机所能表示的范围是有限的,当我们对比较小的数进行运算时,如:1234+5678,这样的数值并没有超出计算机的表示范围,所以可以运算.但是当我们在实际的应用中进行大量的数据处理时,会发现参与运算的数往往超过计算机的基本数据类型的表示范围,比如说,在天文学上,如果一个星球距离我们为100万光年,那么我们将其化简为公里,或者是米的时候,我们会发现这是一个很大的数.这样计算机将无法对其进行直接计算. 可能我们认为实际应

  • 关于统计数字问题的算法

    一本书的页码从自然数1开始顺序编码直到自然数n.书的页码按照通常的习惯编排,每个页码都不含多余的前导数字0.例如第6页用6表示而不是06或006.数字统计问题要求对给定书的总页码,计算出书的全部页码中分别用到多少次数字0,1,2,3,.....9. 这个题目有个最容易想到的n*log10(n)的算法.这是自己写的复杂度为O(n*log10(n))的代码: void statNumber(int n) { int i, t; int count[10] = {0}; for(i = 1; i <=

  • C++实现分数计算器

    分数计算器项目设计,供大家参考,具体内容如下 一.问题描述及功能要求 1.分数计算器程序的每种功能都可以用菜单选项列出,用户可以根据需要选择相应的菜单项,从而执行不同的子程序以完成相应的功能 2.增加运算符重载功能,使所设计的分数计算器可以进行四则运算&幂运算&逻辑运算.四则运算&幂运算可以用菜单选项列出,用户可以根据需要选择相应的运算. 3.程序具有判断功能,当有非法的输入时(如分母等于零等),能给出提示信息并退出运算 4.可将分数化为十进制小数和带分数 5.设计逻辑功能的函数使

  • C++统计中英文大小写字母、数字、空格及其他字符个数的方法

    本文实例讲述了C++统计中英文大小写字母.数字.空格及其他字符个数的方法.分享给大家供大家参考,具体如下: /* * 作 者: 刘同宾 * 完成日期:2012 年 11 月 28 日 * 版 本 号:v1.0 * 输入描述: * 问题描述: 有一篇文章,共有三行文字,每行有80个字符.要求分别统计出其中英文大写字母.小写字母.数字.空格以及其他字符的个数. * 程序输出: * 问题分析:略 * 算法设计:略 */ #include<iostream> using namespace std;

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

    目录 一.问题描述: 二.问题分析: 1. 抽取题意: 2. 初步思考: 3. 示例分析: 4. 总结规律: 5. 解除约定: 三. 编写代码: 四. 相关例题: Tips:如果你是真的不理解,不要只看,拿出笔来跟着步骤自己分析. 一.问题描述: 一本书的页码从自然数 1 开始顺序编码直到自然数 n .书的页码按照通常的习惯编排, 每个页码不含多余的前导数字 0. 例如, 第 6 页用数字 6 表示而不是 06 或 006等. 数字计数问题要求对给定书的总页码 n,计算书的全部页码分别用到多少次

  • Go Java算法猜数字游戏示例详解

    目录 猜数字游戏 方法一:遍历(Java) 方法一:遍历(Go) 猜数字游戏 你在和朋友一起玩 猜数字(Bulls and Cows)游戏,该游戏规则如下: 写出一个秘密数字,并请朋友猜这个数字是多少.朋友每猜测一次,你就会给他一个包含下述信息的提示: 猜测数字中有多少位属于数字和确切位置都猜对了(称为 "Bulls",公牛), 有多少位属于数字猜对了但是位置不对(称为 "Cows",奶牛).也就是说,这次猜测中有多少位非公牛数字可以通过重新排列转换成公牛数字. 给

  • Python线性点运算数字图像处理示例详解

    目录 点运算 定义 分类 线性点运算 分段线性点运算 非线性点运算 对数变换 幂次变换 点运算 定义 分类 线性点运算 例子: 分段线性点运算 非线性点运算 对数变换 幂次变换 1. 点运算是否会改变图像内像素点之间的空间位置关系? 点运算是一种像素的逐点运算,它与相邻的像素之间没有运算关系,点运算不会改变图像内像素点之间的空间位置关系. 2. 对图像灰度的拉伸,非线性拉伸与分段线性拉伸的区别? 非线性拉伸不是通过在不同灰度值区间选择不同的线性方程来实现对不同灰度值区间的扩展与压缩,而是在整个灰

  • Python数学建模StatsModels统计回归可视化示例详解

    目录 1.如何认识可视化? 2.StatsModels 绘图工具包 (Graphics) 3.Matplotlib 绘图工具包 4.Seaborn 绘图工具包 5.多元回归案例分析(Statsmodels) 5.1 问题描述 5.2 问题分析 观察数据分布特征 观察数据间的相关性 建模与拟合 6.Python 例程(Statsmodels) 6.1 问题描述 6.2 Python 程序 6.3 程序运行结果: 1.如何认识可视化? 需要指出的是,虽然不同绘图工具包的功能.效果会有差异,但在常用功

  • Python 统计字数的思路详解

     问题描述: 用 Python 实现函数 count_words(),该函数输入字符串 s 和数字 n,返回 s 中 n 个出现频率最高的单词.返回值是一个元组列表,包含出现次数最高的 n 个单词及其次数,即 [(<单词1>, <次数1>), (<单词2>, <次数2>), ... ],按出现次数降序排列. 您可以假设所有输入都是小写形式,并且不含标点符号或其他字符(只包含字母和单个空格).如果出现次数相同,则按字母顺序排列. 例如: print count

  • Python猜数字算法题详解

    今天刷的第一道算法题,先拿一道简单点的试试手,这道题目的要求是: 两个人甲乙在猜数字,甲先从1,2,3三个数字中随机抽3次,结果是guess.乙随后也随机抽三次,结果是answer.然后对比甲乙两个人的结果.示例如下: guess:[1,2,3], answer: [1, 2, 3] 那么结果就是猜对了3次 guess: [1,2,3] answer:[3,2,1] 那么结果就是猜对了1次 guess: [1,2,3], answer:[3, 3,1] 那么结果就是猜对了0次 即将guess和a

  • Python数学建模StatsModels统计回归之线性回归示例详解

    目录 1.背景知识 1.1 插值.拟合.回归和预测 1.2 线性回归 2.Statsmodels 进行线性回归 2.1 导入工具包 2.2 导入样本数据 2.3 建模与拟合 2.4 拟合和统计结果的输出 3.一元线性回归 3.1 一元线性回归 Python 程序: 3.2 一元线性回归 程序运行结果: 4.多元线性回归 4.1 多元线性回归 Python 程序: 4.2 多元线性回归 程序运行结果: 5.附录:回归结果详细说明 1.背景知识 1.1 插值.拟合.回归和预测 插值.拟合.回归和预测

  • Go Java算法之从英文中重建数字示例详解

    目录 从英文中重建数字 Java实现 Go实现 从英文中重建数字 给你一个字符串 s ,其中包含字母顺序打乱的用英文单词表示的若干数字(0-9).按 升序 返回原始的数字. 示例 1: 输入:s = "owoztneoer" 输出:"012" 示例 2: 输入:s = "fviefuro" 输出:"45" 提示: 1 <= s.length <= 105 s[i] 为 ["e","g&

  • 基于Django模板中的数字自增(详解)

    Django框架的模板提供了{% for %} 标签来进行循环 例如对集合进行循环是比较简单的 {% for row in v1 %} <div>{{row.name}}</div> {% endfor %} 但是在Django中,并不直接支持形如"int i = 0;i<100;i++" 这样的循环,Django有自己的自增方法 假设v1内有2个元素 1,从1开始正向自增 结果1,2 {% for row in v1 %} <div>{{fo

  • JSON创建键值对(key是中文或者数字)方式详解

    先准备好一个空的json对象 var obj = {}; 1. 最原始的方法 obj.name = 'zhangsan'; //这种方式很简单的添加了一个键值对 //输出:{name:"zhangsan"} //缺点:这边的name不能是对象 /* 比如: var name = 'tom'; obj.name = 'zhangsan'; 输出obj:{name:'zhangsan'} 中文可以使用,但是数字不能使用 obj.家="中国"; obj.88(不能这么使用

随机推荐