幸运数字Ⅱ (DFS)

幸运数字Ⅱ (DFS)

题目传送门

题意：求出区间[L, R]的next[i]的幸运数之和

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
ll a[N],cnt=2;
void dfs(ll x){
    if(x>1e9) return;
    a[cnt++]=x;
    dfs(x*10+4);
    dfs(x*10+7);
}
int main(){
    ll l,r;
    a[0]=4,a[1]=7;
    dfs(4);
    dfs(7);
    a[cnt]=4444444444;
    sort(a,a+cnt+1);
    cin>>l>>r;
    int p1=lower_bound(a,a+cnt+1,l)-a,p2=lower_bound(a,a+cnt+1,r)-a;
    ll ans=0;
    for(int i=p1;i<=p2;i++){
        ans+=(min(a[i],r)-l+1)*a[i];
        l=a[i]+1;
    }
    cout<<ans<<endl;
    return 0;
}