Problem Description
Given an array of n non-negative integers: A1, A2, …, AN. Your mission is finding a pair of integers Au, Av (1 ≤ u < v ≤ N) such that (Au and Av) is as large as possible.
And is a bit-wise operation which is corresponding to & in C++ and Java.
Input
The first line of the input contains a single integer N. The ith line in the next N lines contains the Ai.
Output
Contains a single integer which is the largest value of Au and Av where 1 ≤ u < v ≤ N.
Constraints
50 points:
2 ≤ N ≤ 5000
0 ≤ Ai ≤ 109
50 points:
2 ≤ N ≤ 3 × 105
0 ≤ Ai ≤ 109
Example
Input:
4
2
4
8
10
Output:
8
Explanation
2 and 4 = 0
2 and 8 = 0
2 and 10 = 2
4 and 8 = 0
4 and 10 = 0
8 and 10 = 8
题解
首先感谢lwher，是他让我真正领会到“正难则反”的妙用。
这道题在codechef上的数据太水了，竟然排序后只算a[i]&a[i-1]都能过！在这里给出反例，如/0011/0100/1011。
显然50分的暴力人人都会……可是我们并不能找到一种行之有效的方法去优化暴力。这时候，我们就可以想想“反过来做”：对于我们要的答案（看成2进制），一定是“每个位置不是1就是0，且越高位有1越好”（显然100比011大），那么怎么才能确定这位是否能是1呢？显然：当至少2个数这一位有1即可。所以算法如下：
我们一位一位确定答案，从高位开始。每次在现有的数里面for一遍，把这位为1的拿出来。如果个数为2个或以上，那么这一位是1，否则是0。如果是1，那么现有的数就变成我们上次拿出来的那些。复杂度 nlogK。K为数值范围
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int n,a[300002],d[35],ans;//2^30>1000000000
void init()
{
scanf("%d",&n);
int i;
for(i=1;i<=n;i++) scanf("%d",&a[i]);
}
void find()
{
int i,j,ct,now=n,t;
for(i=30;i>=0;i--)
{ct=0;
for(j=1;j<=now;j++)
{if(a[j]&(1<<i)) ct++;}
if(ct<2) continue;
t=0; d[i]=1;
for(j=1;j<=now;j++)
{if(a[j]&(1<<i)) a[++t]=a[j];}
now=t;
}
for(i=30;i>=0;i--)
{if(d[i])
ans=ans^(1<<i);
}
printf("%d\n",ans);
}
int main()
{
init(); find();
return 0;
}