前，我在谷歌面试中被问到这个问题，到目前为止，我还没有找到一个好的答案：这是一款 2 人游戏，您将获得一串零和一。在每个回合，玩家可以选择一个 1（或彼此相邻的任意数量的 1）并将其/它们更改为 0/0。将最后 1（或一组 1）更改为 0/0 的玩家是游戏的获胜者。
例如，从0101110开始。第一个玩家有7种可能的动作：
- 0101110 -> 0001110 （第二名玩家可以获胜）
- 0101110 -> 0100 110 （第二名玩家可以获胜）
- 01011 10-> 01010 10（第二名玩家可以获胜）
- 0101110 -> 0101100 （第二名玩家可以获胜）
- 01011 10-> 0100010 （第一个玩家可以获胜）
- 0101110 -> 0101000 （第一个玩家可以获胜）
- 0101110 -> 0100000 （第二个玩家可以获胜）
目标是弄清楚如果你先开始是否有一个成功的策略。我们在这里假设两个球员都是好球员（这意味着他们不会犯错误！
更新：这个游戏与Nim（https://en.wikipedia.org/wiki/Nim）略有不同，对于Nim来说，桩（或堆）的数量在每个回合都保持不变，而在这里，在每个回合，你都可以改变桩的数量。例如，如果我们最初做 01011 10-> 0101010，我们有两堆大小为 1 和 3 的堆，但在移动后我们将有 3 堆大小为 1。
nim[n]成为一系列n的敏捷者。然后，我们有以下递归关系：
nim[n] = mex{nim[i] xor nim[j]: i, j >= 0, i + j < n}
（一般理论见斯普拉格-格伦迪定理。
从这种递归关系中，可以尝试计算序列nim的前几项，你会发现它似乎nim[n] = n。
然后可以很容易地推断出一个证据，我将留给你们。
因此，连续n序列实际上相当于大小为n的尼姆堆。现在很容易找到任何游戏的结果。
例如，如果我们有 0101110 ，那么它相当于两堆 Nim，大小分别为 1 和 3。因此，总 nimber 等于 1 xor 3 = 2 ，即非零，因此第一个玩家获胜。
再举一个例子，如果我们有1110011111000111111，那么总尼姆等于 3 xor 5 xor 6 = 0 ，所以第一个玩家输了。
编辑：至于你关于改变桩的问题，这里有更多的解释。
虽然桩数会发生变化，但关键点如下：
- 如果状态为零 NIMBER 状态，则任何有效移动都必须将其更改为非零 NIMBER 状态。
- 如果状态具有非零 NIMBER 状态，则必须存在有效移动，这会将其更改为零 NIMBER 状态。
因此，对于获胜者来说，策略是将零敏捷状态留给他的对手。
示例：让我们从序列1110011111000111111开始，我简称为3, 5, 6。
如果第一个玩家用2和3的总和替换6，那么第二个玩家将面临状态3, 5, 1, 4，它具有更灵活的3 xor 5 xor 2 xor 3 = 7。为了保持零灵活性，第二个玩家用2替换5，让第一个玩家3, 2, 2, 3，它再次具有零灵活性。
该过程将继续，直到第一个玩家没有有效的移动。
它可以使用图表示来解决。
顶点将是给定二进制字符串/整数与二进制 -> 十进制转换的可能组合。
每个顶点都应该有一个连接到顶点的边，其值可以通过根据游戏规则进行 1 -> 0 转换来获得。
在这种情况下，7 位 => 2^7 = 128 个组合。我们仍然可以过滤掉从给定的初始组合中永远无法到达的顶点。
例如
0101110 -> 0001110 -> 0000000 （第二名玩家获胜）
0101110 -> 0100 110-> 0100000 -> 0000000 （第一个玩家获胜）
事情就这样继续下去。在每次移动中，我们都可以通过获取相邻的顶点来确定下一个可能的组合，它将我们一直引导到获胜的组合 （0000000）