E、幸运数字Ⅱ

戳我传送

解题思路

可以通过观察在一段区间内的值是相同的 1-3->4;4-6->7。
我们通过预处理将可能的值升序放在一个容器内，注意一点要把放进去，<-当输入1e9时。
给定l,r；我们通过lower_bound(it,it,l)，查找l在容器中的位置。一步步往下去取区间，注意特判临界情况，即第一个区间的右边界>r，最后一个区间左边界是不是要全拿。

时间复杂度 O(N)

Code

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;
 
inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
 
const int maxn = 1e9 + 3;
vector<ll> p; //存放4 7 44 47 74...
queue<ll> que;
 
void init() {
    p.push_back(4);
    p.push_back(7);
    que.push(4);
    que.push(7);
    while (que.size()) {
        ll x = que.front();
        que.pop();
        ll tmp1 = (x << 3) + (x << 1) + 4, tmp2 = (x << 3) + (x << 1) + 7;
        if (tmp1 < maxn) {
            p.push_back(tmp1);
            que.push(tmp1);
        }
        if (tmp2 < maxn) {
            p.push_back(tmp2);
            que.push(tmp2);
        }
    }
    p.push_back(4444444444);
}
 
int main() {
    init();
    int l = read(), r = read();
    int pos = lower_bound(p.begin(), p.end(), l) - p.begin();
    ll sum = 0;
    if (p[pos] <= r) sum = (p[pos] - l + 1) * p[pos];
    else {
        sum = (r - l + 1) * p[pos];
        printf("%lld\n", sum);
        return 0;
    }
    for (++pos; p[pos] <= r; ++pos)  sum += (p[pos] - p[pos - 1]) * p[pos];
    if (p[pos] > r && p[pos - 1] != r)   //r不在边界上  7777
        sum += (r - p[pos - 1]) * p[pos];
    printf("%lld\n", sum);
    return 0;
}