《算法竞赛·快冲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求余。
【输入样例】
样例1:
1
10
样例2:
12345
65432
【输出样例】
样例1:
10
样例2:
35882
题解
由于区间[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。文章来源:https://www.toymoban.com/news/detail-696515.html
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模板网!