ARC131C题解

黑部奈叶香 · 2022-12-22 06:35:53 · 题解

结论：当 N 为奇数则先手必胜，否则如果先手第一步能成功则显然先手必胜，剩余情况后手必胜。

证明也很显然：考虑奇数的情况，如果先手第一回合获胜则游戏结束，否则我们需要证明后手一定无法第二回合内获胜。

首先显然由于异或的消去性质，设当前异或为 K ，必须满足对于所有的 i ，都有 K \oplus i \in a 。而由于所有的 a_i 互不相同，则显然这些值两两配对，又由于 n 为奇数，所以总存在一个没有配对的位置，这样后手无法在两步内获胜。

于是先手要么在 n 的时候获胜，要么转移到 n-2 的状态，而 n=1 的时候显然先手获胜，于是先手总是获胜。

回到 n 为偶数，如果先手第一局无法获胜，则后手变为先手， n 变为奇数，则后手显然必胜。

时间复杂度 \mathcal{O}(n) ，可以通过。

代码：

#import<bits/stdc++.h>
using namespace std;
int main() 
{
    int N;
    cin>>N;
    int X=0,A[N];
    for (int i=0;i<N;i++) 
    {
        cin>>A[i];
        X^=A[i];
    }
    if(N&1)
        return !printf("Win\n"); 
    else
        for (int i=0;i<N;i++)
          if(A[i]==X)
            return !printf("Win");
    printf("Lose");
}