4 条题解

  • -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;
    }
    

    信息

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