Hackerrank 有一个称为十进制数的问题,它本质上是具有 0-9 位数值的数字,但使用 2 的幂进行幂运算。问题要求我们显示第 x 个十进制数。这个问题还有另一个转折点。多个十进制数可以等于同一个十进制数。例如,十进制的 4 可以是十进制的 100、20、12 和 4。
起初,我认为找出给定十进制数有多少个十进制数会很有帮助。我查阅了这篇文章以获得一些帮助(https://math.stackexchange.com/questions/3540243/whats-the-number-of-decibinary-numbers-that-evaluate-to-given-decimal-number)。这篇文章有点难以理解,但后来我也意识到,即使我们有一个十进制数可以有多少个十进制数,这也无助于找到它们(至少据我所知),这是最初的目标问题。
我确实意识到,对于任何十进制数,它的最大十进制数只是它的二进制表示。例如,对于 4,它是 100。因此,蛮力方法是检查每个十进制数在此范围内的所有数字,看看它们的十进制表示是否计算为给定的十进制数,但很明显,这种方法永远不会由于输入约束将 x 定义为从 1 到 10^16,因此通过。不仅如此,我们还必须为 aq 数量的查询找到第 x 个十进制数,其中 q 从 1 到 10^5。
这个问题属于 dp 部分,但我很困惑如何使用 dp 或者它是如何可能的。为了计算第 x 个十进制数 q 次(在上面的蛮力方法中进行了描述),最好使用一个表格(就像问题所暗示的那样)。但为此,我们需要存储和计算 10^16 个整数,因为这就是 x 的大小。假设一个整数是 4 字节,4B * 10^16 ~= 4B * (2^3)^16 = 2^50 字节。
有人可以解释一下如何以最佳方式解决这个问题。我还是 CP 的新手,所以如果我在某些方面犯了错误,请告诉我。
(有关完整的问题陈述,请参见下面的链接): https ://www.hackerrank.com/challenges/decibinary-numbers/problem