《算法竞赛·快冲300题》每日一题:“彩虹数”

这篇具有很好参考价值的文章主要介绍了《算法竞赛·快冲300题》每日一题:“彩虹数”。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

算法竞赛·快冲300题》将于2024年出版,是《算法竞赛》的辅助练习册。
所有题目放在自建的OJ New Online Judge。
用C/C++、Java、Python三种语言给出代码,以中低档题为主,适合入门、进阶。


彩虹数” ,链接: http://oj.ecustacm.cn/problem.php?id=1840

题目描述

【题目描述】 彩虹数:一个无前导0的10进制整数,相邻的两个数字不相同。
给定下界和上界,计算它们之间的彩虹数数量。
【输入格式】 输入第一行为正整数L,表示下界。第二行为正整数R,表示上界。
1≤L≤R≤10^(100000)。注意,此处的数字长度可能会达到100000。
【输出格式】 输出一个数字表示答案,由于答案过大,需要对998244353求余。
【输入样例】

样例11
10

样例212345
65432

【输出样例】

样例110

样例235882

题解

  由于区间[L, R]的范围极大,直接暴力验证每个数字是否为彩虹数会超时。另外,由于数字太大,直接按数字进行计算不方便,可以用高精度处理大数,用数组num[]来存这个大数,num[i]是大数的第i位。
  本题与数位统计有关,是一道比较直接的数位统计DP题。代码使用了《算法竞赛》“5.3.2 数位统计DP的记忆化搜索实现”的dfs()模板[ 数位统计DP的原理和两种编码方法见《算法竞赛》,清华大学出版社,罗勇军、郭卫斌著,333~338页。本题代码套用了书上的模板。],在dfs()中统计数字时,排除掉彩虹数即可。
  定义dp[]为有前导零、无数位限制时的彩虹数的数量,例如:
  dp[1],01~09内彩虹数的数量,有dp[1] = 9。
  dp[2],001~099内彩虹数的数量,有dp[2] = 81。排除彩虹数001、002、…、009、011、022、…099,共排除18个,得dp[2] = 99-18 = 81。
  dp[3],0001~0999内彩虹数的数量,对应dp[3] = 729,排除彩虹数0001、0002、0099、0100、…0111、0112、…、0999。
  代码的步骤:
  (1)读L,R。第28行按字符串读入L和R。
  (2)solve(s)计算[1, s]范围内的彩虹数,[L, R]内的彩虹数是solve®-solve(L-1)。由于L是字符串形式表示的数字,第29~32行提前计算得到L-1的字符串形式。
  (3)在solve(s)中,先把字符串s表示的大数转为数组num[],大数存在num[1]~num[len]中。例如输入s =“65432”,得num[1]~num[5] =2、3、4、5、6。
  (4)dfs()统计[1, s]内的彩虹数的数量,s是用num[1]~num[len]表示的大数。第13行累加无前导0时的数字的数量,第14行去除彩虹数。
  下面说明复杂度。dfs()的主要任务是计算dp[],即求dp[1] ~ dp[len],计算量极小,约为10×len。
【重点】 数位统计DP。

C++代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int num[100005];        //存输入的数字
ll dp[100005];
ll MOD = 998244353;
ll dfs(int pos,int last,bool lead,bool limit){             //last: 上一位
    ll ans = 0;
    if(pos==0)   return 1;                                 //递归到0位数,结束返回
    if(!lead && !limit && dp[pos]!=-1)  return dp[pos];    //记忆化搜索
    int up=(limit ? num[pos] : 9);                         //这一位的最大值
    for(int i=0;i<=up;i++){
        if(i==0 && lead)   ans += dfs(pos-1,i,true, limit&&(i==up)); //lead=true,无前导0
        else if(last != i) ans += dfs(pos-1,i,false,limit&&(i==up)); //与上一位不同,排除彩虹数
        ans %= MOD;
    }
    if(!lead && !limit)    dp[pos] = ans;    //状态记录:有前导0,无数位限制
    return ans;
}
ll solve(string s){
    int len=0;
    for(int i=s.length()-1;i>=0;i--)   //把字符串转成数字,存入num[1]~num[len]
        num[++len]=(s[i]-'0');         //例如输入“65432”,得num[1:5]=2 3 4 5 6
    memset(dp,-1,sizeof(dp));
    return dfs(len,-1,true,true);
}
int main(){
    string L,R;   cin>>L>>R;
    for(int i=L.length()-1;i>=0;i--){    //求L-1,例如L=12345,L-1=12344
        if(L[i]!='0') { L[i]--; break;}  //这一位不是0,减1即可
        else   L[i]='9';                 //这一位是0,减1得9
    }
    cout<<((solve(R)-solve(L))%MOD + MOD) % MOD;
    return 0;
}

Java代码

import java.util.*;
public class Main {
    static long[] dp = new long[100005];
    static int[] num = new int[100005];
    static long MOD = 998244353;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String L = scanner.next();
        String R = scanner.next();
        StringBuilder resultL = new StringBuilder(L);
        for (int i = L.length() - 1; i >= 0; i--) {
            if (resultL.charAt(i) != '0') {
                resultL.setCharAt(i, (char)(resultL.charAt(i) - 1));
                break;
            } else {
                resultL.setCharAt(i, '9');
            }
        }
        System.out.println((solve(R) - solve(resultL.toString()) + MOD) % MOD);
    }
    public static long dfs(int pos, int last, boolean lead, boolean limit) {
        long ans = 0;
        if (pos == 0) return 1;
        if (!lead && !limit && dp[pos] != -1) return dp[pos];
        int up = (limit ? num[pos] : 9);
        for (int i = 0; i <= up; i++) {
            if (i == 0 && lead) ans += dfs(pos - 1, i, true, limit && (i == up));
            else if (last != i) ans += dfs(pos - 1, i, false, limit && (i == up));
            ans %= MOD;
        }
        if (!lead && !limit) dp[pos] = ans;
        return ans;
    }

    public static long solve(String s) {
        int len = 0;
        num = new int[100005];
        for (int i = s.length() - 1; i >= 0; i--) 
            num[++len] = s.charAt(i) - '0';
        Arrays.fill(dp, -1);
        return dfs(len, -1, true, true);
    }
}

Python代码

   在solve(s)中,先把字符串s表示的大数转为数组num[],大数存在num[0]~num[len-1]中。例如输入s =“65432”,得num[0]~num[4] =2、3、4、5、6。文章来源地址https://www.toymoban.com/news/detail-696515.html

import sys
sys.setrecursionlimit(100000)
 
MOD = 998244353
dp = [-1] * 100005
num = []
def dfs(pos, last, lead, limit):
    if pos == -1:   return 1     
    global dp
    global num 
    if not lead and not limit and dp[pos] != -1:   return dp[pos]     
    up = num[pos] if limit else 9
    ans = 0     
    for i in range(up + 1):
        if i == 0 and lead:  ans += dfs(pos - 1, i, True,  limit and (i == up))
        elif last != i:      ans += dfs(pos - 1, i, False, limit and (i == up))         
        ans %= MOD     
    if not lead and not limit:    dp[pos] = ans         
    return ans
 
def solve(s):
    global dp
    global num
    num = [int(c) for c in s[::-1]]  #把字符串转成数字,存入num[0]~num[len-1]
    dp = [-1] * 100005
    return dfs(len(num) - 1, -1, True, True)
 
L = input()
R = input()
L_minus_one = str(int(L) - 1)
result = (solve(R) - solve(L_minus_one) + MOD) % MOD
print(result)

到了这里,关于《算法竞赛·快冲300题》每日一题:“彩虹数”的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 《算法竞赛·快冲300题》每日一题:“松鼠与栗子”

    《 算法竞赛·快冲300题 》将于2024年出版,是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C++、Java、Python三种语言给出代码,以中低档题为主,适合入门、进阶。 “ 松鼠与栗子 ” ,链接: http://oj.ecustacm.cn/problem.php?id=1852 【题目描述】 现在有m棵栗

    2024年02月11日
    浏览(43)
  • 《算法竞赛·快冲300题》每日一题:“凑二十四”

    《 算法竞赛·快冲300题 》将于2024年出版,是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C++、Java、Python三种语言给出代码,以中低档题为主,适合入门、进阶。 “ 凑二十四 ” ,链接: http://oj.ecustacm.cn/problem.php?id=1793 【题目描述】 给你n个数字,

    2024年02月11日
    浏览(36)
  • 罗勇军 → 《算法竞赛·快冲300题》每日一题:“排列变换” ← 贪心算法

    【题目来源】 http://oj.ecustacm.cn/problem.php?id=1812 http://oj.ecustacm.cn/viewnews.php?id=1023 【题目描述】 给定一个长度为 n 的排列 a,需要将这个排列变成 b。 每次可以选择一个数字往左移若干个位置。 请求出 最小需要移动的元素个数 。 【输入格式】 第一行为正整数 n,1≤n≤100000。

    2024年02月12日
    浏览(40)
  • 罗勇军 →《算法竞赛·快冲300题》每日一题:“游泳” ← DFS+剪枝

    【题目来源】 http://oj.ecustacm.cn/problem.php?id=1753 http://oj.ecustacm.cn/viewnews.php?id=1023 【题目描述】 游泳池可以等分为n行n列的小区域,每个区域的温度不同。 小明现在在要从游泳池的左上角(1, 1)游到右下角(n, n),小明只能向上下左右四个方向游,不能游出泳池。 而小明对温度十分

    2024年02月10日
    浏览(36)
  • 罗勇军 →《算法竞赛·快冲300题》每日一题:“小球配对” ← 并查集

    【题目来源】 http://oj.ecustacm.cn/problem.php?id=1850 http://oj.ecustacm.cn/viewnews.php?id=1023 【题目描述】 给定 n 个小球,编号为 1-n ,给定 m 个篮子,编号为 1-m 。 每个球只允许放入样例给定的编号为 Ai 或者 Bi 的两个篮子中的 1 个。 每个球必须放入某个篮子。 如果篮子中球的数量为奇

    2024年02月11日
    浏览(39)
  • ( 动态规划) 516. 最长回文子序列 ——【Leetcode每日一题】

    难度:中等 给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。 子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。 示例 1: 输入:s = “bbbab” 输出:4 解释:一个可能的最长回文子序列为 “bbbb” 。 示例

    2024年02月06日
    浏览(42)
  • ( 动态规划) 1035. 不相交的线 ——【Leetcode每日一题】

    难度:中等 在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。 现在,可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线,这些直线需要同时满足满足: nums1[i] == nums2[j] 且绘制的直线不与任何其他连线(非水平线)相交。 请注意,连线即使在端点也不能相交

    2024年02月05日
    浏览(42)
  • 【Leetcode每日一题】 动态规划 - 地下城游戏(难度⭐⭐⭐)(61)

    1. 题目解析 题目链接:174. 地下城游戏 这个问题的理解其实相当简单,只需看一下示例,基本就能明白其含义了。 2.算法原理 一、状态表定义 在解决地下城游戏问题时,我们首先需要对状态进行恰当的定义。一个直观的想法是,从起点开始,到达[i, j]位置时所需的最低初始

    2024年04月29日
    浏览(42)
  • [Week 19]每日一题(C++,数学,并查集,动态规划)

    目录 [Daimayuan] T1 倒数第n个字符串(C++,进制) 输入格式 输出格式 样例输入 样例输出 解题思路 [Daimayuan] T2 排队(C++,并查集) 输入格式 输出格式 样例输入1 样例输出1 样例输入2 样例输出2 样例输入3 样例输出3 数据规模 解题思路 [Daimayuan] T3 素数之欢(C++,BFS) 数据规模

    2024年02月02日
    浏览(50)
  • 【每日一题 | 动态规划】访问完所有房间的第一天

    【动态规划】【数组】【2024-03-28】 1997. 访问完所有房间的第一天 定义状态 定义 f[i] 表示第一次到达房间 i 的日期编号。 根据题意,首次(第 1 次)访问房间 i 时,因为 1 是计数,所以下一次一定会访问房间 j = nextVisit[i] 。只有访问次数达到偶数才能访问右边的下一个房间

    2024年04月16日
    浏览(38)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包