首页 > 其他分享 >Nim 游戏

Nim 游戏

时间:2023-03-16 21:34:16浏览次数:58  
标签:游戏 puts Nim int res scanf else zero

[acwing]3421.异或数列

/*
    A ^ B = X1 ^ X2 ^ ... ^ Xn
    
    如果结果为 0,说明 A == B,平局
    如果结果不为 0,只需要看结果的二进制形式最高位的 1 是谁拿到的
    
    one[i] 记录所有 X 中位 i 为 1 的个数
    zero[i] 记录所有 X 中位 i 为 0 的个数
    
    从最高位开始遍历
    如果 one[i] 为偶数,那么结果的此位为 0,直接看下一位
    如果 one[i] 为奇数,那么结果的此位为 1,
        如果 one[i] == 1,A 赢,否则
            (手动模拟一下很清晰)
            如果 zero[i] 为偶数,那么 A 赢
            如果 zero[i] 为奇数,那么 A 输
*/
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 20;

int one[N], zero[N];
int T;

void get(int x)
{
    for (int i = 0; i < 20; i++) {
        if (x >> i & 1) one[i]++;
        else zero[i]++;
    }
}

int main()
{
    scanf("%d", &T);
    
    while (T--) {
        memset(one, 0, sizeof(one));
        memset(zero, 0, sizeof(zero));
        int n;
        scanf("%d", &n);
        int res = 0;
        while (n--) {
            int x;
            scanf("%d", &x);
            res ^= x;
            get(x);
        }
        if (res == 0) puts("0");
        else {
            for (int i = 19; i >= 0; i--) {
                if (one[i] & 1) {
                    if (one[i] == 1) {
                        puts("1");
                        break;
                    } else if (zero[i] & 1) {
                        puts("-1");
                        break;
                    } else {
                        puts("1");
                        break;
                    }
                }
            }
        }
    }
    
    return 0;
}

标签:游戏,puts,Nim,int,res,scanf,else,zero
From: https://www.cnblogs.com/cong0221/p/17224225.html

相关文章