90pts WA on #5 求调 悬关
查看原帖
90pts WA on #5 求调 悬关
556975
PNNNN楼主2024/4/6 09:46
#include<bits/stdc++.h>
#define int long long
using namespace std;

int L,R,dp[15][15],fac[15]={1};

inline int lg(int x){
	int res=0;
	while(x){
		res++,x/=10;
	}return res;
}

inline int solve(int x){
	if(x<10)return x;
	int res=0ll,n=lg(x)-1;
	for(int i=0;i<n;i++){
		res+=dp[i][9]-dp[i][0];
	}res+=dp[n][x/fac[n]-1]-dp[n][0];
	for(int i=n-1;i>=0;i--){
		int y=x/fac[i+1],z;
		x%=fac[i+1],z=x/fac[i];
		for(int j=0;j<x/fac[i];j++){
			if(llabs(j-y)>=2){
				res+=dp[i][j];
				if(j)res-=dp[i][j-1]; 
			}
		}if(llabs(y-z)<2)break;
	}return res;
}

inline int read(){
	register int x(0),t(0);
	static char ch=getchar();
	while(!isdigit(ch)){t|=(ch=='-');ch=getchar();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return t?-x:x;
}

signed main(){
	for(int i=1;i<=10;i++)fac[i]=fac[i-1]*10;
    for(int i=0;i<=9;i++)dp[0][i]=i+1;
	for(int i=1;i<=10;i++){
		for(int j=0;j<=9;j++){
			if(j-2>=0)dp[i][j]+=dp[i-1][j-2];
			if(j+2<=9)dp[i][j]+=dp[i-1][9]-dp[i-1][j+1];
		}
		for(int j=1;j<=9;j++){
			dp[i][j]+=dp[i][j-1];
		}
	}
	L=read(),R=read();
	cout<<solve(R)-solve(L-1);
	return 0;
}
2024/4/6 09:46
加载中...