Windy数题解

发表于

题目

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;
}