AOJ 840.下一个幸运数|OhYee 博客

这是一篇最后编辑于 8 年前的文章，其内容可能与目前实际情况差异较大，请注意甄别

题目

{% raw %}

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

{% raw %}

{% endraw %}

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

{% raw %}

{% endraw %}

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

{% raw %}

{% endraw %}

3
4 4
3 4
4 7

{% raw %}

{% endraw %}

4
8
25

{% raw %}

{% endraw %}

题解

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

最后测试的时候,应该对于 l 和 r 都测试下比幸运数小 1 大 1 相等的情况
也即最后测试 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++] = t10+4;
L[pos++] = t10+7;
dfs(t10+4);
dfs(t10+7);
}

LL lower_bound(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.sync_with_stdio(false);

dfs(0LL);
sort(L,L+pos);
/*
for(int i=0;i<pos;i++)
    cout << 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;i<pos2;i++)
        ans2 += (L[i+1] - L[i])*L[i+1];
    LL ans3 = (r-L[pos2])*L[pos2];
    //cout <<pos1<<" "<<pos2<<endl;
    //cout << ans1 << " " << ans2 << " " << ans3 << endl;
    cout << ans1+ans2+ans3 << endl;
}

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

}

</div>

推荐订阅源

OhYee 博客

题目

题解

代码