4 条题解

  • 1
    @ 2023-7-28 16:58:09

    #include<iostream> #include<string> #include<cctype> #include<cmath> #include<cstdlib> #include<cstring> #include<vector> #include<algorithm> #include<map> #include<set> #include<iomanip> using namespace std; #define LL long long const int N = 1e6+10; const int INF = 0x3f3f3f3f; #define mod 1e9+7 int a[20],dp[20][2]; int dfs(int pos,int pre,int limit){ if(pos==-1)return 1; if(!limit&&dp[pos][pre6]!=-1)return dp[pos][pre6]; int tmp=0; int up=limit?a[pos]:9; for(int i=0;i<=up;i++){ if(pre6&&i2)continue; if(i4)continue; tmp+=dfs(pos-1,i,limit&&ia[pos]); } if(!limit)dp[pos][pre==6]=tmp; return tmp; } int solve(int x){ int pos=0; while(x){ a[pos++]=x%10; x/=10; } return dfs(pos-1,-1,true); } int main(){ //freopen("","r",stdin); //freopen("","w",stdout); int ri,le; while(~scanf("%d %d",&ri,&le)&&ri+le){ memset(dp,-1,sizeof(dp)); printf("%d \n",solve(le)-solve(ri-1)); } return 0; }

    • 1
      @ 2022-8-25 11:59:53
      #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;
      }
      
      • -1
        @ 2021-11-21 10:09:39
        #include<iostream> 
        #include<cstring>
        using namespace std; 
        int dp[8][2];
        int a[8];
        int n,m;
        int dfs(int pos, int bef, bool limit){
            if(pos == -1) return 1;
            if(!limit && dp[pos][bef==6] != -1)
                return dp[pos][bef==6];
            int maxx = limit ? a[pos] : 9;
            int tmp = 0;
            for(int i = 0; i <= maxx; i++){
                if(bef == 6 && i == 2) continue;
                if(i == 4) continue;
                tmp += dfs(pos-1, i, limit && i == a[pos]);
            }
            if(!limit) dp[pos][bef==6] = tmp;
            return tmp;
        }
        int solve(int n){
            int pos = 0;
            while(n){
                a[pos++] = n % 10;
                n /= 10;
            }
            return dfs(pos-1, -1, true);
        }
        int main(){
        	while(cin >> n >> m && n+m){
                memset(dp,-1,sizeof(dp));
                cout << solve(m) - solve(n-1) << endl;
            }
            return 0;
        }
        
        • -3
          @ 2021-11-21 10:09:19
          /*****************************************
          Note  : 
          ******************************************/
          #include <queue>
          #include <math.h>
          #include <stack>
          #include <stdio.h>
          #include <iostream>
          #include <vector>
          #include <iomanip>
          #include <string.h>
          #include <algorithm>
          using namespace std;
          #define LL long long
          const int N = 1e5 + 10;
          const int INF = 0x3f3f3f3f;
          int a[N];
          int dp[20][3];
          int dfs(int len , int pre , int limit)
          {
          	if(len == -1) return 1;
          	if(!limit && dp[len][pre==6] != 0 ) return dp[len][pre == 6];
          	int up = limit ? a[len] : 9;
          	int ans = 0;
          	for(int i = 0 ; i <= up ; i++)
          	{
          		if( (i == 4) || (pre == 6 && i == 2) ) continue;
          		ans += dfs(len-1 , i , limit && i == a[len]);
          	}
          	if(!limit) dp[len][pre==6] = ans;
          	return ans;
          }
          int find(int x)
          {
          	int len = 0;
          	while(x)
          	{
          		a[len++] = x%10;
          		x/=10;
          	}
          	return dfs(len - 1, -1 , true);
          }
          int main()
          {
          	int l ,r ;
          	while(cin >> l >> r && l + r != 0)
          		cout << find(r) - find(l-1) << endl;
          	return 0;
          }
          
          • 1

          信息

          ID
          483
          时间
          1000ms
          内存
          512MiB
          难度
          5
          标签
          递交数
          88
          已通过
          33
          上传者