蓝桥杯2021年第十二届省赛真题-异或数列 - C语言网 (dotcpp.com)https://www.dotcpp.com/oj/problem2605.html
先手胜输出1,平局输出0,先手败输出-1;
A和B起始值都是0;
两人数字相同时,即A^B=0时平局;
首先0^1=1,0^0=0,1^1=0,A^B=X1^X2^……^Xn;
故平局时,X1^X2^……^Xn=0;
谁数字大就赢,也就是当A和B(二进制)从高到低有一位不同时,是1的那个人赢;
用num数组统计X1……Xn每一位为1的次数;
例如,4(100),6(110),5(101),这3个数统计后,num[3]=3,num[2]=1,num[1]=1;
当最高位为1的个数为奇数且n为偶数时,先手赢;
例如最高位1出现3次(A,B,C),n=5;
先手拿A与自己的值异或,最高位是1;
接着 , 1.后手拿B与自己的值异或,先手拿C与后手的值异或,后手最高位为0,先手胜;
2.后手拿最高位0与自己的值异或,先手拿另一个最高位0与自己的值异或,回到1;
同时,当最高位为1的个数为奇数且n为奇数时,后手赢;
区别就是上面2的情况先手没有0的值拿,于是和后手交换了拿最高位为1的数的顺序;
由此推之,当最高位为1的个数为偶数时,看次高位,次高位为1个数是偶数,看次次高位……
#includeusing namespace std; // A和B初始的数值都是0。 int num[23]; long long a; void pre(long long a) { int cnt=1; while(a){ if(a&1)num[cnt]++; cnt++; a>>=1; } } int main() { int T; ios::sync_with_stdio(0);cin.tie(0); cin>>T; while(T--){ memset(num,0,sizeof(num)); int n,sum=0; cin>>n; for(int i=0;i >a; pre(a); sum^=a; } if(!sum)puts("0"); else{ for(int i=20;i>0;i--) if(num[i]==1){puts("1");break;} else if(num[i]%2==1){ if(n%2==1){puts("1");break;} else if(n%2==0){puts("-1");break;} } } } return 0; }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)