【思路】
初始时A和B都为0, 由异或的性质最终 $A \bigoplus B = X_1 \bigoplus X_2 \bigoplus X_i…$
如果所有$X$异或的结果为0,那么说明最终的A 和 B 是相同的,直接输出平局$0$。
如果要使得最终结果最大,那么肯定优先选最高位的1,我们记录每一位上1
出现的次数
由于异或中:与 1 异或是取反,与 0 异或不变,
当某一位的num[i]
为偶数,则游戏结果的这一位一定相等,直接看下一位出现的次数
如果num[i]
的个数为1,则一定是先手赢(抢了1之后,就没有1了|只有A最高位变成了1)
那么当num[i]
为大于1的奇数, 0的个数为偶数,则先手赢
当num[i]
为大于1的奇数, 0的个数为奇数,则后手赢
#include<iostream>
#include<cstring>
using namespace std;
const int N = 22;
int num[N]; // 记录每一位出现1的次数
void get_cnt(int n) {
int cnt = 1;
while(n) {
if(n & 1) num[cnt]++;
cnt++;
n >>= 1;
}
}
int main() {
int n;
cin >> n;
while(n--) {
memset(num, 0, sizeof num);
int k, sum = 0;
scanf("%d", &k);
for(int i = 0; i < k;i++) {
int s;
scanf("%d", &s);
get_cnt(s); // 记录num数组
sum ^= s;
}
if(!sum) puts("0");
else {
for(int i = 20; i >= 1;i--) {
if(num[i] == 1) {
puts("1");
break;
}else if(num[i] & 1) { // 1的个数为奇数
if(k % 2 == 0) {puts("-1"); break;} // 0的个数是奇数
else {puts("1"); break;} // 0的个数是偶数
}
}
}
}
return 0;
}
有人试过
1
6 1 1 1 1 1 0
这个数据吗
大佬厉害
嘎嘎牛
太妙了
牛,看到本质了
蓝桥官网时间超限83%
我交了一次能全部通过呀
你复制到c语言网上的蓝桥题库里交一下,里面的那一篇题解和这个方法一模一样也是超限83%
好的,那个我没试,我以为你说的是https://www.lanqiao.cn/cup这个
这个题目要是能在比赛里20分钟内想出来,怎么样都能拿个奖,毕竟20分的题目
不懂啊,我的觉得奇数个0 先手才能赢啊,为啥是偶数个
我的理解是这样,比如7个数,3个1,4个0,我先抢个1,然后分三种情况,第一种,对面选择1,那我直接给对面安排一个1.第二种,对面给我安排1,那我继续选1.第三种,如果对面选0或者给我安排0,我相应的选0就行,最后他只能选1.总之,我会一直卡死他
之前看错题目了!我之前以为和下棋一样是两个人抢这几个数字,原来还可以给对面安排!😂
为什么可以给对面安排?不是每一方都是选择对自己最有利的情况吗
就是因为选对自己最有利的,所以才会剩下差的留给对方,所以相当于给对方安排了
所有数中同一最高位的0的个数
你好,这里说的0的个数是什么意思?当前这位的0的个数吗?为什么0的个数为奇数个的话,后手赢呢?
因为1的个数是奇数0的个数是偶数的话,我先拿一个1,然后无论对面拿什么,我都拿和他一样的,这样总能保持我是1而他是0,由于1和0个数都是偶数(1已经被我先拿一个),则最终所有的0和1都能被凑对,导致对手肯定会被我限制成0。但是如果是1个数奇数0的个数也是奇数,那么无论我怎么拿,对手都可以采取上述的策略来限制我,此时的我就像是上诉的对手一样,无论怎么拿,对手都能拿到和我一样的来限制我,最终对手可以保证他一定是1
醍醐灌顶