algorithm - TopCoder 算法问题 - 如何在这个问题上取得进展？

Question

我最近加入了 TopCoder，过去几天一直在练习室练习。我遇到了这个我似乎无法解决的问题。任何帮助将不胜感激。

问题

The product value of a string is the product of all the digits ('0'-'9') in the string. For example, the product value of "123" is 1 * 2 * 3 = 6. A string is called colorful if it contains only digits and the product value of each of its nonempty contiguous substrings is distinct.

For example, the string "263" has six substrings: "2", "6", "3", "26", "63" and "263". The product values of these substrings are: 2, 6, 3, 2 * 6 = 12, 6 * 3 = 18 and 2 * 6 * 3 = 36, respectively. Since all six product values are distinct, "263" is colorful.

On the other hand, "236" is not colorful because two of its substrings, "6" and "23", have the same product value (6 = 2 * 3).

Return the k-th (1-based) lexicographically smallest colorful string of length n. If there are less than k colorful strings of length n, return an empty string instead.

我的方法

我们不能将“0”和“1”作为 n 中的数字。所有数字必须不同。所以首先，n应该小于9。(只能使用数字2、3、4、5、6、7、8、9，每个数字只能使用一次)。

因为我们知道，我们可以从“23”(最小的 2 位彩色字符串)作为基本字符串并添加一个允许的数字(在每次添加时检查字符串是否仍然是彩色的)直到我们达到长度 n。

一旦我们达到长度 n，我们就可以“玩弄”数字以找到最小的 k。

我的问题

我觉得这种方法不够快。即使是，我应该以什么系统的方式来处理这些数字，以便我从最小的开始，一直到第 k 个最小的？

如何使用这种方法在这个问题上取得进展？还是有更聪明的方法来解决这类问题？

我不要求任何解决方案或任何东西。我只是在寻求一些线索和线索。

有些问题我可以在几秒钟内解决，有些需要几个小时的思考，有些像这样我做不到。但我相信这一切都需要一些练习，但如果没有人带路，我就无法取得进步。

提前致谢 =)

*顺便说一句，这个问题来自SRM 464 DIV 2 - 500pt。问题。所有版权归 TopCoder 所有。

Answer 1

Topcoder 有一个论坛，他们在其中为每个 SRM 创建一个线程(464 是 here)。也许您的问题已经在那里得到解答:)