竞赛讨论区 > 【每日一题】4月6日题目精讲 枚举优化
头像
王清楚
编辑于 2020-04-09 11:54
+ 关注

【每日一题】4月6日题目精讲 枚举优化

题号 NC13221
名称 数码
来源 美团2017年CodeM大赛-资格赛
戳我进入往期每日一题汇总贴~

一切的解题其实都是从最暴力开始的,本题最暴力的方法:先枚举x,然后枚举x的因子,将它们最高位的情况进行统计。

eg:l=3 r=6:
x=3 因子有1 3
x=4 因子有1 2 4
x=5 因子有1 5
x=6 因子有1 2 3 6

为了简化问题,我们可以先求区间[1,r]的答案然后求区间[1,l-1]的答案(这样子不用过于纠结左界的问题,不容易出错)。

观察枚举的过程你可以发现以下几点:

第一,x其实只是一个中间的渠道,我们实际上也并不关心x的值和不同的x对应的因子都有谁,我们要的只有最后的统计结果。

第二,因子都是成对出现的,即x可以表示成 的形式,其中 (完全平方数有一对a=b的情况,后面可能需要特判)。

第三,如果我们固定了 当中的a,那么x在[l,r]的范围内取值时,可以取到的b是连续的,如时,b可以取2,3。

那么我们可以考虑枚举a,计算出b的取值范围:,然后我们可以对b的最高位直接进行统计。

现在问题就变成了,给你一个区间[L,R],问这个区间中的数最高位中1~9每个数码出现的次数。

我们也来看一个例子(不要看不起这种看起来低端的操作,不会的时候尝试手算一个例子是也许会有奇效的。)

L=1,R=317
最高位是1:1,10-19,100-199,共1+10+100个数字;
最高位是2:2,20-29,200-299,共1+10+100个数字
最高位是3:3,30-39,300-317,共1+10+18个数字
最高位是4:4,40-49,共11个数字;
最高位是5:5,50-59,共11个数字;
最高位是6:6,60-69,共11个数字

由此我们可以看到我们只要是按照几位数和最高位是几进行枚举,有多少个这样的数就可以直接统计出来。
具体的操作是:先枚举是几位数num,然后枚举最高位k,这种情况下能取值的范围是区间端点相减加一就是数字个数。
如:R=2333,三位数最高位是2时:左界是200,右界是min(2333,299)=299。这样b的首位为某个数值的个数就求出来了。

而a用了多少个则更简单——就是b的取值范围。

特别注意,算出来左界大于右界的时候说明一个都取不了,直接是0个,不要再去区间端点相减加一算个数了。

但是这里其实还会有一个问题:所有小于的数你会把它当成a算一遍再当成b算一遍,然后就重了,由于有完全平方数的存在,直接除以二其实也不是个特别好的办法,所以实际上b的下界是要从a开始枚举(即保证)就可以了。

算法时间复杂度:

枚举a:

计算对应的b中最高位每个数码出现的次数:

总复杂度:

代码可戳我查看

看完邓老师的题解,记得自己去做题提高呀~
欢迎各位大佬来做题写题解,也欢迎大家踊跃在当日讨论贴中提问!

活动奖励:

在牛客博客中写出题解,并回复地址
审核通过可获得(依据题目难度和题解的内容而定)

本道题目4月13日中午12:00之前写的题解有获得牛币资格~

牛客博客开通方式

  1. 如何开通牛客博客:https://www.nowcoder.com/discuss/202952
  2. 如何使用博客搬家功能:进入博客--->设置--->底部博客搬家
  3. 如果你对牛客博客有任何意见或建议:牛客博客意见反馈专贴

全部评论

(33) 回帖
加载中...
话题 回帖

本文相关内容

等你来战

查看全部

热门推荐