题目
windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。
windy想知道, 在A和B之间,包括A和B,总共有多少个windy数?
100%的数据,满足1<=A<=B<=2000000000
洛谷题目链接
读入格式
包含两个整数,A B。
输出格式
一个整数
输入样例一
1 10
输出样例一
9
题解
数位Dp模板题,不懂的感性理解一下。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
| #include <stdio.h> #define re register
int a[15]; int f[15][15];
inline int Abs(int x) {return x<0?-x:x;}
inline void Next_Dp() { //f[i][j] i为位数,j为第i位的数值 //f[i][j]=f[i-1][k] 如果(j-k)的绝对值大于等于2 即合法 //初始化 f[1][j]=1 j属于0-9 for(re int j=0; j<=9; ++j) f[1][j]=1; for(re int i=2; i<=10; ++i) for(re int j=0; j<=9; ++j) for(re int k=0; k<=9; ++k) if(Abs(j-k)>=2) f[i][j]+=f[i-1][k]; }
//求[0,X) inline int Solve(int x) { int ans=0,len=0; //分解每一位数 while(x) { a[++len]=x%10; x/=10; } //除了最高位,求每一位的0-9的所有f[i][j] i=1->len-1 j=0->9; for(re int i=1; i<len; ++i) for(re int j=1; j<=9; ++j) ans+=f[i][j]; //求最高位,小于X的f[i][j] for(re int j=1; j<a[len]; ++j) ans+=f[len][j]; //逐位等于X,往下比 for(re int i=len-1; i; --i) { for(re int j=0; j<=a[i]-1; ++j) if(Abs(j-a[i+1])>=2) ans+=f[i][j]; if(Abs(a[i+1]-a[i])<2) break; } return ans; }
int main() { Next_Dp(); int A,B; scanf("%d %d",&A,&B); printf("%d\n",Solve(B+1)-Solve(A)); return 0; }
|