0

我在一次采访中被问到这个问题。问题是这样的

您有一串 '+' 和 '-' （例如 ++----++++++-+--+ ）。有两个玩家玩家 1 和玩家 2。在每一轮，玩家之一可以选择任意两个连续的“+”，即 ++ 并将它们翻转为 -。因此，如果初始字符串是 ++----++++++-+--+ 则玩家有以下 6 个选择 (2 - 7) 。（第一个供参考）。

  1. ++----++++++-+--+
  2. ------++++++-+--+
  3. ++--------++++-+--+
  4. +----+--+++-+--+
  5. ++----++--++-+--+
  6. +----+++--+-+--+
  7. ++----++++---+--+

玩家一一进行。下最后一步的玩家将获胜（或失败 - 没有区别）。

给定一个初始字符串，如果玩家 1 第一轮，我们必须告诉谁赢了？

现在这似乎是一个经典的博弈论问题，每个玩家都试图以最佳方式进行游戏，并且在每一步都采取将他移动到获胜位置的动作。

关于如何解决这个问题的任何想法？

PS - 对方法比对解决更感兴趣。我已阅读http://www.codechef.com/wiki/tutorial-game-theory但无法在这里应用相同的逻辑。

4

1 回答 1

0

我们可以在这里使用 Grundy 函数，因为在将 ++ 转换为 -- 之后，游戏被分为 2 个独立游戏的总和：向左从 -- 和向右。假设 g(l, r) 是给定字符串的 [l, r] 区间的 Grundy 函数的值。为了计算它，我们可以尝试将 ++ 更改为 -- 在所有可能的位置，存储所有 g(l, k - 1) xor g(k + 2, r)（其中 k 是 ++ 开始的位置）值并选择不在其中的最小的非负整数。基本情况的值（当没有可能的移动时）是 0 或 1（取决于最后一个玩家是输还是赢）。当且仅当 g(0, n - 1)(n 是输入字符串的长度) 不为零时，第一个玩家获胜。该解决方案具有 O(n^3) 时间复杂度（有 O(n^2) 可能（l,

于 2014-12-16T09:32:19.203 回答