牛客练习赛13 B 幸运数字Ⅱ【前缀和 + 位运算 + 二分】

题目描述

定义一个数字为幸运数字当且仅当它的所有数位都是4或者7。
比如说，47、744、4都是幸运数字而5、17、467都不是。
定义next(x)为大于等于x的第一个幸运数字。给定l，r，请求出next(l) + next(l + 1) + … + next(r - 1) + next(r)。

输入描述:

两个整数l和r (1 <= l <= r <= 1000,000,000)。

输出描述:

一个数字表示答案。

示例1

输入

2 7

输出

33

示例2

输入

7 7

输出

7

题意： 略

分析： 我们可以预处理出来范围内的幸运数子，然后维护一下前缀和，再二分出左右端点，两边剩下的独立计算，中间的利用前缀和即可，例如
[5,45]为例，已知前几项为 4， 7， 44， 47 ....
然后我们找到端点[7,44],中间的前缀和处理，然后两端的单独处理即可

注意 ： 虚加0前缀和时方便处理，当题目给你1e9时，位运算只到了 77777777，还得虚加一个数据，这里单独处理即可，还有long long

参考代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;

vector<ll> a;
ll rr[maxn];

ll f(int x,int tag) {
    ll res = 0;
    for (int i = 0; (1 << i) <= x; i++) {
        if((1 << i) & x) {
            if(tag) res = res * 10 + 4;
            else res = res * 10 + 7;
        } else {
            if(tag) res = res * 10 + 7;
            else res = res * 10 + 4;
        }
    }
    return res;
}


int main() {
    ios_base::sync_with_stdio(false);
    a.push_back(0);
    for (int i = 1; i < (1 << 9); i++) {
        a.push_back(f(i,0));
        a.push_back(f(i,1));
    }
    a.push_back(4444444444);
    sort(a.begin(),a.end());
    for (int i = 1; i < a.size(); i++) {
        rr[i] = rr[i - 1] + (a[i] - a[i - 1]) * 1ll * a[i];
    }
    ll l,r;cin>>l>>r;
    int L,R;   //左右端点
    L = lower_bound(a.begin(),a.end(),l) - a.begin();
    R = lower_bound(a.begin(),a.end(),r) - a.begin();
    if(a[R] != r) R--; //注意细节
    ll res = rr[R] - rr[L];
    res += (r - a[R]) * 1ll * a[R + 1];
    res += (a[L] - l + 1) * 1ll * a[L];
    cout<<res<<endl;
    return 0;
}

最后

以上就是仁爱流沙为你收集整理的牛客练习赛13 B 幸运数字Ⅱ【前缀和 + 位运算 + 二分】的全部内容，希望文章能够帮你解决牛客练习赛13 B 幸运数字Ⅱ【前缀和 + 位运算 + 二分】所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。