[cf] Codeforces Round #793 (Div. 2) B.AND Sorting

前言

t a g : tag : tag: 位运算 &操作 交换 传送门 :

题意 :

给定一个未排序的数组 a [ ] a[] a[],我们需要找到一个最大的 X X X,使得其可以在满足条件的情况下将 a [ ] a[] a[]变为有序

条件 : a [ i ] & a [ j ] = X a[i]\&a[j]=X a[i]&a[j]=X则可以交换

思路 : 因为 & \& &只会把 1 1 1变为 0 / 1 0/1 0/1,不会把 0 0 0变为 1 1 1,所以 & \& &会使得结果越来越小

同样的对于数组中满足任意交换,我们只需要找到一个对于任意的 a [ i ] & a [ k ] = X a[i]\&a[k]=X a[i]&a[k]=X即可

显然 a [ k ] a[k] a[k]一定是最小的那个二进制数,因此我们可以将所有未排序的数对 111111 111111 111111进行 & \& &操作,最

后即可得到最小的二进制数即是答案

特别的 − 1 -1 −1的二进制数正好是 1111111.. 1111111.. 1111111.. code :

int n;
int a[N],b[N];
void solve(){
	cin>>n;
	for(int i=1;i>a[i];
		b[i] = a[i];
	}
	
	int minn = -1;
	sort(b+1,b+1+n);
	
	for(int i=1;i