TopCoder算法问题--如何在这个问题上取得进展？
我最近加入了TopCoder，在过去的几天里一直在练习室练习。我遇到了这个我似乎解决不了的问题。任何帮助都将不胜感激。
问题
字符串的乘积值是字符串中所有数字('0'-'9')的乘积。例如，"123“的乘积值为1*2*3= 6。如果字符串仅包含数字，且其每个非空连续子串的乘积值是不同的，则称为彩色字符串。例如，字符串"263“有六个子字符串："2”、"6“、"3”、"26“、"63”和"263“。这些子子的乘积值分别为: 2，6，3，2*6= 12，6*3= 18，2*6*3= 36。由于所有六个产品的价值是不同的，"263“是丰富多彩的。 另一方面，"236“不是彩色的，因为它的两个子字"6”和"23“具有相同的产品价值(6 =2* 3)。返回k(1)字形最小的长度为n的彩色字符串。如果长度小于k个彩色字符串，则返回一个空字符串。
My approach
我们不能用'0‘和'1’作为n中的数字，所有的数字都必须是不同的。因此，首先，n应该小于9。(只能使用数字2、3、4、5、6、7、8、9，每个数字只能使用一次)。
因为我们知道，我们可以从"23“开始(最小的2位彩色字符串)作为基字符串，并添加一个允许的数字(在每个加法上，检查字符串是否仍然是彩色的)，直到我们到达长度n。
一旦我们达到长度n，我们可以“玩”与数字，以找到k-最小。
我的问题
我觉得这样做还不够快。即使是这样，我应该用什么系统的方式来玩数字，这样我才能从最小的开始，通过最小的kth-最小的？
我怎样才能在这个问题上取得进展呢？还是有更明智的方法来解决这类问题？
我没有要求任何解决办法什么的。我只是想要些线索和线索。
有些问题我在几秒钟内就解决了，有些需要花上几个小时的思考，有些像这样的我做不到。但我相信这需要的只是一些练习，但如果没有人带路，我就不可能取得进步。
预先谢谢=)
*顺便问一下，这个问题来自SRM 464 DIV 2-500pt。问题来了。所有版权归TopCoder所有。
回答 4
Stack Overflow用户
发布于 2010-07-20 02:48:35
Topcoder有一个论坛，他们为每个SRM创建一个线程(464是这里)。也许你的问题已经在这里得到了回答:)
Stack Overflow用户
发布于 2010-07-19 21:35:35
我觉得这样做还不够快。
为什么不行？我甚至不会为此“聪明”：你有8个数字，每个数字最多只能一次使用。它的总数为8*7 + 8*7*6 + 8*7*6*5 +. 8*7*6*5*4*3*2*1 = 109592，这对计算机来说是快速的。
将所有这些按字典顺序列举出来，并检查每一个，看看它们是否“丰富多彩”。
Stack Overflow用户
发布于 2010-07-19 21:47:59
减少搜索空间的一种方法是考虑这一点:长度为n的字符串只有在其第一个n-1字符提供的子字符串也是彩色的情况下才能是彩色的。这个断言是正确的应该是相当明显的。
假设您有一个函数colorful(n)，它返回长度为n的所有彩色字符串的集合。可以递归地实现它，如下所示：
colorful(n):
if n = 1:
return { "0", "1", "2", "3", "4", "5", "6", "7", "8", "9" }
def colorful_subs = colorful(n-1)
def colorfuls
for each sub in colorful_subs:
remaining_digits = { 2, 3, 4, 5, 6, 7, 8, 9 } - digits_in(sub)
for each digit in remaining_digits:
if is_colorful(sub, digit):
colorfuls += (sub + digit)
return colorfuls而支持函数is_colorful可以利用这样一个事实，即作为第一个参数提供的子字符串已经被认为是彩色的，并且不包含附加的数字。
然后调用colorful(n)并选择返回集的k第四元素。(请注意，在基本情况下，我们必须包含"0“和"1”，否则n=1会给出错误的答案)
这基本上是一种动态规划方法。我相信这是可以改进的--也许有一种聪明的方法可以找出在一个彩色数字上加上一个特定的数字是否会使这个数字在没有实际操作和检查的情况下就不再是彩色的。但这确实比2-9的所有可能排列数要少得多。
https://stackoverflow.com/questions/3285206
复制相似问题
腾讯云开发者
