宁夏交通建设股份有限公司网站,怎样做推广营销,中国建设银行u盾官方网站,网页制作网页蓝桥杯2021年第十二届省赛真题-异或数列 - C语言网 (dotcpp.com)
题目描述
Alice 和 Bob 正在玩一个异或数列的游戏。初始时#xff0c;Alice 和 Bob 分别有一个整数 a 和 b#xff0c;有一个给定的长度为 n 的公共数列 X1, X2, , Xn。 Alice 和 Bob 轮流操作#xff0…蓝桥杯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的值为0b的值为0现在A可以拿到最后一个1a可以变为1而b为0A获胜。 eg2.如果现在a的值为1b的值为1A拿到最后一个1可以将b的值变为0此时A获胜。 如果x 1那么先手必胜A必胜
如果x 1, 如果y为偶数A必胜A先拿随意给人每次和B对称拿最后A一定拿最后一个1 如果y为奇数B必胜因为第一轮AB都拿变成偶数个0和偶数个1此时A先拿B总能 拿到最后一个1
#includebits/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;
}
