反nim博弈

Xyan_ · 2020-08-25 09:39:15 · 个人记录

反nim博弈

反nim博弈的自我口嗨证明

当全部石子堆石子个数都为1时，即可根据奇偶确定是否必胜

当存在一个及以上石子堆个数不为1，

若异或和为0，则代表二进制1的数量是"那种"偶数，那么就可以确定，先手必败，因为普通nim前人操作后人模仿，因为是偶数，所以后手凉凉。现在反nim游戏，前人操作，后人模仿，但是后手第一次留了一手，少拿一手，这样给前人留了一个，那样就前人拿最后一个，后手必胜。

否则异或和不为0，总有一种小于a[i]的操作使得异或和为0，就不老生常谈了。

#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;
int a[49];
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int num = 0;
        int nim_sum = 0;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            nim_sum ^= a[i];
            num += (a[i] == 1?1:0);
        }
        cout << (num == n ? (num % 2 ? "Brother\n": "John\n" ) : (nim_sum?"John\n":"Brother\n"));
    }
}