蓝桥杯|蓝桥杯2021年第十二届省赛真题-异或数列蓝桥杯|职场和发展

题目 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 #include #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<=0; i--){ int num0=n-num[i]; if(num[i]%2==0){ continue; } else if(num[i]==1){ cout<<1<T; while(T--){ cin>>n; rep(i,1,n){ cin>>x[i]; } solve(); } return 0; }

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