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#如何动态创建Label,及动态label事件

《C#如何动态创建Label,及动态label事件》:本文主要介绍C#如何动态创建Label,及动态label事件,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#如何动态创建Label,及动态label事件第一点:switch中的生成我们的label事件接着,

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

C++ 中的 if-constexpr语法和作用

《C++中的if-constexpr语法和作用》if-constexpr语法是C++17引入的新语法特性,也被称为常量if表达式或静态if(staticif),:本文主要介绍C++中的if-c... 目录1 if-constexpr 语法1.1 基本语法1.2 扩展说明1.2.1 条件表达式1.2.2 fa

C++中::SHCreateDirectoryEx函数使用方法

《C++中::SHCreateDirectoryEx函数使用方法》::SHCreateDirectoryEx用于创建多级目录,类似于mkdir-p命令,本文主要介绍了C++中::SHCreateDir... 目录1. 函数原型与依赖项2. 基本使用示例示例 1:创建单层目录示例 2:创建多级目录3. 关键注

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

C++ 各种map特点对比分析

《C++各种map特点对比分析》文章比较了C++中不同类型的map(如std::map,std::unordered_map,std::multimap,std::unordered_multima... 目录特点比较C++ 示例代码 ​​​​​​代码解释特点比较1. std::map底层实现:基于红黑