幸运数字Ⅱ

牛客网

时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld

题目描述

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

题意：
打表出奇迹
你可以提前打好表，记录在数组里
或者现打表，有两个方法
一个是用vector，
或者自身递归查找，存在pre中
打完表后，直接从l开始对比数到r
直接if判断然后sum加有点慢
你可以看每两个pre之间的数最后都做一样相加，比如47~74之间（不含47）的数都算作74，那有多少个数？就是74-47+1，然后直接乘74，加起来就ok了
注意注意！！！不要忘了longlong，可坑死我了

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll pre[100000];
int cnt=0;
int min(ll a,ll b)
{
    return a>b?b:a;
}
void dfs(ll n)
{
    if(n>1e10+2)return ; 
    pre[cnt++]=n;
    dfs(n*10+4);
    dfs(n*10+7);
}
/*
void dfs(ll x)
{
    if(n-1e9>0)return ;
    q.push_back((x<<3)+(x<<1)+4);
    dfs((x<<3)+(x<<1)+4);
    dfs((x<<3)+(x<<1)+7);
    q.push_back((x<<3)+(x<<1)+7);
}

dfs(0);
sort(q.begin(),q.end());
q.push_back(4444444444); 
*/
int main()
{
    ll r,l;
    scanf("%lld %lld",&l,&r);
    dfs(0);
    sort(pre+1,pre+1+cnt);
//    cout<<pre[cnt-1]<<endl;
    ll sum=0;
    ll ant=0;
    for(ll i=l;i<=r;)
    {
    //    if(i>pre[ant])ant++;
    //    sum+=pre[ant];
        while(i>pre[ant])ant++;
        sum+=pre[ant]*(min(r,pre[ant])-i+1);
        i=pre[ant]+1;
    }
    printf("%lld\n",sum);
}