本题通过对所有位数的符合的数进行深度优先遍历,从而得到所有符合的数(提前打表)。在打完表之后只需要进行排序后使用lower_bound和upper_bound就可以找个最近和最远的范围。
然后在遍历这个范围的时候还需要根据没加上的数和当前遍历到的数的差值进行相乘,这样可以节省不停二分寻找的造成的时间。
#include <bits/stdc++.h> using namespace std; #define int long long //使用DFS提前将所有的幸运数字打表打出来 const int maxn = 2048+10; int cnt = 0; int a[maxn]; void dfs(int n, int num) { if (n==11) return ; if (num!=0) a[cnt++] = num; dfs(n+1, num*10+4); dfs(n+1, num*10+7); } signed main() { ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); dfs(1, 0); sort(a, a+cnt); a[cnt++] = 4444444444; // for (int i=0;i<cnt;i++) { // cout<<a[i]<<endl; // } //用二分找到左边界和右边界 int l, r; int ans = 0; cin>>l>>r; int L = lower_bound(a, a+cnt, l)-a; int R = upper_bound(a, a+cnt, r)-a; for (int i=L;i<=R;i++) { ans += (min(a[i], r)-l+1)*a[i]; l = min(a[i], r)+1; } cout<<ans<<endl; return 0; }