pypy3 解法, 执行用时: 161ms, 内存消耗: 27112K, 提交时间: 2023-06-09 20:08:01

from functools import lru_cache
mod = int(1e9) + 7
@lru_cache(None)
def solve(n):
    s = str(n)
    @lru_cache(None)
    def f(i,mask ,is_limit, is_num):
        if i == len(s):
            return int(is_num)
        res = 0
        if not is_num:
            res = f(i + 1, 0, False, False)
        low = 1 - int(is_num)
        up = int(s[i]) if  is_limit else 9
        for d in range(low, up + 1):
            if not is_num:
                res +=  f(i + 1, d, is_limit and d == up, True)
            elif abs(d - mask) >= 2:
                res += f(i + 1, d, is_limit and d == up, True)
        return res
    return f(0,0,True,False)


l, r = map(int,input().split())
print(solve(r) - solve(l - 1))

C++ 解法, 执行用时: 3ms, 内存消耗: 424K, 提交时间: 2022-06-08 13:03:06

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f[20][12]={0};
int Dim[20]={0};
ll DFS(int x,int pre,int bj)
{
	if(!x)return 1;
	if(!bj&&f[x][pre]!=-1)return f[x][pre];
	int maxn=bj?Dim[x]:9;
	ll temp=0;
	for(int i=0; i<=maxn; i++)
	{
		if(abs(pre-i)<2)continue;
		if(pre==11&&i==0)
		temp+=DFS(x-1,11,bj&&i==maxn);
		else temp+=DFS(x-1,i,bj&&i==maxn);
	}
	if(!bj)f[x][pre]=temp;
	return temp;
}
ll Ask(ll x)
{
	Dim[0]=0;
	while(x)
	{
		Dim[++Dim[0]]=x%10;
		x/=10;
	}
	Dim[Dim[0]+1]=0;
	return DFS(Dim[0],11,1);
}
int main()
{
	ll a,b;
	memset(f,-1,sizeof(f));
	cin>>a>>b;
	cout<<Ask(b)-Ask(a-1)<<endl;
    return 0;
}