C++ 动态规划 数位统计DP 计数问题

2024-02-10 16:44

本文主要是介绍C++ 动态规划 数位统计DP 计数问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

给定两个整数 a
和 b
,求 a
和 b
之间的所有数字中 0∼9
的出现次数。

例如,a=1024,b=1032
,则 a
和 b
之间共有 9
个数如下:

1024 1025 1026 1027 1028 1029 1030 1031 1032

其中 0 出现 10
次,1 出现 10
次,2 出现 7
次,3 出现 3
次等等…

输入格式
输入包含多组测试数据。

每组测试数据占一行,包含两个整数 a
和 b

当读入一行为 0 0 时,表示输入终止,且该行不作处理。

输出格式
每组数据输出一个结果,每个结果占一行。

每个结果包含十个用空格隔开的数字,第一个数字表示 0 出现的次数,第二个数字表示 1 出现的次数,以此类推。

数据范围
0<a,b<100000000
输入样例:
1 10
44 497
346 542
1199 1748
1496 1403
1004 503
1714 190
1317 854
1976 494
1001 1960
0 0
输出样例:
1 2 1 1 1 1 1 1 1 1
85 185 185 185 190 96 96 96 95 93
40 40 40 93 136 82 40 40 40 40
115 666 215 215 214 205 205 154 105 106
16 113 19 20 114 20 20 19 19 16
107 105 100 101 101 197 200 200 200 200
413 1133 503 503 503 502 502 417 402 412
196 512 186 104 87 93 97 97 142 196
398 1375 398 398 405 499 499 495 488 471
294 1256 296 296 296 296 287 286 286 247
在这里插入图片描述
主要思想就是分情况讨论。

#include <iostream>
#include <algorithm>
#include <vector>using namespace std;int get(vector<int> num, int l, int r) // 辅助函数,返回一个大数l与r位之间的数字
{int res = 0;for(int i = l; i >= r; i -- )res = res * 10 + num[i];return res;
}int power10(int x) // 辅助函数,返回10的x次方
{int res = 1;while(x -- )res *= 10;return res;
}int count(int n, int x) // 计算1 - n之间,x出现的次数
{if(!n) return 0;vector<int> num; // 把每一位取出来存下来while(n){num.push_back(n % 10);n /= 10;}n = num.size();int res = 0;for(int i = n - 1 - !x; i >= 0; i -- ) //- !x的意思是,如果x是0 的话,不枚举最高位{if(i < n - 1) // 非最高位的一般情况{res += get(num, n - 1, i + 1) * power10(i); // 情况1if(!x) res -= power10(i); // 特判一下特殊情况(x = 0),例子图总从001开始算(本来是从000开始算的)//也就是少一份power10(i), 减掉即可}if(num[i] == x) // 情况2.2res += get(num, i - 1, 0) + 1; else if(num [i] > x) // 情况2.3res += power10(i); }return res;
}int main ()
{int a, b;while(cin >> a >> b, a || b){if(a > b) swap(a, b);for(int i = 0; i < 10; i ++ )cout << count(b, i) - count(a - 1, i) << ' ';cout << endl;}return 0;
}

这篇关于C++ 动态规划 数位统计DP 计数问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/697586

相关文章

一文详解SpringBoot中控制器的动态注册与卸载

《一文详解SpringBoot中控制器的动态注册与卸载》在项目开发中,通过动态注册和卸载控制器功能,可以根据业务场景和项目需要实现功能的动态增加、删除,提高系统的灵活性和可扩展性,下面我们就来看看Sp... 目录项目结构1. 创建 Spring Boot 启动类2. 创建一个测试控制器3. 创建动态控制器注

从入门到精通C++11 <chrono> 库特性

《从入门到精通C++11<chrono>库特性》chrono库是C++11中一个非常强大和实用的库,它为时间处理提供了丰富的功能和类型安全的接口,通过本文的介绍,我们了解了chrono库的基本概念... 目录一、引言1.1 为什么需要<chrono>库1.2<chrono>库的基本概念二、时间段(Durat

C++20管道运算符的实现示例

《C++20管道运算符的实现示例》本文简要介绍C++20管道运算符的使用与实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录标准库的管道运算符使用自己实现类似的管道运算符我们不打算介绍太多,因为它实际属于c++20最为重要的

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性:

c++中的set容器介绍及操作大全

《c++中的set容器介绍及操作大全》:本文主要介绍c++中的set容器介绍及操作大全,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录​​一、核心特性​​️ ​​二、基本操作​​​​1. 初始化与赋值​​​​2. 增删查操作​​​​3. 遍历方

解析C++11 static_assert及与Boost库的关联从入门到精通

《解析C++11static_assert及与Boost库的关联从入门到精通》static_assert是C++中强大的编译时验证工具,它能够在编译阶段拦截不符合预期的类型或值,增强代码的健壮性,通... 目录一、背景知识:传统断言方法的局限性1.1 assert宏1.2 #error指令1.3 第三方解决

C++11委托构造函数和继承构造函数的实现

《C++11委托构造函数和继承构造函数的实现》C++引入了委托构造函数和继承构造函数这两个重要的特性,本文主要介绍了C++11委托构造函数和继承构造函数的实现,具有一定的参考价值,感兴趣的可以了解一下... 目录引言一、委托构造函数1.1 委托构造函数的定义与作用1.2 委托构造函数的语法1.3 委托构造函

C++11作用域枚举(Scoped Enums)的实现示例

《C++11作用域枚举(ScopedEnums)的实现示例》枚举类型是一种非常实用的工具,C++11标准引入了作用域枚举,也称为强类型枚举,本文主要介绍了C++11作用域枚举(ScopedEnums... 目录一、引言二、传统枚举类型的局限性2.1 命名空间污染2.2 整型提升问题2.3 类型转换问题三、C

在Linux终端中统计非二进制文件行数的实现方法

《在Linux终端中统计非二进制文件行数的实现方法》在Linux系统中,有时需要统计非二进制文件(如CSV、TXT文件)的行数,而不希望手动打开文件进行查看,例如,在处理大型日志文件、数据文件时,了解... 目录在linux终端中统计非二进制文件的行数技术背景实现步骤1. 使用wc命令2. 使用grep命令

springboot如何通过http动态操作xxl-job任务

《springboot如何通过http动态操作xxl-job任务》:本文主要介绍springboot如何通过http动态操作xxl-job任务的问题,具有很好的参考价值,希望对大家有所帮助,如有错... 目录springboot通过http动态操作xxl-job任务一、maven依赖二、配置文件三、xxl-