NC15291 幸运数字Ⅱ

题目描述

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

输出描述:

一个数字表示答案。

思路

先dfs打表，然后排序，排序后找L，R。

当确定L，R后，计算next(l)-next(r)的和，计算和时为了保证符合题意: next(x)为大于等于x的第一个幸运数字 故使大于等于他的第一个幸运数字乘以区间长度。

在处理右边界时为了，为了不使答案准确，故舍去next(r)-r+1这段区间，选择r-l+1这段区间，其中l是动态变化的，每个 l 都是区间的左端点。

#include
#define INF 0x3f3f3f3f
#define DOF 0x7f7f7f7f
#define endl '\n'
#define pii pair
#define pll pair
#define mem(a,b) memset(a,b,sizeof(a))
#define debug(case,x); cout<<case<<"  : "<<x<<endl;
#define open freopen("ii.txt","r",stdin)
#define close freopen("oo.txt","w",stdout)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef long long ll;
using namespace std;
const int maxn = 2e5 + 10;

ll ans=0;
ll a[maxn],cnt=0;

void dfs(ll x){
    if(x>1000000000) return ;
    a[cnt++]=x;
    dfs(x*10+4);
    dfs(x*10+7);
}
int main()
{
    ll l,r;
    cin>>l>>r;
    dfs(4);
    dfs(7);
    a[cnt++]=4444444444;
    sort(a,a+cnt);
    int L=lower_bound(a,a+cnt,l)-a;
    int R=lower_bound(a,a+cnt,r)-a;
    for(int i=L;i<=R;++i){
        ans+=(min(a[i],r)-l+1)*a[i];
        l=a[i]+1;
    }
    cout<<ans<<endl;

}