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

相关文章

C++中全局变量和局部变量的区别

《C++中全局变量和局部变量的区别》本文主要介绍了C++中全局变量和局部变量的区别,全局变量和局部变量在作用域和生命周期上有显著的区别,下面就来介绍一下,感兴趣的可以了解一下... 目录一、全局变量定义生命周期存储位置代码示例输出二、局部变量定义生命周期存储位置代码示例输出三、全局变量和局部变量的区别作用域

C++中assign函数的使用

《C++中assign函数的使用》在C++标准模板库中,std::list等容器都提供了assign成员函数,它比操作符更灵活,支持多种初始化方式,下面就来介绍一下assign的用法,具有一定的参考价... 目录​1.assign的基本功能​​语法​2. 具体用法示例​​​(1) 填充n个相同值​​(2)

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中,如果使用类成员变量时未给定其初始值,那么它将被

C++中NULL与nullptr的区别小结

《C++中NULL与nullptr的区别小结》本文介绍了C++编程中NULL与nullptr的区别,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编... 目录C++98空值——NULLC++11空值——nullptr区别对比示例 C++98空值——NUL

C++ Log4cpp跨平台日志库的使用小结

《C++Log4cpp跨平台日志库的使用小结》Log4cpp是c++类库,本文详细介绍了C++日志库log4cpp的使用方法,及设置日志输出格式和优先级,具有一定的参考价值,感兴趣的可以了解一下... 目录一、介绍1. log4cpp的日志方式2.设置日志输出的格式3. 设置日志的输出优先级二、Window

一文详解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. 遍历方