难度：黄/绿

算法：数位 dp，打表

打表出奇迹。

令块长 $b=10^7$。

我们对于每个 $i$，暴力打表求得 $[1,i\times b]$ 中有多少满足条件的数。

如果我们要求 $[1,r]$ 中满足条件的数，只需要找到最大的 $i$ 使得 $i\times b\le r$，使用事先打好的表算出这部分的结果。其余部分不足 $b$，直接暴力算。

打表代码：

#include<bits/stdc++.h>
using namespace std;
int n=2e9,b=1e7,c;
inline bool ck(int x){
	while(x>=10){
		if(int(abs(x%10-(x/10)%10))<=1) return false;
		x/=10;
	}
	return true;
}
int main(){
	freopen("windynumbers.txt","w",stdout);
	printf("0,");
	for(int i=1;i<=n;i++){
		if(ck(i)) c++;
		if(i%b==0){``
			printf("%d",c);
			if(i!=n) putchar(',');
		}
	}
}

时间复杂度 $O(n\log_{10}n)$，本机运行时间 $47$ 秒左右。

用于提交的代码：

#include<bits/stdc++.h>
using namespace std;
int s=1e7,a,b;
vector<int> v={0,1459689,2442570,3442552,4440413,5438525,6436637,7434498,8434480,9417361,10538745,10538745,10538745,10538745,11536606,12534718,13532830,14530691,15530673,16513554,17634938,18756322,18756322,18756322,18756322,19754434,20752546,21750407,22750389,23733270,24854654,25976038,26958919,26958919,26958919,26958919,27957031,28954892,29954874,30937755,32059139,33180523,34163404,35163386,35163386,35163386,35163386,36161247,37161229,38144110,39265494,40386878,41369759,42369741,43367602,43367602,43367602,43367602,44367584,45350465,46471849,47593233,48576114,49576096,50573957,51572069,51572069,51572069,51572069,52554950,53676334,54797718,55780599,56780581,57778442,58776554,59774666,59774666,59774666,59774666,60896050,62017434,63000315,64000297,64998158,65996270,66994382,67992243,67992243,67992243,67992243,69113627,70096508,71096490,72094351,73092463,74090575,75088436,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,77209802,78192683,78192683,78192683,78192683,79190795,80188656,81188638,82171519,83292903,84414287,85397168,86397150,86397150,86397150,86397150,87395011,88394993,89377874,90499258,91620642,92603523,93603505,94601366,94601366,94601366,94601366,95601348,96584229,97705613,98826997,99809878,100809860,101807721,102805833,102805833,102805833,102805833,103788714,104910098,106031482,107014363,108014345,109012206,110010318,111008430,111008430,111008430,111008430,112129814,113251198,114234079,115234061,116231922,117230034,118228146,119226007,119226007,119226007,119226007,120347391,121330272,122330254,123328115,124326227,125324339,126322200,127322182,127322182,127322182};
inline bool ck(int x){
	while(x>=10){
		if(int(abs(x%10-(x/10)%10))<=1) return false;
		x/=10;
	}
	return true;
}
int re(int x){
	int u=x/s;
	int res=v[u];
	for(int i=u*s+1;i<=x;i++){
		if(ck(i)) res++;
	}
	return res;
}
int main(){
	scanf("%d%d",&a,&b);
	printf("%d",re(b)-re(a-1));
}