幸运数字II

幸运数字II

题目描述：

定义一个数字为幸运数字当且仅当它的所有数位都是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)。

输出描述：

一个数字表示答案。

样例输入：

2 7

样例输出：

33

Idea

因为此类数数量不多，所以直接打表记录下所有数字，然后再求l-r的和时，其实是分段进行的，对于一个左端点x求next（x），那么再x-next（x）- 1区间均为next（x）,所以直接计算，然后更新左端点为next（x）+ 1，直到将所有全部计算完。

Code

/******************************************
/@Author: .Sunbeam
/@Date: 2020-04-08
/@Remark:    
/@FileName: luckynumber
******************************************/
#include <bits/stdc++.h>
#define CSE(x,y) memset(x,y,sizeof(x))
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
#define FAST ios::sync_with_stdio(false);cin.tie(0);
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll , ll> pll;

const int maxn = 111111;

ll get_val(vector<ll> box)
{
    ll ans = 0, step  = 1;
    for(auto i : box)
    {
        ans += i * step;
        step *= 10;
    }
    return ans;
}

ll next_val(ll number)
{
    vector<ll> box;
    while(number)
    {
        box.push_back(number % 10);
        number /= 10;
    }
    for(auto &i : box)
    {
        if(i == 4)
        {
            i = 7;
            return get_val(box);
        }
        else
        {
            i = 4;
        }
        
    }
    box.push_back(4);
    for(auto &i : box)
        i = 4;
    return get_val(box);
}

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.in","r",stdin);
    #endif
    FAST;
    vector<ll> arry;
    ll be = 4;
    arry.push_back(be);
    while(be <= 10000000000)
    {
        be = next_val(be);
        arry.push_back(be);
    }
    ll l, r;
    cin >> l >> r;
    ll ans = 0;
    while(l <= r)
    {
        int ad = lower_bound(arry.begin(), arry.end(), l) - arry.begin();
        ll k = arry[ad];
        if(k <= r)
            ans += k * (k - l + 1);
        else
        {
            ans += k * (r - l + 1);
        }
        l = k + 1;
        //cout << l << endl;
    }
    cout << ans << endl;
    return 0;
}