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

这篇具有很好参考价值的文章主要介绍了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
C++ 动态规划 数位统计DP 计数问题,力扣,动态规划,算法笔记,c++,动态规划
主要思想就是分情况讨论。文章来源地址https://www.toymoban.com/news/detail-830676.html

#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); // 情况1
            if(!x) res -= power10(i); // 特判一下特殊情况(x = 0),例子图总从001开始算(本来是从000开始算的)
                                      //也就是少一份power10(i), 减掉即可
        }
        if(num[i] == x) // 情况2.2
            res += get(num, i - 1, 0) + 1; 
        else if(num [i] > x) // 情况2.3
            res += 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 计数问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 动态规划——数位DP 学习笔记

    引入 数位 DP 往往都是这样的题型:给定一个区间 ([l, r]) ,求这个区间中满足某种条件的数的总数。 简单的暴力代码如下: 而当数据规模过大,暴力枚举就 (mathbb T) 飞了,因此引入数位 DP: 概念 数位(digit):对于十进制,即把一个数字按照个位、十位、百位等,一位

    2024年02月08日
    浏览(44)
  • 算法基础复盘笔记Day11【动态规划】—— 区间DP、计数类DP、树形DP、记忆化搜索

    ❤ 作者主页:欢迎来到我的技术博客😎 ❀ 个人介绍:大家好,本人热衷于 Java后端开发 ,欢迎来交流学习哦!( ̄▽ ̄)~* 🍊 如果文章对您有帮助,记得 关注 、 点赞 、 收藏 、 评论 ⭐️⭐️⭐️ 📣 您的支持将是我创作的动力,让我们一起加油进步吧!!!🎉🎉 1. 题目

    2024年02月01日
    浏览(40)
  • AcWing算法学习笔记:动态规划(背包 + 线性dp + 区间dp + 计数dp + 状态压缩dp + 树形dp + 记忆化搜索)

    算法 复杂度 时间复杂度0(nm) 空间复杂度0(nv) 代码 算法 通过滚动数组对01背包朴素版进行空间上的优化 f[i] 与 f[i - 1]轮流交替 若体积从小到大进行遍历,当更新f[i, j]时,f[i - 1, j - vi] 已经在更新f[i, j - vi]时被更新了 因此体积需要从大到小进行遍历,当更新f[i, j]时,f[i - 1,

    2024年02月21日
    浏览(42)
  • POJ - 2282 The Counting Problem(数位DP 计数问题)

    Given two integers a and b, we write the numbers between a and b, inclusive, in a list. Your task is to calculate the number of occurrences of each digit. For example, if a = 1024 a = 1024 a = 1024 and b = 1032 b = 1032 b = 1032 , the list will be 1024 1024 1024 1025 1025 1025 1026 1026 1026 1027 1027 1027 1028 1028 1028 1029 1029 1029 1030 1030 1030 1031 10

    2023年04月17日
    浏览(35)
  • 【动态规划】【 数位dp】2827. 范围中美丽整数的数目

    数位dp 动态规划汇总 给你正整数 low ,high 和 k 。 如果一个数满足以下两个条件,那么它是 美丽的 : 偶数数位的数目与奇数数位的数目相同。 这个整数可以被 k 整除。 请你返回范围 [low, high] 中美丽整数的数目。 示例 1: 输入:low = 10, high = 20, k = 3 输出:2 解释:给定范围

    2024年04月12日
    浏览(41)
  • [leetcode~数位动态规划] 2719. 统计整数数目 hard

    给你两个数字字符串 num1 和 num2 ,以及两个整数 max_sum 和 min_sum 。如果一个整数 x 满足以下条件,我们称它是一个好整数: num1 = x = num2 min_sum = digit_sum(x) = max_sum. 请你返回好整数的数目。答案可能很大,请返回答案对 109 + 7 取余后的结果。 注意,digit_sum(x) 表示 x 各位数字之

    2024年01月18日
    浏览(42)
  • C++动态规划-线性dp算法

    莫愁千里路 自有到来风 CSDN 请求进入专栏                                    X 是否进入《 C++ 专栏》? 确定 目录  线性dp简介 斐波那契数列模型  第N个泰波那契数 思路: 代码测试:  三步问题 思路: 代码测试: 最小花费爬楼梯 思路: 代码测试:  路径问题 数字三

    2024年02月19日
    浏览(45)
  • c++ 算法之动态规划—— dp 详解

    dp 是 c++ 之中一个简单而重要的算法,每一个 OIer 必备的基础算法,你知道它究竟是什么吗? 目录 一、简介         1.为什么不能贪心?         2.揭秘 dp   二、应用         1.定义         2.边界值         3.动态转移方程         4.结果         5.代码

    2024年04月09日
    浏览(44)
  • 【算法】动态规划(dp问题),持续更新

    介绍本篇之前,我想先用人话叙述一般解决动态规划问题的思路: 动态规划的问题,本身有许多产生结果的可能,需要在具体题目下得到满足某个条件的解。 如何得到呢? 我们就需要根据这个具体问题,建立一个状态表( dp 表 ),在这张 dp 表中的每一个位置的数据都有明

    2024年02月04日
    浏览(47)
  • C++算法 —— 动态规划(7)两个数组的dp

    每一种算法都最好看完第一篇再去找要看的博客,因为这样会帮你梳理好思路,看接下来的博客也就更轻松了。当然,我也会尽量在写每一篇时都可以不懂这个算法的人也能边看边理解。 动规的思路有五个步骤,且最好画图来理解细节,不要怕麻烦。当你开始画图,仔细阅读

    2024年02月07日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包