【每日一题】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\times b$ 的形式,其中 $a \leq \sqrt{x}$ （完全平方数有一对a=b的情况，后面可能需要特判）。

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

那么我们可以考虑枚举a，计算出b的取值范围: $[1， \lfloor r/a \rfloor]$ ,然后我们可以对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，这种情况下能取值的范围是 $k \times 10^{num-1}, min(r,(k+1) \times 10^{num-1}-1)]$ 区间端点相减加一就是数字个数。
如：R=2333，三位数最高位是2时：左界是200，右界是min(2333，299)=299。这样b的首位为某个数值的个数就求出来了。

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

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

但是这里其实还会有一个问题：所有小于 $\sqrt{x}$ 的数你会把它当成a算一遍再当成b算一遍，然后就重了，由于有完全平方数的存在，直接除以二其实也不是个特别好的办法，所以实际上b的下界是要从a开始枚举（即保证 $a \times b$ 中 $a\leq b$ ）就可以了。

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

活动奖励：

牛客博客开通方式

全站热榜

创作者周榜

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