刷题记录:牛客NC15291幸运数字Ⅱ

传送门:牛客

题目描述:

定义一个数字为幸运数字当且仅当它的所有数位都是4或者7。
比如说，47、744、4都是幸运数字而5、17、467都不是。
定义next(x)为大于等于x的第一个幸运数字。给定l，r，请求出next(l) + next(l + 1) + ... + next(r - 1) + next(r)。
输入:
2 7
输出:
33

emmm,算是一道水题吧.

主要思路:

1. 对于这道题我们发现幸运数字的个数最多也只有1<<10+1中可能性.所以我们准备直接存储即可
2. 对于我们的存储方法我们可以在判断过程中进行存储,此时我们只要求出每一次我们当前的K [K属于L~R之间的一个位置],所小于的一个幸运数字即可此时我们可以选择直接枚举.(当然你也可以选择一个区间一个区间的进行累加,速度会比单个累加快上很多,但是此处直接枚举并不会超时)

刚开始我一直在思考假设用DFS如何保证存进数组中的数字有序,最后发现自己可以使用sort就行(/笑哭),浪费了时间…

具体的代码部分:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
#include <stack>
#include <deque>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
ll l,r;
ll ans=0;
ll a[1<<11];int cnt=0;
void dfs(ll n) {
	if(n>=1000000000) return ;
	a[++cnt]=n;
	dfs(n*10+4);
	dfs(n*10+7);
	return ;
}
int main() {
	dfs(0);
	a[++cnt]=4444444444;
	sort(a+1,a+cnt+1);
	l=read();r=read();
	int pos=lower_bound(a+1,a+cnt+1,l)-a;
	for(ll i=l;i<=r;i++) {
		if(i<=a[pos]) {
			ans+=a[pos];
		}else {
			pos+=1;
			ans+=a[pos];
		}
	}
	printf("%lld\n",ans);
	return 0;
}