数位dp,挂了,样例没过,求解答
查看原帖
数位dp,挂了,样例没过,求解答
461359
huangrenheluogu楼主2023/1/31 15:44
#include<bits/stdc++.h>
#define int long long
using namespace std;
int l,r,a[15],cnt,f[15][15][15][2][2][2];
inline void read(int &res){
	res=0;int f=1;char ch=getchar();
	while('0'>ch||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while('0'<=ch&&ch<='9'){
		res=(res<<1)+(res<<3)+(ch^48);
		ch=getchar();
	}
	res*=f;
}
inline void put(int x){
	if(x<0) putchar('-'),x=-x;
	int i=1;
	while(i*10<=x) i*=10;
	while(i){
		putchar(x/i+'0');
		x%=i;i/=10;
	}
}
inline int work(int dep,int laslas,int las,bool lian,bool _4,bool _8,int lim){
	if(dep==0) return (lian&&(_4^_8));
	if(lim==0&&f[dep][laslas][las][lian][_4][_8]!=-1) return f[dep][laslas][las][lian][_4][_8];
	if(_4&&_8) return 0;
	int res=0,up=lim?a[dep]:9;
	for(int i=(dep==cnt)?1:0;i<=up;i++){
		if(i==4&&_8) continue ;
		if(i==8&&_4) continue ;
		res+=work(dep-1,las,i,lian||(i==laslas&&i==las),_4||(i==4),_8&&(i==8),lim&&(i==up));
	}
	if(lim==0) f[dep][laslas][las][lian][_4][_8]=res;
	return res;
}
inline int div(int x){
	memset(f,-1,sizeof(f));
	cnt=0;
	while(x){
		a[++cnt]=x%10;
		x/=10;
	}
	return work(cnt,10,10,0,0,0,1);
}
signed main(){
	read(l),read(r);
	printf("%lld",div(r)-div(l-1));
	return 0;
}

谢谢大佬。

2023/1/31 15:44
加载中...