AOJ 840.下一个幸运数

173


题目


点击显/隐题目

数字的每一位只可能是4或者7的称为幸运数,比如说4,7,44,474,7474都是幸运数,而54,40,444467777都不是幸运数。而数字A的下一个幸运数,表示的是大于等于A的最小的幸运数。比如4的下一个幸运数是4,而5的下一个幸运数是7。现在给出一个区间[L, R],求出区间内每个数的下一个幸运数的和。





一个整数t,表示测试数据的组数(1<=t<=200)。
每组测试数据,两个整数L和R,空格隔开(1<=L<=R<=1000000000)。





区间内每个数的下一个幸运数的和





3
4 4
3 4
4 7





4
8
25





题解



找到 [l,r] 范围内所有的所有整数的 下一个幸运数
很显然,幸运数是非常少的
47 看作 01
可以发现数量只有 {% raw %}$ log_2 1000000000 ${% endraw %} 个
然后打个表,二分查找 lr 两侧的幸运数,每两个幸运数为一个区间(最两侧端点是 lr)
然后计算求和即可
不用一个一个加,区间端点相减乘以右端点即可

最后测试的时候,应该对于 lr 都测试下比幸运数小 11 相等的情况
也即最后测试 6 组即可
顺便测试下极端值也行(为了保证极端值没问题,打表要打到比最大值大)




代码


点击显/隐代码
`cpp 下一个幸运数 https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
/*/
#define debug
#include
//*/
#include
#include
#include
#include
using namespace std;


typedef unsigned long long LL;
const int maxn = 5000;
LL L[maxn];
int pos=0;

void dfs(LL t){
if(t >= 7777777777LL)
return;
L[pos++] = t*10+4;
L[pos++] = t*10+7;
dfs(t*10+4);
dfs(t*10+7);
}

LL lowerbound(LL arr,int size, LL key) {
int half;
int mid;
int first = 0;
while (size > 0) {
half = size >> 1;
mid = first + half;
if (arr[mid] < key) {
first = mid + 1;
size = size - half - 1;
} else {
size = half;
}
}
return first;
}

int main(){
#ifdef debug
freopen("in.txt", "r", stdin);
int START = clock();
#endif
cin.tie(0);
cin.syncwithstdio(false);

dfs(0LL);
sort(L,L+pos);
/*
for(int i=0;icout << i << " " << L[i]<< endl;
*/

int T;
cin >> T;
while(T--){
int l,r;
cin >> l >> r;
LL pos1 = lower_bound(L,pos,l);
LL pos2 = lower_bound(L,pos,r);

LL ans1 = (L[pos1]-l+1)*L[pos1];//��һ����
LL ans2 = 0;
for(int i=pos1;ians2 += (L[i+1] - L[i])*L[i+1];
LL ans3 = (r-L[pos2])*L[pos2];
//cout <//cout << ans1 << " " << ans2 << " " << ans3 << endl;
cout << ans1+ans2+ans3 << endl;
}

#ifdef debug
printf("Time:%.3fs.n", double(clock() - START) / CLOCKSPERSEC);
#endif
return 0;
}

发布评论
  • 点击查看/关闭被识别为广告的评论