首页 > 试题广场 >

诡异数字

[编程题]诡异数字

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

有一天clccle在家里玩手机,突然手机上出现了一个诡异的黑影,眼里闪烁着白光,发出了奇怪的声音(像是正常的声音倒放之后再正放的样子),clccle努力辨别后终于听懂了这个黑影在说什么,大概如下,给定你一个区间[l,r]和多个约束,
请你求出在这个区间内满足这个约束的数字个数(不含前导零),如果clccle不能在1s内求出这个答案,就会被送入一个奇怪的旅馆(Rusty Lake Hotel),因为clccle很害怕,请你帮她在1s之内求出这个答案

输入描述:

注意:此题有多组数据

第一行,一个整数T,代表数据组数

对于每组数据,

有三个数字 l,r,n

接下来n行，每行一个数字x，接下来一个数len表示数字x在数字串中连续出现的次数不能大于len

输出描述:

对于每组数据

输出一个整数,表示l,r中满足约束的数字个数。(对20020219取模)

示例1

输入

输出

50
99

备注:

数据保证没有对数字0的限制( •̀ ω •́ )✧Ǜ

对于全部数据:1<=T<=50,0<=l<r<=1e18,1<=n<=100

算法知识视频讲解

sunsetcolors

发表于 2020-08-19 22:52:10

诡异数字题目地址： https://ac.nowcoder.com/acm/problem/20669 基本思路：考虑维护数位,每次我们维护表示填到位，前一个数位的数为,它连续出现了次的答案,对于每次我们只有两个转移方向,要么这一位和上一位相同,，要么不同变为。其余部分都套上数位的板子就展开全文

瑜画

发表于 2020-08-19 20:54:39

数位dp，注意当出现次数大于限制次数的时候直接返回0，pos==0还不大于就返回1 f[pos][num][cnt] 表示第pos位，末尾数字为num，连续次数为cnt如果下一位还是num，那么转移到dp(pos-1,num,cnt+1)否则转移到dp(pos-1,i,1)也就是说转移到新的数字这展开全文