题目链接

幸运数字Ⅱ

思路

首先，不难发现我们可以很轻松地枚举出所有的幸运数字。对于位数，其幸运数字的数量为个，因为每一位要么是，要么是。根据范围，幸运数字的个数约为：，枚举完全OK

按照从小到大枚举出所有的幸运数字之后，以范围中的所有幸运数字为界限，将其分割成多段，那么每段的next值必然相同，避免了重复计算，从而降低时间复杂度

我的分割方法是： 对于范围，找出的下标和的下标。那么，整个数组可以分为如下的几段：

编号	区间	next值
1		arr[idxl+1]
2		arr[idxl+2]
...	...	...
n		arr[idxr]

AC code

#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;

const int N = 1<<12;  // 设置到2e10其实就可以了
ll arr[N+10]; int len = 1;  // 数组长度

void init()  // 初始化操作
{
    arr[0] = 0;
    int idx = 0;
    while( arr[len-1] <= 1e9 ){
        // 如果一个数是幸运数，那么在其后面添上4或者7，这个数还是幸运数（数学归纳法可证）
        arr[len ++] = arr[idx] * 10 + 4;
        arr[len ++] = arr[idx] * 10 + 7;
        idx ++;
    }
    return;
}

int main() {
    init();
    ll res = 0, lt, rt; cin >> lt >> rt;
    int idxl = upper_bound(arr, arr+len, lt) - arr - 1;
    int idxr = lower_bound(arr, arr+len, rt) - arr;
    if( lt == rt ) res = arr[idxr];  // SPJ：只有一个数，没必要计算
    else{
	    for( int i = idxl; i < idxr; i ++ )
	        res += (min(arr[i+1], rt) - max(arr[i], lt-1)) * arr[i+1];
            // lt-1用了一点小技巧，因为只有和lt挂钩的部分才是左闭区间，其余的左区间都是开区间
	}
    cout << res;
    return 0;
}

评价

这道题放在搜索里面不合适，更像枚举+分块，带有一点点的二分