LeetCode810. 黑板异或游戏

题意是有一个数组，两个人轮流从中取数，当一个人在要取数时，数组中剩余数的异或值为$0$，则该人获胜。问：给你这个数组，判断先手能否必胜

数据范围 $1 \le N \le 1000,\quad 0 \le nums[i] \le 2^{16}$

这个题很巧妙，乍一看感觉是个博弈论，但是仔细一思考，其实没有那么难。

首先，因为是两个人轮流取数，那么如果刚开始是偶数个数，则每次他取数的时候，数组中都是剩余偶数个数，奇数也同理。那么我们就可以从奇偶性上下手，假设$N$个数的异或值为$S$，若$S = 0$ 则先手直接胜利，若$S \neq 0$，若我们从中取走$nums[i]$之后，剩余数的异或值为$A_i$。当我们任意取走一个$nums[i]$后，$A_i$均为$0$，则说明此时先手必输。

由$A_i \bigoplus nums[i] = S$可推出$A_i = nums[i] \bigoplus S$。

若任意$A_i$均为$0$，那么有$A_1 \bigoplus A_2 \bigoplus … A_n = 0$，即

$nums[1] \bigoplus S \bigoplus nums[2] \bigoplus S \bigoplus… nums[n] \bigoplus S = 0$

$\begin{matrix}N\\\overbrace{S \bigoplus S \cdots\bigoplus S}\\\\\end{matrix} \bigoplus nums[1] \bigoplus …nums[n] = 0 \Longrightarrow \begin{matrix}N + 1\\\overbrace{S \bigoplus …S }\\\\\end{matrix}= 0$

因为$S \neq 0$，故当$N$为偶数时，$N+1$为奇数，此时$N+1$个$S$异或起来必然不为$0$，矛盾。

故而得出结论。当$N$为偶数时，不可能出现不管我们取哪一个数，剩余数的异或值均为$0$的情况。也就是说，当一个人要取数时，此时场上剩下偶数个数，那这个人取完数一定不会输。而结合上文红字，若开局数组中数的个数为偶数，则先手每次取数时，面对的均为有偶数个数的数组，则他必然不会输，及必胜。而当先手面临的是奇数个数时，就说明后手面临的是偶数个数，则后手必胜。但是也有一个特殊情况就是刚开局的时候，虽然数组中有奇数个数，但是他们的异或值为$0$，此时仍是先手胜。

复杂度$O(N)$

#include <bits/stdc++.h>

using namespace std;

void Solve()
{
    int N = 0;
    scanf("%d", &N);

    int *nums = new int[N + 1];
    for (int i = 1; i <= N; i++)
        scanf("%d", &nums[i]);

    if (!(N % 2))
        printf("true");
    else
    {
        for (int i = 2; i <= N; i++)
            nums[1] ^= nums[i];
        printf("%s", (nums[1]) ? "false" : "true");
    }

    delete[] nums;
}

int main()
{
    Solve();

    return 0;
}

使用C#提交至$Leetcode$的方式：

/*
 * @lc app=leetcode.cn id=810 lang=csharp
 *
 * [810] 黑板异或游戏
 */

// @lc code=start
public class Solution
{
    private bool CalcSum(int[] nums)
    {
        for (int i = 1; i < nums.Length; i++)
            nums[0] ^= nums[i];

        return (nums[0] == 0);
    }
    public bool XorGame(int[] nums)
    {
        return (nums.Length % 2 == 0) ? true : CalcSum(nums);
    }
}
// @lc code=end