- 异或应用3
异或解决异或应用3(非80ac版)
- 2025-2-12 20:32:30 @
相关知识点:
异或 按位与(重点) 数组 循环 输入输出
注:按位与简单介绍
按位与运算是一种基础的二进制运算,它对两个数的二进制表示进行逐位比较,只有在两个相应的二进制位都为1时,结果位才为1,否则为0。
正式开始
思考:分组 假设这两个唯一的数是shu1和shu2。那么整个数组异或后的结果应该是shu1异或su2,因为其他数异或之后会抵消。 又因为两数不一样 且异或结果中二进制位一定有1 所以只要找到shu1和shu2最后一位1在哪就能分组 可以把原数组分成两组。其中一组包含a,另一组包含b。这样,每组中就只剩下一个单独的数,其他的都是可以抵消。然后分别对这两组进行异或,就能得到shu1和shu2了
代码:
#include<bits/stdc++.h>
using namespace std;
unsigned long long a,x[1001]={0},m=0,s;
int res;
signed main(){
cin>>s;
for(unsigned long long i=2;i<=s+1;i++){
cin>>x[i];
res^=x[i];
}//先利用变量result(res)全部异或一遍 此时res=shu1^shu2
int awy=((res)&(0-res/*-res*/));//负数在二进制中是补码表示,这样可以得到最右边的1的位置。
int shu1=0,shu2=0;
for(int i=0;i<1001;i++){//分组
if(x[i]&awy){//x[i]这一位是1
shu2^=x[i];
}
else{//x[i]这一位是0
shu1^=x[i];
}
}
if(shu2>shu1){//排序
cout<<shu1<<" "<<shu2;//输出
}
else{//排序
cout<<shu2<<" "<<shu1;//输出
}
return 0;
}
谢谢观看 点个赞吧
0 comments
No comments so far...
Information
- ID
- 1152
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 8
- Tags
- (None)
- # Submissions
- 142
- Accepted
- 18
- Uploaded By