幸运数字

题目链接：https://ac.nowcoder.com/acm/problem/15291

题目描述

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

分析

本题利用深搜打表，之后处理一波数据即可。
注意打完表后要排序，处理数据采用的方法见代码，较为巧妙。
另外，本题用int过不去，上long long。

AC代码

---

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
using namespace std;
 
int l,r;
const int maxn=1024*2;
long long a[maxn];
int cnt=0;
 
void dfs(long long x)
{
    if(x>1000000000)
        return;
    a[cnt++]=x;
    dfs(x*10+4);
    dfs(x*10+7);
}
int main()
{
    cin >> l >> r;
    dfs(4);
    dfs(7);
    a[cnt]=4444444444;  //r为10亿时对应的值
    sort(a,a+cnt);
    int x=lower_bound(a,a+cnt+1,l)-a;
    int y=lower_bound(a,a+cnt+1,r)-a;
    long long ans=0;
    for (int i = x; i <= y; i++)    //注意此处的处理
    {
        ans+=(min((long long)r,a[i])-l+1)*a[i];
        //*右侧为next()的值 左侧为多少数的next()的值是右侧值
        l=a[i]+1;
    }
    cout << ans << endl;
    return 0;
}