莫名其妙的20分 WA了八个
查看原帖
莫名其妙的20分 WA了八个
315998
8Grklter楼主2021/4/26 23:35

(开了些完全没必要的long long

#include <cstdio>
#include <algorithm>
#include <cstring>
#define ll long long
using namespace std;
ll a,b,d[15],f[12][12];
int c[12];
int getlen(ll x){
	int l=0;
	while(x/d[++l]);
	return l;
}
int abs1(int x){
	if(x<0)x=-x;return x;
}
void ttt(){//10^i
	d[0]=1;
	for(int i=1;i<=11;++i)d[i]=10*d[i-1];
}
void work(){
	int len=getlen(b+1);
	//f[i][j]:i为最高位,共j位 
	for(int i=0;i<=9;++i)f[i][1]=1;
	for(int i=2;i<=len;++i){//位数 
		for(int j=0;j<=9;++j){//当前位 
			for(int k=0;k<=9;++k){//下一位 
				if(abs1(k-j)<=1)continue;
				f[j][i]+=f[k][i-1];
			}
		}
	}
} 
int dp(ll x){
	ll ans=0; 
	int len=getlen(x);int tt=len;
	while(tt){
		c[tt--]=x/d[tt];x%=d[tt];
	}
	c[len+1]=-1;
	for(int i=1;i<len;++i)
		for(int j=1;j<=9;++j)ans+=f[j][i];
	while(len){
		for(int i=0;i<c[len];++i){//当前位 
			if(abs1(c[len+1]-i)<=1)continue;
			ans+=f[i][len];
		}
		if(abs1(c[len]-c[len+1])<=1)break;
		len--;
	}
	return ans;
}
int main(){
	scanf("%lld%lld",&a,&b);
	ttt();
	work();
	ll ans=dp(b+1);
	ans-=dp(a);
	printf("%lld",ans);
	return 0;
}
2021/4/26 23:35
加载中...