4

这个问题真的让我很困惑；给定两个整数A , B，我们想计算[A, B]范围内数字的出现次数。我认为，如果我们可以计算[0, A]和[0, B]范围内的数字出现次数，那么剩下的就很简单了。那么如何计算[0, x]范围内的数字出现次数？这不是作业，这实际上是 SPOJ 的问题。天真的方法行不通，因为 A 和 B 可以大到 10 ^ 9。这里有一些例子：

输入：

1 10

输出：

1 2 1 1 1 1 1 1 1 1

输入：

44 497

输出：

85 185 185 185 190 96 96 96 95 93

4

3 回答 3

9

我会先尝试蛮力方法来使某些东西起作用。查看每个数字，遍历该数字的字符串表示中的每个字符，等等。

但是，有一种更简单的方法。

  • 在区间[0,9]中，3出现了1次
  • 在区间[0,99]中，3在第一位出现10次，在第二位出现10次
  • 在区间 [0,999] 中，3 在第一位出现 100 次，在第二位出现 100 次，在第三位出现 100 次。

您可以对此进行概括，并通过一些努力得出一个公式，以确定某个数字（0 是可能的特殊情况）将出现在某个范围内的数量。您不需要实际检查每个数字。

于 2011-07-08T20:33:35.787 回答
1

Wolfram Alpha 是你的朋友（至少在 21 * 10^4 附近的某个数字上）： 

Input:

44 497

Output:

85 185 185 185 190 96 96 96 95 93

试试我

结果：

{85、185、185、185、188、96、96、96、95、93}

于 2011-07-08T22:13:15.137 回答
-1

对于这类问题，在确定如何正确快速地完成之前，从一个缓慢而丑陋的实现开始通常很有用。您可能会了解问题的结构，并且可以使用慢速实现来测试快速实现的正确性。

例如，在 Python 中，您可能会像这样编写慢速版本（这不一定是最好的方法，但它是最短的……）

>>> A, B = 1, 100
>>> from collections import Counter
>>> Counter(''.join(map(str, range(A, B + 1))))
Counter({'1': 21, '3': 20, '2': 20, '5': 20, '4': 20,
         '7': 20, '6': 20, '9': 20, '8': 20, '0': 11})
于 2011-07-08T21:09:29.810 回答