异或数列 蓝桥杯2021

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
//
// Created by 86199 on 2022/3/30.
//

//异或数列
//alice和bob最初分别拥有两个数值相同的数，有一个固定大小的数列X[]，
//两人分为先手后手从中选择任意位置上的数Xi与自己的数或者对方的数进行异或，每个位置上的数只能用一次，
//直到X数列中的元素全部用完，数值大的一方获胜，alice胜：1，平手：0，alice负：-1。

/*
 * 分析：
 * alice可进行的操作有（bob同样）：
 * 1 选择一个数对自己当前的数进行异或，使自己当前的数变大
 * 2 选择一个数对bob的数进行异或，使bob当前的数变小
 * 3 alice会怎么选择？由于是最优选择，所以alice肯定会做出操作后与初始值的差值最大的选择
 *
 * 特殊情况：
 * 1 数列中所有数进行异或后结果为0；
 * 导致这种情况有两种情形：
 * 1 数列大小为偶数，且数列中每一个数值的个数为两个，也就是说，数列中数值不同的数的个数为n/2
 * 2 数列大小为奇数，最大偶数个数的情况符合1情形，且多出来的一个奇数为0
 *
 * 对于特殊情况：
 * 如果数列大小为偶数，alice先手选择对自己造成优势最大的数进行异或，或者选择对bob造成劣势最大的数进行异或，
 * 但无论哪种选择，当bob进行后手操作时，都可以选择同样的数进行同样操作，因此当数列全部选完后，alice和bob的数的大小都没有变，平手
 * 如果数列大小为奇数，alice和bob做出和以上的同样的操作，多出来的一个数为0，alice先手操作，任何数与0异或等于本身，平手
 * 因此，当数列的所有数累计异或后结果为0，对弈结果必然为平手
 *
 * 对于普遍情况：
 * 判定规则：如果数列累计异或结果不为0，那么在进行所有异或操作后，结果所对应的二进制数1的位数最高的人获胜
 * 如果将数列中每一个数所对应的二进制数中为1的位进行累加，有以下几种情况：
 * 1 统计所得最高位为1的数的个数只有一个，由于alice是先手，选择这个数对自己或bob操作，后续所有数的这一位都是0，任何数与0异或都等于本身，alice必胜
 * 2 统计所得最高位为1的数的个数为偶数个，alice和bob各选一半对自己或对方进行操作，对于这一位的最终结果alice和bob最终为平手，继续对次一位重复判断，不用进行任何操作
 * 3 统计所得最高位为1的数的个数为奇数个，有两种情况：
 *      ① 数列大小为奇数，那么这一位为0的数的个数为偶数，如果alice和bob都选择先将最高位为1的数选完，alice先手，最后一个高位为1的数属于alice，alice胜；
 *         如果alice先选高位1的数，bob选0，alice也为了拿到最后一个高位数跟着选0，由于为0的个数为偶数，bob先选所以bob先选完，不得不开始选高位为1的数，
 *         由于开始已经拿了一个，这时候高位1的个数为偶数，最后一个属于alice，alice胜；
 *         也就是说，这种情况下，只要alice先选高位1，无论bob先选高位1还是高位0都必输
 *         由于alice会做出最优决策，所以alice必胜；
 *
 *      ② 数列大小为偶数，那么这一位为0的数的个数为奇数，alice先手，如果alice先选高位1，为了确保能拿到最后一个高位1，bob不会跟着选，而是先选高位0，
 *         alice不可能继续选高位去创造bob的优势或者减小自己的优势，只能跟着选高位0，结果最后一个高位0必属于bob，alice只能选高位1，bob胜
 *         如果alice先选高位0，bob选高位1，alice接下来不可能选高位1，只能将高位0选完，最后一个属于bob，alice只能选高位1，bob胜
 *         也就是说，这种情况下，只要bob第一次后手先选0，无论alice先手选的高位1还是高位0都必输
 *         由于bob会做出最优决策，所以bob必胜*/

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

void bitCount(int *res, int bit[], int length);

void gamingRes(int res, const int *bit, int length, int n);

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int length;
        cin >> length;
        int res = 0;
        int *bit = new int[22];
        memset(bit, 0, sizeof(*bit));
        bitCount(&res, bit, length);
        gamingRes(res, bit, 20, length);
    }
    return 0;
}

void bitCount(int *res, int bit[], int length) {
    for (int j = 0; j < length; j++) {
        int x;
        cin >> x;
        *res ^= x;
        int index = 1;
        while (x > 0) {
            if ((x & 1) > 0) {
                bit[index]++;
            }
            x >>= 1;
            index++;
        }
    }
}

void gamingRes(int res, const int *bit, int length, int n) {
    if (res == 0) {
        cout << 0 << endl;
    } else {
        for (int i = length; i > 0; i--) {
            if (bit[i] == 1) {
                cout << 1 << endl;
                break;
            }
            if ((bit[i] & 1) == 1) {
                if ((n & 1) == 1) {
                    cout << 1 << endl;
                    break;
                } else {
                    cout << -1 << endl;
                    break;
                }
            }
        }
    }
}