hihoCoder 1496寻找最大值

描述

给定N个数A₁, A₂, A₃, ... A_N，小Ho想从中找到两个数A_i和A_j(i ≠ j)使得乘积A_i × A_j × (A_i AND A_j)最大。其中AND是按位与操作。  

小Ho当然知道怎么做。现在他想把这个问题交给你。

输入

第一行一个数T，表示数据组数。(1 <= T <= 10)  

对于每一组数据：

第一行一个整数N（1<=N<=100,000）

第二行N个整数A₁, A₂, A₃, ... A_N(0 <= A_i <2²⁰)

输出

一个数表示答案

样例输入 2 3 1 2 3 4 1 2 4 5 样例输出 12 80

在学习了dalao的代码后，才写出来的。并不好表述具体实现，大意是通过枚举(A_i AND A_j）并预先处理出每一个(A_i AND A_j）对应的最大和次大值。

#include<cstdio> #include<cmath> #include<algorithm> #include<vector> #include<map> #include<iostream> using namespace std; typedef long long ll; const int N = (1<<20)+1; int maxn[N],secn[N]; int main() { int t,n; scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i=0;i<N;i++) maxn[i]=secn[i]=0; for(int i=0;i<n;i++) { int in; scanf("%d",&in); for(int i=in;i>0;i=(i-1)&in) //遍历所有in可以出现的 Ai AND Aj 的值，并求出每一个可能的&的结果能形成的最大次大值 { if(in>maxn[i]) { secn[i]=maxn[i]; maxn[i]=in; } else if(in>secn[i]) { secn[i]=in; } } } ll res=0; for(int i=0;i<N;i++) res=max(res,1LL*maxn[i]*secn[i]*i); cout<<res<<endl; } } 关于 i=(i-1)&in：很强，个人感觉编程的魅力很多时候都是在这种地方体现出来。