将两个连续的正数转换为负数的游戏

Question

我在一次面试中被问到了这个问题。问题是这样的

你有一串“+”和“-”(例如。++-+- )有两个玩家，玩家1和玩家2。在每个回合中，玩家中的一个可以选择任意两个连续的'+‘，即++，并将它们转换为--。因此，如果初始字符串是++-+-然后播放器有以下6个选项(2-7)。(第一个是供参考的)。

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

这位球员一个接一个地转。最后一步的球员会赢(或者输-不会有什么区别)。

给出一个初始的字符串，如果第一轮是第一轮，我们必须知道谁赢了？

现在，这似乎是一个经典的博弈理论问题，每个玩家都试图发挥最佳的，在每一步发挥一个移动，使他到一个胜利的位置。

对我如何解决这个问题有什么想法吗？

PS -更感兴趣的是方法而不是解决问题。我读过http://www.codechef.com/wiki/tutorial-game-theory，但不能在这里应用相同的逻辑。

Answer 1

我们可以在这里使用Grundy函数，因为在将++转换成-，游戏被分成两个单独的游戏的总和:从左到右。假设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，r)对，我们可以用线性时间计算它们的答案)。