# include <bits/stdc++.h>
using namespace std;
int n;
long long a[1000010];
long long mx = -0x7f7f7f7f;
int main() {
	scanf("%d", &n);
	for (register int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
    }
	sort(a + 1, a + n + 1);
	for (register int i = 1; i < n; i++) {
		for (register int j = i + 1; j <= n; j++) {
			mx = max(mx, a[i] & a[j]);
        }
    }
	printf("%lld", mx);
	return 0;
}

这是一道暴力水题。

我们可以双重循环枚举每一种情况，但是这样会超时。

其实我们只需要枚举前$32$大的数的情况就行了。

证明如下：

1. $int$范围内的非负整数就是$31$为二进制
2. 数学归纳法，下证$k-1$位二进制时前$k$个一定能取到最优$(k\ge2)$.
3. $k=2$时，显然$1$位二进制时前$2$个能取到最优。
4. $k=n$时可以，则$k=n+1$时，如果所有数的最高位都相同则所有数的最高位无关。
5. 由归纳假设，$k-2$位二进制前$k-1$个数必有最优。
6. 如果有至少两个最高位为$1$，至少一个最高位为$0$，则舍弃所有最高位为$0$的数，归入第一类情况，则前$k-1$个必有最优。
7. 如果仅有一个最高位为$1$，其他都为$0$，则舍弃最高位为$1$的数，归入第一类情况，则去掉最大数（最高位为$1$的数）后前$k-1$个必有最优，故前$k$个必有最优。

时间复杂度$O(min(n,32))$。

AC Code

#include<bits/stdc++.h>
using namespace std;
long long a[1000010];
bool cmp(int a,int b)
{
     return a>b;
}
int main()
{
     int n;
     scanf("%d",&n);
     for(int i=1;i<=n;i++)
     {
           scanf("%lld",&a[i]);
     }
     sort(a+1,a+n+1,cmp);
     n=min(n,32);
     long long mx=0;
     for(int i=1;i<=n;i++)
     {
          for(int j=1;j<=n;j++)
          {
              if(i!=j) mx=max(mx,a[i]&a[j]);
          }
     }
     cout<<mx;
     return 0;
}