博弈论好神奇！！！（虽然不会）

[ARC131C] Zero XOR

题目链接

博弈论真是太好了！！！

先观察题目，看完之后思考，思考完之后直接猜一个结论，反正是跟先后手有关，那就根据规则，猜出来一个神奇的结论：

当n为奇数时，先手必胜

手模几组样例之后，发现很对，那为什么这么对呢？接下来是重头戏。

我们考虑当前状态，当堆数为奇数时，我们尝试证明：先手总有一种拿走一堆石子的方式，使后手无论怎么拿，都无法使异或和为0。

如果能够证出这个结论，那最后一堆石子一定是一开始那个先手拿走的，那他就赢了，也就是先手必胜。

下面开始证明：

　　反证法：也就是不存在这么一种方式，我们去尝试推翻他。

　　我们设当前所有数的异或和为 K ,既然不存在这种方式，也就是说，先手无论拿走哪堆，后手都有一种方式，再拿一堆，使异或和为零。（看上去就不对，但有存在的可能性吗，会有巧合吗）

设先手拿走的石子为 a ,后手拿走的为 b,剩下的异或和为 c, 其中 c = 0;

那么：a^b^c=K

那么：a^b=K;

根据题意，每一堆石子的数量不同，也就是说每一个 a 唯一对应一个 b,两两相匹配。

此时你会发现现在的堆数为奇数，总会剩那么一堆，没有其他一堆和他相匹配。

也就是先手可以拿走那个单独的一堆，使后手无论拿走那一堆，都无法使剩下的异或和为零。

然后循环这个操作，最后得出结论：n为奇数时，先手必胜。

那反过来，n为偶数时，一定先手必败吗，答案显然不是，因为可能先手一下就成了，不给后手机会。

如果不是先手一击制胜，那就是先手必败。

#include <iostream>
#include <cstdio>

const int MAXN=4e5+10;

using namespace std;

inline int read() {
    int f=1,x=0;
    char ch=getchar();
    while(ch>'9' || ch<'0') {
        if(ch=='-') {
            f=-1;
        }
        ch=getchar();
    }
    while(ch>='0' && ch<='9') {
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    return f*x;
}

int n;
int a[MAXN],sum;

int main() {
    
    n=read();
    for(int i=1;i<=n;i++) {
        a[i]=read();
        sum=a[i]^sum;
    }
    if(n%2==1) {
        printf("Win\n");
        return 0;
    }
    
    for(int i=1;i<=n;i++) {
        if(a[i]==sum) {
            printf("Win\n");
            return 0;
        }
    }
    
    printf("Lose\n");
    
    return 0;
}

View Code

526互联

博弈论

[ARC131C] Zero XOR