3

我在这里问这个，因为我在代码厨师论坛上没有得到答案。

在 codechef 的线程。

这是我解决的第一个问题。我收到 TLE 错误。

问题 - ASTRGAME。

所以我最初的方法是创建一个Min-Max 游戏树。这是我最近的解决方案。

伪码算法是：

def recursiveFunction(string, currentTurn):
        for word in dictionary: 
             if word is in string: //use a string matching algorithm
                  remove word from string, and split the remaining string
                  value-a = recursiveFunction(string-a, !currentTurn)
                  if value-a == currentTurn return currentTurn //winning position
                  value-b recursiveFunction(string-b, !currentTurn)
                  if value-b == currentTurn return currentTurn //winning position
                  
        if none of the words in the dictionary are in the string (or none of them are winning positions)
            return !currentTurn   //losing position

（我认为这是正确的）。

所以想法是，它递归地分支出来，但如果它找到一个肯定会获胜的分支，那么它可以跳过该级别的其他分支。

但是，当然，我遇到了 TLE 错误，所以我在这里查看了执行此操作的指南。

社论建议使用Sprague-Grundy 定理。阅读了一些关于使用 SG 定理的内容。几个好的来源 ：一二 。

现在，这两个教程都在 Nim 游戏的背景下讨论 SG 定理。使用 Nim，-我知道您不需要递归地分支树来查找每个游戏的 grundy 数字，您可以从一开始就应用 XOR 函数，并立即解决它。（你不需要为 nim 扩展树的原因是因为你知道一堆 N 个硬币，有一个糟糕的 N - 你通过思考知道这一点 - 例如，一堆 3，扩展可以是一堆2、1还是0，一堆2可以是0、1，一堆1只能变成0，所以1的grundy数是1，2的grundy数是2，3有一个3 的脏数字...）。

同样，对于本教程中提到的马棋游戏，我们可以对棋盘上每个位置的粗略数字进行预处理，并为我们的棋盘配置查找这些粗略数字并应用 XOR 函数。

但是我发现我们如何将其应用于这个问题并不是那么清楚。甚至社论似乎也暗示涉及一些递归：

游戏分为两个子游戏，S(i, a-1) 和 S(b+1, j)。因为玩家可以在他/她的回合中选择任何游戏，所以游戏的 Grundy 数只是两个子游戏的 Grundy 数的 XOR。

即 - 它似乎仍然涉及扩展树直到你找到一个失败的位置，然后传递它。

即是这样的：

 def recursiveFunction(string):
     set = []
     for word in dictionary:
         if word is in string: 
             remove word from string and split the remaining string:
             set.add(recursiveFunction(string-a) XOR recursiveFunction(string-b))
     return mex(set)

我看不出这与 min-max 解决方案有根本的不同。实际上 - 是不是 min-max更快？- 因为 min-max 一旦找到获胜的分支就可以退出，而 SG 需要继续尝试每个单词。

所以，要么我需要澄清我对 SG 定理的使用，要么这只是优化我当前算法的问题。例如，我认为我不需要每次迭代都进行字符串搜索，我可以只存储索引位置。

4

0 回答 0