2 条题解

  • 1
    @ 2022-8-25 12:01:48
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<string>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<algorithm>
    #define int long long
    using namespace std;
    const int N=1e6+5;
    const int INF=0x3f3f3f3f;
    int n,m,a[N],dp[20][3];
    int dfs(int len,int f,int flag){
    	if(len==-1)return 1;
    	if(!flag&&dp[len][f==6]!=0)return dp[len][f==6];
    	int nid=flag?a[len]:9;
    	int ans=0;
    	for(int i=0;i<=nid;i++){
    		if((i==4)||(i==2&&f==6))continue;
    		ans+=dfs(len-1,i,flag&&i==a[len]);
    	}
    	if(!flag){
    		dp[len][f==6]=ans;
    	}
    	return ans;
    }
    int find(int num){
    	int len=0;
    	while(num!=0){
    		a[len]=num%10;
    		len++;
    		num/=10;
    	}
    	return dfs(len-1,-1,true);
    }
    signed main(){
    	while(scanf("%lld%lld",&n,&m)){
    		if(n==0&&m==0)return 0;
    		cout << find(m)-find(n-1) << endl;
    	}
    	return 0;
    }
    

    信息

    ID
    482
    时间
    1000ms
    内存
    512MiB
    难度
    7
    标签
    递交数
    90
    已通过
    24
    上传者