2 条题解

  • 0
    @ 2023-5-22 20:35:31
    #include <bits/stdc++.h>
    using namespace std;
    int l,r;
    int f[8][10];
    inline void init(){
    	for(int i=0;i<=9;i++) if(i!=4) f[1][i]=1;
    	for(int i=2;i<=7;i++)
    		for(int j=0;j<=9;j++){
    			if(j==4) continue;
    			for(int k=0;k<=9;k++){
    				if(k==4||(k==2&&j==6)) continue;
    				f[i][j]+=f[i-1][k];
    			}
    		}
    }
    inline int dp(int n){
    	if(!n) return 1;
    	vector <int> nums;
    	while(n){
    		nums.push_back(n%10);
    		n/=10;
    	}
    	int res=0,last=0,x;
    	for(int i=nums.size()-1;i>=0;i--){
    		x=nums[i];
    		for(int j=0;j<x;j++){
    			if((last==6&&j==2)||j==4) continue;
    			res+=f[i+1][j];
    		}
    		if(x==4||(last==6&&x==2)) break;
    		last=x;
    		if(!i) res++;
    	}
    	return res;
    }
    int main(){
    	init();
    	while(1){
    		cin>>l>>r;
    		if(l==0&&r==0) return 0;
    		cout<<dp(r)-dp(l-1)<<endl;
    	}
    	return 0;
    }
    

    信息

    ID
    646
    时间
    1000ms
    内存
    512MiB
    难度
    9
    标签
    递交数
    11
    已通过
    6
    上传者