幸运数字II 打表

题意：定义只包含4和7的数字为幸运数字 给出区间l,r 求l,r中每个next(i)的值的和 next（i）为第一个大于等于i的幸运数

思路：看到数据范围好像很大 其实不然 在范围内的幸运数字只有几千个 按位数来算的话 1~9 那么幸运数字总共有2^1+2^2+...+2^9个

所以我们采用bfs打表的方式 然后根据l,r一块一块的计算总和 至于为什么要分块计算 按照样例2 7 其中 2 3 4 的next值都是 4
同理 5 6 7 的next值也都是7 更新左端点l的值 当前块next值+1 就变成下一块的区间左端点了 然后用右端点r判断是否结束

#include <bits/stdc++.h>

using namespace std;

#define LL long long

const int N = 2005;
const LL maxn = 5000000000;
LL dp[N];
int top;

void db()
{
    queue <LL> que;

    que.push(4),que.push(7);

    top = 0;

    map <LL,int> mp;

    while(!que.empty())
    {
        LL now = que.front();

        que.pop();

        dp[++ top] = now;

        if(now*10 + 4 <= maxn && !mp[now*10 + 4])
            que.push(now*10 + 4),mp[now*10 + 4] = 1;

        if(now*10 + 7 <= maxn && !mp[now*10 + 7])
            que.push(now*10 + 7),mp[now*10 + 7] = 1;
    }
}

int main()
{
    db();

    LL l,r;

    cin >> l >> r;

    LL res = 0;

    for(int i = 1;i <= top;i ++)
    {
        if(dp[i] >= l)
        {
            if(dp[i] <= r)
            {
                res += (dp[i] - l+ 1)*dp[i];
                l = dp[i] + 1;
            }
            else
            {
                res += (r - l + 1)*dp[i];
                break;
            }
        }
    }

    cout << res << '\n';

    return 0;
}