题目描述
“I have a pen,I have an apple.Eh,Apple-Pen!.
I have a pen,I have pineapple.En,Pineapple-Pen!
Apple-Pen,Pineapple-Pen.Eh,Pen-Pineapple-Apple-Pen!”
Akn最近中毒于一首音乐，于是他买来了一堆苹果来学习这首音乐。Akn发现，只要边唱这首歌，边做把两个完整的苹果碰在一起的动作，两个苹果就会融合成一个新的大苹果，但是大苹果却不能再融合，因为他的细胞内部结构已经改变。Akn还发现，当两个苹果融合的时候，苹果的质量会发生一些玄妙的改变，就是与运算（a&b）。但是，最近他的同学找他要一个苹果吃，akn出于好心，准备把他学习ppap用的苹果融合成的大苹果给同学吃，好让同学一起中毒于ppap，而且akn还想让大苹果的质量最大，那么请问akn能给同学吃的苹果质量最大是多少？
输入输出格式
输入格式：
第一行包含一个整数T，表示数据组数
接下来T组数据，每组数据第一行包含一个整数n，表示n个苹果
第二行包含n个整数wi，表示第i个小苹果重wi kg
输出格式：
每组数据输出一行一个整数大苹果最大的质量，注意格式，Case #x: ans，case和#间有空格，:和ans之间有空格
输入输出样例
3
4
1 3 5 7
10
32 54 21 52 14 25 92 75 14 27
21
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576
Case #1: 5
Case #2: 72
Case #3: 0
说明
由于数据包大小限制，故只上传部分数据（第1,2,3,4,5,6,7,8,10,11,12,13,16,19,20点）
第一组数据解释：
1(2)=1
3(2)=11
5(2)=101
7(2)=111选取5和7进行融合最终得到答案5 数据范围
10%的数据n≤5000，t≤1
另有10%的数据n≤2000，t≤6
另有20%的数据a≤2^10
另有5%的数据n≤10^5，a≤2^20，最大的两个数相等
另有20%的数据n≤10^4，a≤2^15
另有15%的数据n≤10^5，a≤2^20，t≤6
另有15%的数据n≤10^5，a≤2^20，t≤12
100数据n≤10^5，a≤2^20，t≤20
By：worcher
思路：以下是瞎搞AC的，可能是因为数据太水的原因吧。
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 100010
using namespace std;
int t,n,ans,tot;
int num[MAXN];
int main(){
scanf("%d",&t);
while(t--){
tot++;ans=;
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&num[i]);
sort(num+,num++n);
for(int i=;i<n;i++){
ans=max(ans,num[i]&num[i+]);
ans=max(ans,num[i]&num[i+]);
}
cout<<"Case #"<<tot<<": ";
cout<<ans<<endl;
}
}
这是正解：思路就是每次找第k位为1的存入一个数组中，若有多个，则继续找第k+1为1的直到只剩下两个数为止，则这两个数的按位与的答案就是我们所要求的结果。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int t,n,tot;
int a[],b[];
int main(){
scanf("%d",&t);
while(t--){
tot++;
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
for(int k=;k>=;k--){
int top=;
for(int i=;i<=n;i++)
if(a[i]&(<<k)) b[++top]=a[i];
if(top>=){
for(int i=;i<=top;i++) a[i]=b[i];
n=top;
}
}
printf("Case #%d: %d\n",tot,a[]&a[n]);
}
}