leetcode-810-黑板异或游戏

黑板异或游戏

题面

leetcode题目

黑板上写着一个非负整数数组 nums[i] 。Alice 和 Bob 轮流从黑板上擦掉一个数字，Alice 先手。如果擦除一个数字后，剩余的所有数字按位异或运算得出的结果等于 0 的话，当前玩家游戏失败。 (另外，如果只剩一个数字，按位异或运算得到它本身；如果无数字剩余，按位异或运算结果为 0。）

并且，轮到某个玩家时，如果当前黑板上所有数字按位异或运算结果等于 0，这个玩家获胜。
假设两个玩家每步都使用最优解，当且仅当 Alice 获胜时返回 true。

example

输入：nums = [1, 1, 2] 输出：false

题解

总体思路

博弈题，推结论还蛮麻烦的。

解题思路

参考了 题解

博弈一般可以先考虑是否存在必败态，定义由必败态走的每一步都会转移到必胜态，由必胜态存在走到必败态的可能。因为必胜态的转移是可能性，必败态的转移是固定的，所以一般从必败态开始考虑。
这个题首先考虑，假设输入已经是异或和为0时，则已经处于必胜态。
假设异或和不为0，那么考虑假设处于必败态，则当前任意去掉任何一个值，剩余的异或和都为0。因为去掉一个值也可以看作异或掉这个值，即可表达为: \[ sum \oplus a_{i} = 0 \] 其中\(sum\)为去掉前的异或和。
由于\(0 \oplus x = x\) 则可以展开上式为: \[ (sum \oplus a_0) \oplus (sum \oplus a_1) \cdots \oplus (sum \oplus a_k) \cdots \oplus (sum \oplus a_{n-1}) = 0 \] 异或具有结合性，可以将上式写作: \[ (sum \oplus sum \cdots \oplus sum) \oplus (a_0 \oplus a_1 \cdots \oplus a_k \cdots \oplus a_{n-1}) = 0 \] 即: \[ (sum \oplus sum \cdots \oplus sum) \oplus sum = 0 \] 由于\(sum \neq 0\) 我们可以推出当前有奇数项(左边的异或和中的每一项\(sum\)都是与原式子中的某一项进行异或时提取出来的，左边有多少项原式就有多少项)，也就是处于必败态时操作前有奇数项，于是可以反推，当有偶数项时，处于必胜态。

代码

#include <iostream>
#include <vector>
#include <set>
//#define _DEBUG
using namespace std;
class Solution
{
public:
    bool xorGame(vector<int> &nums)
    {
        int sum = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            sum ^= nums[i];
        }
        if (sum == 0)
            return true;

        int count = nums.size();
        if (count % 2 == 0)
        {
            return true;
        }
        return false;
    }
};

// for test
int main()
{
    Solution s;

    return 0;
}