《算法競(jìng)賽·快沖300題》將于2024年出版，是《算法競(jìng)賽》的輔助練習(xí)冊(cè)。
所有題目放在自建的OJ New Online Judge。
用C/C++、Java、Python三種語言給出代碼，以中低檔題為主，適合入門、進(jìn)階。

題目描述

【題目描述】 彩虹數(shù)：一個(gè)無前導(dǎo)0的10進(jìn)制整數(shù)，相鄰的兩個(gè)數(shù)字不相同。
給定下界和上界，計(jì)算它們之間的彩虹數(shù)數(shù)量。
【輸入格式】 輸入第一行為正整數(shù)L，表示下界。第二行為正整數(shù)R，表示上界。
1≤L≤R≤10^(100000)。注意，此處的數(shù)字長度可能會(huì)達(dá)到100000。
【輸出格式】 輸出一個(gè)數(shù)字表示答案，由于答案過大，需要對(duì)998244353求余。
【輸入樣例】

樣例1：
1
10

樣例2：
12345
65432

【輸出樣例】

樣例1：
10

樣例2：
35882

題解

??由于區(qū)間[L, R]的范圍極大，直接暴力驗(yàn)證每個(gè)數(shù)字是否為彩虹數(shù)會(huì)超時(shí)。另外，由于數(shù)字太大，直接按數(shù)字進(jìn)行計(jì)算不方便，可以用高精度處理大數(shù)，用數(shù)組num[]來存這個(gè)大數(shù)，num[i]是大數(shù)的第i位。
??本題與數(shù)位統(tǒng)計(jì)有關(guān)，是一道比較直接的數(shù)位統(tǒng)計(jì)DP題。代碼使用了《算法競(jìng)賽》“5.3.2 數(shù)位統(tǒng)計(jì)DP的記憶化搜索實(shí)現(xiàn)”的dfs()模板[ 數(shù)位統(tǒng)計(jì)DP的原理和兩種編碼方法見《算法競(jìng)賽》，清華大學(xué)出版社，羅勇軍、郭衛(wèi)斌著，333~338頁。本題代碼套用了書上的模板。]，在dfs()中統(tǒng)計(jì)數(shù)字時(shí)，排除掉彩虹數(shù)即可。
??定義dp[]為有前導(dǎo)零、無數(shù)位限制時(shí)的彩虹數(shù)的數(shù)量，例如：
??dp[1]，01~09內(nèi)彩虹數(shù)的數(shù)量，有dp[1] = 9。
??dp[2]，001~099內(nèi)彩虹數(shù)的數(shù)量，有dp[2] = 81。排除彩虹數(shù)001、002、…、009、011、022、…099，共排除18個(gè)，得dp[2] = 99-18 = 81。
??dp[3]，0001~0999內(nèi)彩虹數(shù)的數(shù)量，對(duì)應(yīng)dp[3] = 729，排除彩虹數(shù)0001、0002、0099、0100、…0111、0112、…、0999。
??代碼的步驟：
??（1）讀L，R。第28行按字符串讀入L和R。
??（2）solve(s)計(jì)算[1, s]范圍內(nèi)的彩虹數(shù)，[L, R]內(nèi)的彩虹數(shù)是solve?-solve(L-1)。由于L是字符串形式表示的數(shù)字，第29~32行提前計(jì)算得到L-1的字符串形式。
??（3）在solve(s)中，先把字符串s表示的大數(shù)轉(zhuǎn)為數(shù)組num[]，大數(shù)存在num[1]~num[len]中。例如輸入s =“65432”，得num[1]~num[5] =2、3、4、5、6。
??（4）dfs()統(tǒng)計(jì)[1, s]內(nèi)的彩虹數(shù)的數(shù)量，s是用num[1]~num[len]表示的大數(shù)。第13行累加無前導(dǎo)0時(shí)的數(shù)字的數(shù)量，第14行去除彩虹數(shù)。
??下面說明復(fù)雜度。dfs()的主要任務(wù)是計(jì)算dp[]，即求dp[1] ~ dp[len]，計(jì)算量極小，約為10×len。
【重點(diǎn)】 數(shù)位統(tǒng)計(jì)DP。

C++代碼

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int num[100005];        //存輸入的數(shù)字
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位數(shù)，結(jié)束返回
    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，無前導(dǎo)0
        else if(last != i) ans += dfs(pos-1,i,false,limit&&(i==up)); //與上一位不同，排除彩虹數(shù)
        ans %= MOD;
    }
    if(!lead && !limit)    dp[pos] = ans;    //狀態(tài)記錄：有前導(dǎo)0，無數(shù)位限制
    return ans;
}
ll solve(string s){
    int len=0;
    for(int i=s.length()-1;i>=0;i--)   //把字符串轉(zhuǎn)成數(shù)字，存入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表示的大數(shù)轉(zhuǎn)為數(shù)組num[]，大數(shù)存在num[0]~num[len-1]中。例如輸入s =“65432”，得num[0]~num[4] =2、3、4、5、6。文章來源地址http://www.zghlxwxcb.cn/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]]  #把字符串轉(zhuǎn)成數(shù)字，存入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)

到了這里，關(guān)于《算法競(jìng)賽·快沖300題》每日一題：“彩虹數(shù)”的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！