90pts #4TLE 求助qwq
查看原帖
90pts #4TLE 求助qwq
757816
skcks楼主2024/8/16 23:49
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <iomanip>
#include <cmath>
#include <queue>
#include <vector>
using namespace std;
long long T;
long long n,tot=0,m;
long long f[10][11];
long long a[11];
long long dfs(long long len,bool lim,int bz,bool vis){
	if(bz>0)vis=true;
	if(len==0)return 1;
	if(!lim&&f[bz][len]!=-1&&!vis){
		return f[bz][len];
	}
	long long up=(lim?a[len]:9),ans=0;
	for(int i=0;i<=up;i++){
		if(vis&&abs(bz-i)<2)continue;
		ans+=dfs(len-1,lim&&i==up,i,vis);
	}
	if(!lim)f[bz][len]=ans;
	return ans;
}
long long calc(long long s){
	tot=0;
	memset(f,(long long)-1,sizeof(f));
	memset(a,(long long)0,sizeof(a));
	long long x=s;
	while(x){
		a[++tot]=x%10;
		x/=10;
	}
//	cout<<tot<<":"<<endl;
	return dfs(tot,1,-2,false); 
}
int main(){
	scanf("%lld%lld",&n,&m);
	cout<<calc(m)-calc(n-1)<<endl;
	return 0; 
}

2024/8/16 23:49
加载中...