题目 2605: 蓝桥杯2021年第十二届省赛真题-异或数列

题目描述

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 轮后）游戏结束。游戏结束时，拥有的数比较大的一方获胜，如果双方数值相同，即为平手。
现在双方都足够聪明，都采用最优策略，请问谁能获胜

输入

每个评测用例包含多组询问。询问之间彼此独立。
输入的第一行包含一个整数 T，表示询问数。
接下来 T 行每行包含一组询问。其中第 i 行的第一个整数 ni 表示数列长度，随后 ni 个整数 X1, X2, · · · , Xni 表

输出

输出 T 行，依次对应每组询问的答案。
每行

样例输入

4
1 1
1 0
2 2 1
7 992438 1006399 781139 985280 4729 872779 563580

样例输出

1
0
1
1

提示

【评测用例规模与约定】
对于所有评测用例，1 ≤ T ≤ 200000，1 ≤ ∑Ti=1 ni ≤ 200000，0 ≤ Xi < 220。

题目分析：

首先明确，为什么给定一个数列，游戏的结局是确定的呢？

A赢的意思是：A能采取某种策略，不管B作何应对，A保证自己一定能赢；

B赢的意思是：B能采取某种策略，不管A作何应对，B保证自己一定能赢；

对于异或：0^X ——保持X ； 1^X——翻转X  ;

偶数次翻转将回到原来的状态，即与偶数个1异或将保持不变

首先，最后两个结果数A^B = a^b^sum ,其中sum为给定数列所有数的异或和，sum = X1^X2^...Xni

所以如果是平局，即A = B，则A^B=0，等价于 sum = 0 （输出：“0”）。

现在考虑sum != 0时，因为是按位异或，并且最后比较A和B两值的大小，所以要从高位开始比较，如果最高位相等，比较次高位，以此往下比较。用num[ i ]存储在第 i 位上1的总数量；

先说结论：

如果某一位的num[ i ]为偶数，则游戏结果的这一位一定相等，考虑下一位 ；

如果第i位上1的个数为 1，则一定是先手赢（输出：“1”）；

如果第i位上1的个数为大于1的奇数，0的个数为偶数，则先手赢（输出：“1”）；

如果第i位上1的个数为大于1的奇数，0的个数为奇数，则后手赢（输出：“-1”）；

下面分析原因：

如果某一位的num[ i ]为奇数，即该位上有奇数个1与a和b异或，比如有5个1，因为0不会改变状态,其（a,b）的状态转移过程一定是:

（0，0）->翻转->平局->翻转->平局->翻转，也就是说在平局不管是（0，0）或（1，1）的基础上，Alice 和 Bob谁拥有最后一次翻转权（也就是最后一个1），谁就赢得游戏！

那怎么让最后一个1轮到自己身上？就要用到0了，因为0不会改变数的大小，但相当于让自己“轮空一次”。还是考虑上面5个1的情况：

如果在最后一次翻转之前（不管在什么位置）插入偶数个0，则最后一次1的翻转权来到了先手 Alice，则先手胜出；

如果在最后一次翻转之前（不管在什么位置）插入奇数个0，则最后一次1的翻转权来到了后手 Bob，则后手胜出；

因为Alice和Bob都“足够聪明”，面对奇数个1，Bob一定要去“ 抢0 ”，自己才有一线生机，而Alice也要以“ 抢0 ”来作应对，让最后一次翻转权回到自己手里，奈何0的个数有限，最后决定胜负的就是0个数的奇偶性。

总体而言，这道题目没有考查某种典型的算法或数据结构，但对按位异或的性质和逻辑分析能力有一定要求，测试数据的压力比较大，暴力法还是比较难得分的。

实现代码如下：

//2021省赛G-异或数列 
#include <iostream>
#include <cstring>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define _for(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;const int inf = 0x3f3f3f3f;
const int N = 200000+10;
int T,n,ans,a,b,sum;
int x[N],num[20+5];void count()    //存储各位上1的个数 
{   sum=0;memset(num,0,sizeof(num));rep(i,1,n){int xi=x[i];sum^=xi;int pos=0;  while(xi){if(xi&1) num[pos]++;pos++;xi>>=1; }}
}void solve(){count();if(!sum){cout<<0<<endl;return;}else{for(int i=19;i>=0;i--){int num0=n-num[i];if(num[i]%2==0){continue;}else if(num[i]==1){cout<<1<<endl;return;}else{if(num0%2==0){cout<<1<<endl;return;}else{cout<<-1<<endl;return;}}} }cout<<ans<<endl;
}int main(){cin>>T;while(T--){cin>>n;rep(i,1,n){cin>>x[i];}solve();}return 0;
} 

因为输入数据量大，加上下面语句后速度会快一点：

ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);