题目描述
- "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% 的数据 n5000,t1
另有 10% 的数据 n2000,t6
另有 20% 的数据 a2^10
另有 5% 的数据 n10^5,a2^20, 最大的两个数相等
另有 20% 的数据 n10^4,a2^15
另有 15% 的数据 n10^5,a2^20,t6
另有 15% 的数据 n10^5,a2^20,t12
100 数据 n10^5,a2^20,t20
By:worcher
一道披着位运算色彩的贪心题目. 开始想先手动模拟一下样例, 第二个数据模拟了好久. win10 自带的计算器是骗子 ==And 运算都是错误, 被这里蒙蔽了好久 ==. 所以还是自己写程序输出二进制数比较好 ==.
开始只能想到 n 方算法, 但是 交上去只有 7 分, 百思不得其解. 觉得应该是找规律的, 最长后缀匹配??
正解: 按位贪心. 因为序列中的数最大为 2^20, 所以从 20 到 0 倒序枚, 找二进制位最高为 1 的数, 然后找次高位为 1 时从是最高位的数中找出, 时间复杂度为 O(20n). 也就是每次都更新序列, 找到可行的, 再从其中计算.
- #include<cstdio>
- #include<algorithm>
- using namespace std;
- typedef long long ll;
- int n,T,ans,cnt;
- int seq[200000],neww[200000];
- int main()
- {
- scanf("%d",&T);
- for(int qwq=1;qwq<=T;qwq++)
- {
- scanf("%d",&n);
- for(int i=1;i<=n;i++) scanf("%d",&seq[i]);
- for(int k=20;k>=0;k--)
- {
- cnt=0;
- for(int i=1;i<=n;i++)
- if((1<<k)&seq[i]) neww[++cnt]=seq[i];
- if(cnt>1)
- {
- for(int i=1;i<=cnt;i++) seq[i]=neww[i];
- n=cnt;
- }
- }
- printf("Case #%d: %d\n",qwq,seq[1]&seq[2]);
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2761408.html