[LeetCode]Chalkboard XOR Game

Game类的题首先想到的就是minmax tree，对于这题来说，我们只有赢还是不赢这一标准。既然两人都是optimal move，对于当前选手a来说，如果存在move m，使得apply m之后，b的任何move都没有办法导向胜利，那么a肯定是可以获胜的。否则，不存在这样的m，代表对于a当前所有的move，b都有办法获得胜利，那么a显然就不可能获得胜利。本质上还是DFS，每个节点对应a或者b的move，自上而下递归即可。我们先求出所有数xor之后的值x，然后每一次抹去一个数num，就相当于在x上在xor num即可。假设输入数组长度为n，时间复杂度O(n!)，相当于枚举所有的排列，但是我们会early cut，所以一般情况并没有这么差。但是可以看到输入数组长度最长可以到1000，我们这个方法肯定是会TLE的，但我们还是给出代码，因为这是解双人游戏题的普遍思路：


一个可能的优化是，因为我们可能有很多相同的数，事实上，不管相同的数有多少个，我们只关心他是奇数个还是偶数个，偶数个相同的数我们可以直接把他们抹掉而不会影响结果，假设值为k的数有偶数个：

1. 抹去偶数个k不会影响所有数xor的结果，也就是说我们起始条件不会变
2. 如果抹去一个k之后，我们剩下奇数个k，xor的结果变成了0。代表除去k外，存在一个集合S = {num1, num2 ...}, S中所有数xor的结果等于k。那么如果我们不抹去k而抹去S中的任何一个数都不会使得结果为0，所以为了不输，就应该永远抹去S中的数而不是k，直到不存在S。那么就变成了情况3
3. 如果抹去一个k之后，我们剩下奇数个k，xor的结果不为0。代表不存在S了，但是这种情况永远会让对手有另外一个k可以抹去，所以我们仍然不应该先去抹k。
4. 所以我们最后会到达剩下偶数个k，并且所有数xor的值为0的情况。那么这偶数个k抹不抹去对结果不会有任何影响

优化之后时间复杂度会变为O(m!)，m代表所有不同的数的数量，testcase还是过不了的，代码如下：

既然仍然是TLE，我们就要考虑一下，是否之前的优化可以让我们导出一些更简单的结论。如果当前玩家a操作的时候，xor的值x不为0，假设当前剩下的总元素为偶数个：

1. 如果x为0，a获胜
2. 如果剩下所有元素相同，同1，a获胜
3. 否则，剩下两个或者两个以上不同的数，我们总可以抹去一个和x不一样的数k，这样剩下的所有数xor的值= x ^ k，是不等于0的
4. 当再回到玩家a的时候，我们仍然可以按照123的条件继续判断，那么a是不可能输的，所以a必胜

所以当满足条件x == 0或者剩下的总元素为偶数个的时候，a必胜。

那么反过来，当x != 0并且剩下总元素有奇数个的时候，a抹去一个数之后，b就永远满足上面所说的1，2，3条件，所以b必胜。那么根据这个结论，我们可以在O(n)的时间判断玩家a是不是可以赢了，代码如下：

如果想verify我们第一种解法的优化结论，也就是说我们只要考虑相同的数有奇数个还是偶数个。我们用第二种写法加第一种解法的优化也是可以AC的，当然这里我们需要遍历两次，实际上更慢了，代码：