Description

  windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道,
在A和B之间,包括A和B,总共有多少个windy数?

Input

  包含两个整数,A B。

Output

  一个整数

Sample Input

【输入样例一】
1 10
【输入样例二】
25 50

Sample Output

【输出样例一】
9
【输出样例二】
20

HINT

【数据规模和约定】

100%的数据,满足 1 <= A <= B <= 2000000000 。

第一题 数位dp  分析了好久还是都是细节没有注意到

题目中给的范围大概在2*10^9左右 显然这题是无法线性解决的  那么我们考虑 因为他和数是多少没有关系 而是和这个数中 每个数字互相之间的大小关系有关 那么我们一位一位来考虑 设f[i][j]表示 我的数字长为i  然后最高位为j 我的windy数一共有多少 那么显然可以看出来这个转移就是  f[i][j]=sigma(f[i-1][k])k=0~9 &&abs(k-j)>=2 然后首先我先预处理出前10位的这个数组 然后采取类似前缀的思想 比如l~r这个区间 那显然我就是1~r区间的windy数-1~l-1区间的windy数的个数

如果直接累加的话 显然很容易超出边界 那怎么办  我首先可以假设这个数一共是k位 然后那么位数<k的时候铁定是所有的windy数我都是可取的 同时 我还知道 如果我现在恰好有k位 那么我<num[k]这位的所有windy数也是可取的 那么当我这一位等于num[k]的时候怎么办呢 那我可以考虑枚举我第k-1位的数是哪些 然后就可以一直递归的做下去 注意 如果我num[i]与num[i+1]的差距小于2的话 后面我都可以不用递归下去了  最后如果没有因为上一个限制条件退出循环的话 那么比如3 5 8 2 9这个数 也会是一个windy数 所以我最后还需要特判一下+1 至于这个递归的话那就是我就是需要去枚举我第i-1位比我原数小的情况  相等时再继续递归的

 


elijahqi

退役了 现在在商院 偶尔打CF,有时有ACM regional也去玩一下

发表评论