洛谷 P2326 AKN’s PPAP 贪心+位运算

贪心+位运算"/>

洛谷 P2326 AKN’s PPAP 贪心+位运算

题目描述
“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之间有空格

输入输出样例
输入 #1
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
输出 #1
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

前言：首先说一下写这一篇题解的目的是为了解释wwwwth这个大佬的代码，如果侵权，请联系删除

题目大意：给你一列数，让你求出这列数中任意两个数与运算之后最大值

解法：贪心

1. 由于题目中要求最大值，所以我们可以从最高位开始枚举，因为a的最大值只有2的20次方，所以我们从第20位开始向后枚举

2. 对于每个数，如果与当前位与运算后仍然为1，那么我们就把这个数加入一个数组，以后再用那个数组继续枚举

3. 我们需要加入一个条件，如果加入数组的小于2，那么我们就不能用那个数组，因为只有1的数或者没有数，题目中要求至少要两个数合并

4. 如果枚举的当前位有多于两个数存入了新数组，那么我们就把新数组的值赋给原数组继续枚举

5. 最后我们只需要输出原数组第一位和第二位与运算之后的结果即可，因为我们当前求得的已经是最优解

AC代码

#include<cstdio>
#define si 100005
#define re register int
using namespace std;
int T,n,cnt,a[si],b[si];
inline int read() {int x=0,cf=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') cf=-1;ch=getchar();}while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}return x*cf;
}
int main() {T=read();while(T--) {n=read(),cnt++;for(re i=1;i<=n;i++) a[i]=read();for(re k=20;k>=0;k--) {int tp=0;for(re i=1;i<=n;i++) {if(a[i]&(1<<k)) b[++tp]=a[i];}if(tp>1) {for(re i=1;i<=tp;i++) a[i]=b[i];n=tp;}}printf("Case #%d: %d\n",cnt,a[1]&a[2]);}return 0;
}