本文主要是介绍【NC15291】幸运数字Ⅱ,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目
幸运数字Ⅱ
枚举,分块
思路
由题意可知在范围 [ 1 , 1 0 9 ] [1,10^9] [1,109] 内的幸运数字个数其实是很少的,这可以通过枚举得到,枚举又可分为递归和迭代,这里由于只有两种数字 4 , 7 4,7 4,7,恰好对应二进制的 0 , 1 0,1 0,1,所以通过迭代法来枚举比较合适。枚举之后会得到一个幸运数字数组 r e s res res,这里面从小到大地存放了在范围 [ 1 , 1 0 9 ] [1,10^9] [1,109] 内的幸运数字。
但是题目要求的并不是幸运数字本身,而是给定 l , r l,r l,r,求出 n e x t ( l ) + n e x t ( l + 1 ) + . . . + n e x t ( r − 1 ) + n e x t ( r ) next(l) + next(l + 1) + ... + next(r - 1) + next(r) next(l)+next(l+1)+...+next(r−1)+next(r)
可以知道,如果某个数 x x x 落在了幸运数区间 [ a , b ] [a,b] [a,b] 中,那么 n e x t ( x ) + ⋯ + n e x t ( b ) = ( b − x + 1 ) ∗ b next(x)+\dots+next(b)=(b-x+1)*b next(x)+⋯+next(b)=(b−x+1)∗b,实质上这些幸运数将 n e x t ( l ) + n e x t ( l + 1 ) + . . . + n e x t ( r − 1 ) + n e x t ( r ) next(l) + next(l + 1) + ... + next(r - 1) + next(r) next(l)+next(l+1)+...+next(r−1)+next(r) 分成了多个块,我们只需要枚举每个块,然后利用乘法即可计算出结果。
不幸的是这道题并没有要求对结果取模,所以答案可能很大(超出了长整型)。
如果使用 c / c + + c/c++ c/c++ 的话,需要手动模拟大整数的乘法和加法,实在太烦。为了方便,这里使用 P y t h o n Python 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】幸运数字Ⅱ的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!