【NC15291】幸运数字Ⅱ

本文主要是介绍【NC15291】幸运数字Ⅱ，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

幸运数字Ⅱ

枚举，分块

思路

由题意可知在范围 $[1,10^9]$ 内的幸运数字个数其实是很少的，这可以通过枚举得到，枚举又可分为递归和迭代，这里由于只有两种数字 $4,7$，恰好对应二进制的 $0,1$，所以通过迭代法来枚举比较合适。枚举之后会得到一个幸运数字数组 $res$，这里面从小到大地存放了在范围 $[1,10^9]$ 内的幸运数字。

但是题目要求的并不是幸运数字本身，而是给定 $l，r$，求出 $next(l)+next(l+1)+...+next(r-1)+next(r)$

可以知道，如果某个数 $x$ 落在了幸运数区间 $[a,b]$ 中，那么 $next(x)+\cdots +next(b)=(b-x+1)\ast b$，实质上这些幸运数将 $next(l)+next(l+1)+...+next(r-1)+next(r)$ 分成了多个块，我们只需要枚举每个块，然后利用乘法即可计算出结果。

不幸的是这道题并没有要求对结果取模，所以答案可能很大（超出了长整型）。

如果使用 $c/c++$ 的话，需要手动模拟大整数的乘法和加法，实在太烦。为了方便，这里使用 $Python$。

代码

res = []# 获取所有幸运数字
def get_fnums():for i in range(1, 12):for j in range(0, 1 << i):t = 0for p in range(0, i):if (j >> p) & 1:t = t * 10 + 7else:t = t * 10 + 4res.append(t)def solve(l, r):get_fnums()res.sort()ans = 0j = 0# 首先找到第一个大于等于l的幸运数字，可以用二分，但意义不大for i in range(0, len(res)):if res[i] >= l:j = ibreak# 如果l,r属于同一个块，则需要特殊处理if r <= res[j]:return (r - l + 1) * res[j]# 如果不是同一个块，则需要累加多个块ans += (res[j] - l + 1) * res[j]for i in range(j + 1, len(res)):if res[i] < r:ans += (res[i] - res[i - 1]) * res[i]else:ans += (r - res[i - 1]) * res[i]breakreturn ansif __name__ == "__main__":tmp = input().split(" ")print(solve(int(tmp[0]), int(tmp[1])))

这篇关于【NC15291】幸运数字Ⅱ的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---