【题目描述】
给定 n 个数,找出两个,使得它们经过与运算后结果最大。
注意,选出来的两个数在原数组中的位置不能一样,但是数值可以一样。
【输入格式】
第一行一个整数 n,表示数字个数。
第二行 n 个数,表示给定的数。
【输出格式】
一个整数表示答案。
【样例输入】
3
1 2 1
【样例输出】
1
【数据范围】
对于 20%的数据点,n <= 1000
对于另外 20%的数据点,只有 0 和 1
对于 100%的数据点,n <= 100000, 0 <= 数值 <= 10^9
从高位到低位贪心枚举每个数的二进制位选取当前位是 1 的数加入集合,剔除当
前位是 0 的数(所有数是 0 的话,就得全部保留),最后的数与运算结果最大。
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 typedef long long ll; 7 ll a[100005],n,ans,cnt,pw[41],del[100005]; 8 int main() 9 {int i,flag,j; 10 cin>>n; 11 pw[0]=1; 12 for (i=1;i<=40;i++) 13 pw[i]=pw[i-1]*2; 14 for (i=1;i<=n;i++) 15 { 16 scanf("%lld",&a[i]); 17 } 18 for (i=41;i>=0;i--) 19 { 20 int cnt=0; 21 for (j=1;j<=n;j++) 22 if (del[j]==0&&(a[j]&pw[i])) cnt++; 23 if (cnt<=1) continue; 24 ans+=pw[i]; 25 for (j=1;j<=n;j++) 26 if (del[j]==0&&(a[j]&pw[i])==0) del[j]=1; 27 } 28 cout<<ans; 29 }