蓝桥杯每日一题2023.9.21

蓝桥杯2021年第十二届省赛真题-异或数列 - C语言网 (dotcpp.com)

题目描述

Alice 和 Bob 正在玩一个异或数列的游戏。初始时，Alice 和 Bob 分别有一个整数 a 和 b，有一个给定的长度为 n 的公共数列 X1, X2, · · · , Xn。
Alice 和 Bob 轮流操作，Alice 先手，每步可以在以下两种选项中选一种：
选项 1：从数列中选一个 Xi 给 Alice 的数异或上，或者说令 a 变为 a ⊕ Xi。（其中 ⊕ 表示按位异或）
选项 2：从数列中选一个 Xi 给 Bob 的数异或上，或者说令 b 变为 b ⊕ Xi。
每个数 Xi 都只能用一次，当所有 Xi 均被使用后（n 轮后）游戏结束。游戏结束时，拥有的数比较大的一方获胜，如果双方数值相同，即为平手。
现在双方都足够聪明，都采用最优策略，请问谁能获胜？

分析

分析可知a ^ b = x1 ^ x2 ^ ... ^ xn

从高位向低位看，如果a,b两数相同则异或结果为0，如果a,b两数不同则异或结果为1，最先找到是1的那一方选手获胜。

两人是任意选择异或的数，也就是谁能得到最后一个1谁就可以获胜，eg1.如果现在a的值为0，b的值为0，现在A可以拿到最后一个1，a可以变为1，而b为0，A获胜。 eg2.如果现在a的值为1，b的值为1，A拿到最后一个1，可以将b的值变为0，此时A获胜。

如果x == 1，那么先手必胜A必胜

如果x > 1, 如果y为偶数，A必胜（A先拿随意给人，每次和B对称拿，最后A一定拿最后一个1

             如果y为奇数，B必胜（因为第一轮AB都拿变成偶数个0和偶数个1，此时A先拿，B总能                   拿到最后一个1）

#include<bits/stdc++.h>
using namespace std;
const int N = 22;
int t, n, x, sum;
int main()
{
    cin >> t;
    while(t --)
    {
        cin >> n;
        sum = 0;
        int cnt[N] = {0};
        for(int i = 1; i <= n; i ++)
        {
            cin >> x;
            sum ^= x;
            for(int j = 0; j < N; j ++)
            {
                cnt[j] += x >> j & 1;//将每一位是1的数取出，此位上1的个数+1 
            }
        }
        if(!sum)cout << 0 << '\n';
        else
        {
            for(int i = N - 1; i >= 0; i --)
            {
                if(sum >> i & 1)
                {
                    if(cnt[i] == 1)cout << 1 << '\n';
                    else if((n - cnt[i]) % 2 == 0)cout << 1 << '\n';
                    else cout << -1 << '\n';
                    break;
                }
            }
        }
    }
    return 0;    
}