P8245 [COCI2013-2014#3] PAROVI & ZLOJ 练习62 D

· · 题解

一道有趣的计数题。

首先题面中最引人注目的就是两个整数的数据范围。很显然，暴力的思路，枚举所有数，找出每一位上每一种数字的个数这种方法是不可行的。

现在我们来思考一下暴力解法的瓶颈。如果我们延续“找出每一位上每一种数字的个数”这种思路的话，就必须舍去枚举所有数的过程，用高效的方式求解。

先设 f_{x,i} 表示 L ~ R 区间内，第 x 位，数字为 i 的数的个数。一开始想到数位 \texttt{dp}，进而发现该数组显然是满足区间可减性的。所以考虑分开计算两部分，那么重点即在于计算 1 ~ n 中每一位数字为 i 的个数。

一下可能没有什么直观的思路，所以可以模拟一下一些数据观察其特性。这里直接给出结论，当然在此之前强烈建议先自己尝试模拟一下。

对于第 x 位的数，若 n 在这一位上的数字是 s_i，那么对于这一位上的某一种待统计的数字 a：

  1. 若 a\lt s_i，则 cnt=(pre_{i-1}+1)\times 10^{len-i}。

  2. 若 a=s_i，则 cnt=pre_{i-1}\times 10^{len-i}+(suf_{i+1}+1)。

  3. 若 a\gt s_i，则 cnt=pre_{i-1}\times 10^{len-i}。

上述等式中，pre_i 表示首位至第 i 位的所有位的数字顺序排列构成的数，suf_i 表示第 i 位至末位的所有位的数字顺序排列构成的数。

剩下的就是最后统计答案了，求出 f 数组后暴力枚举每一位上的两个数，直接计算即可。

这题的关键在于发现 f 数组的区间可减性。另外，以后看到这种类似的统计数位个数的题就可以直接明确统计思路了，算是总结吧。