题解 | #送分了QAQ#

思路

看到楼上有dp做法的，原谅我难以看懂，我是直接暴力过的。
前缀和可以O(1)得到答案，只需要进行预处理求1~1e6讨厌的数个数就好了。O(1e6)
判断一个数是否讨厌，可以对其每一位模4，每两位模38.

代码

#include<bits/stdc++.h>
using namespace std;

int n,m,sum[1000005];

bool check(int x){
    while(x){
        if(x%10==4||x%100==38) return true;
        x/=10;
    }
    return false;
}

int main(){
    sum[0]=0;
    for(int i=1;i<=1000000;i++){
        sum[i]=sum[i-1]+check(i);
    }
    scanf("%d%d",&n,&m);
    while(n!=0||m!=0){
        cout<<sum[m]-sum[n-1]<<endl;
        scanf("%d%d",&n,&m);
    }
    return 0;
}