20220821模拟赛T1--游戏

【题目描述】一个长度为N的整数数组A。现在希望你找到一对$（i,j）$，满足$i\ne j$
使得$(A_i$ $and$ $A_j)$$xor$$(A_i$ $or$ $A_j)$ 最小。
【输入格式】

第一行一个整数$N$。
第二行$N$个整数，表示数组$A$。
【输出格式】 一行一个整数，为这个最小值。
【数据范围】对于全部数据：$2\le N\le 10^5$ $\forall 1\le i\le N,1\le Ai\le 1000000000$。

给个样例数据吧：

input:
10
41 65 63 49 94 85 95 62 99 67

output:
1

这道有点像思维题了，考察位运算的理解和运用，像俺这种蒟蒻就只能拿for循环暴力分。。。

但是！在考试的过程中，俺也发现了一个规律，如果两个数$a$和$b$满足$a$ $xor$ $b$最小，那么根据异或运算的基本性质可知a和b应该尽量让对应的二进制为尽可能相等，且尽可能在高位相等。

那么我考试的时候就这样了，并没有考虑到后续。

这样的a和b应该满足十进制相差最小。
a和b分别对应着$A_i$ $and$ $A_j$和$A_i$ $or$ $A_j$，要想a和b相差最小，不难得出$A_i$和$A_j$相差最小，于是本题被简化成了入门题（）

代码十分简短：

#include<bits/stdc++.h>
using namespace std;
inline int read(){//快读
    int s=0; bool f=0;
    char c=getchar();
    while(!isdigit(c))  f|=c=='-',c=getchar();
    while(isdigit(c))   s=(s<<1)+(s<<3)+(c^48),c=getchar();
    return f?-s:s;
}
long long a[100010],n,ans=1e10;
int main(){
	n=read();
	for(long long i=0;i<n;i++)
		a[i]=read();
	sort(a,a+n);
	for(int i=0;i<n-1;i++) ans=min(ans,a[i]^a[i+1]);
	cout<<ans<<endl;
	return 0;
}

理解下来这一整道题还是比较简单的，，，（哭了）

呜呜呜呜呜呜呜呜呜呜呜呜