【题目链接】 https://hihocoder.com/problemset/problem/1496
【题目大意】
给定N个数A1, A2, A3, ... AN,
从中找到两个数Ai和Aj(i≠j)使得乘积Ai*Aj*(Ai&Aj)最大
【题解】
我们可以枚举x&y的结果z,找出两个数x&y==z使得x*y最大,更新答案即可,
条件可以被削弱为z为x&y的子集,这种条件放缩不会导致最优解的丢失,
z为x&y的子集等价于z为x的子集并且z为y的子集。
那么我们只要找出以z为子集的最大值和次大值,然后枚举z即可计算出答案。
复杂度O(k*2^k).
【代码】
#include <cstdio>
#include <algorithm>
using namespace std;
struct data{
int val[2];
data operator +(const data &rhs)const{
int t_val[2]={val[0],val[1]};
for(int i=0;i<2;i++){
if(rhs.val[i]>t_val[0]){
t_val[1]=t_val[0];
t_val[0]=rhs.val[i];
}else if(rhs.val[i]>t_val[1])t_val[1]=rhs.val[i];
}return data{t_val[0],t_val[1]};
}
}dp[(1<<20)+10];
int T,n;
int main(){
scanf("%d",&T);
int all=1<<20;
while(T--){
for(int i=0;i<all;i++)dp[i]=data{0,0};
scanf("%d",&n);
for(int i=1,x;i<=n;i++){
scanf("%d",&x);
dp[x]=dp[x]+data{x,0};
}
for(int i=0;i<20;i++)
for(int j=0;j<all;j++)
if(~j&(1<<i))dp[j]=dp[j]+dp[j|(1<<i)];
long long ans=0;
for(int i=0;i<all;i++)ans=max(ans,1LL*i*dp[i].val[0]*dp[i].val[1]);
printf("%lld\n",ans);
}return 0;
}
hihocoder 1496 寻找最大值(高维前缀最大次大值)的更多相关文章
-
Hihocoder 1496 寻找最大值(状态压缩 + 高位前缀和)
题目链接 Hiho 1496 设$f[i]$为二进制集合包含$i$的最大的两个数,这个东西用高维前缀和维护. 高位前缀和转移的具体方案 :枚举每一位,然后枚举每个集合,大的转移到小的. 注意合并的时 ...
-
hihocoder 1496 寻找最大值
题解: 注意到$ai$只有$1e6$这件事情肯定要枚举和这个有关的东西 考虑枚举$ai\&aj$的值就可以了 那么这个集合一定是ai,aj的子集 于是我们对每个集合从大到小枚举丢掉一位转移就行 ...
-
HihoCoder 1496:寻找最大值(思维DP)
http://hihocoder.com/problemset/problem/1496 题意:中文. 思路:一开始做有一种想法,把所有的数都变成二进制后,最优的情况肯定是挑选所有数中最高位的1能同时 ...
-
MATLAB寻找数组前k个大值
有时候我们需要寻找数组的前k个大值并按照顺序输出, 在C语言可以通过快速排序等算法,快速求得,这里用matlab写了一个比较简单实用的程序(适用于数组长度不是特别大的情况). function [va ...
-
HihoCoder - 1496:寻找最大值(高维前缀和||手动求子集)
描述 给定N个数A1, A2, A3, ... AN,小Ho想从中找到两个数Ai和Aj(i ≠ j)使得乘积Ai × Aj × (Ai AND Aj)最大.其中AND是按位与操作. 小Ho当然知道怎么 ...
-
LOJ2542 PKUWC2018 随机游走 min-max容斥、树上高斯消元、高维前缀和、期望
传送门 那么除了D1T3,PKUWC2018就更完了(斗地主这种全场0分的题怎么会做啊) 发现我们要求的是所有点中到达时间的最大值的期望,\(n\)又很小,考虑min-max容斥 那么我们要求从\(x ...
-
Luogu3175 HAOI2015 按位或 min-max容斥、高维前缀和、期望
传送门 套路题 看到\(n \leq 20\),又看到我们求的是最后出现的位置出现的时间的期望,也就是集合中最大值的期望,考虑min-max容斥. 由\(E(max(S)) = \sum\limits ...
-
hihocoder1496(高维前缀和)
题意:给定N个数A1, A2, A3, ... AN,小Ho想从中找到两个数Ai和Aj(i ≠ j)使得乘积Ai × Aj × (Ai AND Aj)最大.其中AND是按位与操作. 第一行一个整数N( ...
-
[luogu 3175] [HAOI2015]按位或(min-max容斥+高维前缀和)
[luogu 3175] [HAOI2015]按位或 题面 刚开始你有一个数字0,每一秒钟你会随机选择一个[0,2^n-1]的数字,与你手上的数字进行按位或运算.问期望多少秒后,你手上的数字变成2^n ...
随机推荐
-
原生JS实战:分享一个首页进度加载动画!
本文是苏福的原创文章,转载请注明出处:苏福CNblog:http://www.cnblogs.com/susufufu/p/5871134.html 该程序是本人的个人作品,写的不好,可以参考,但未经 ...
-
【WEB】初探Spring MVC框架
Spring MVC框架算是当下比较流行的Java开源框架.但实话实说,做了几年WEB项目,完全没有SpringMVC实战经验,乃至在某些交流场合下被同行严重鄙视“奥特曼”了.“心塞”的同时,只好默默 ...
-
【BZOJ】【3207】花神的嘲讽计划 I
字符串Hash+可持久化线段树 好神奇的转化…… 蒟蒻一开始还去想AC自动机去了……然而由于a[i]的范围是小于等于n,怎么也想不出一个时间复杂度合理的方法 膜拜了题解0.0原来是字符串Hash! 首 ...
-
Firefox 32 支持 Public Key Pinning 对抗中间人攻击。
Firefox 32 支持 Public Key Pinning 对抗中间人攻击.8月28日消息,即将发布的Firefox 32将支持Public Key Pinning机制,以防止中间人攻击.Pub ...
-
mysql SQL_MODE设置
1.1. SQL_MODE设置 在生产环境中强烈建议将这个值设置为严格模式,这样有些问题可以在数据库的设计和开发阶段就能实现,而如果在生产环境下运行数据库后发现这类问题,那么修改的代价将变得十分巨 ...
-
html系列教程--span style 及表格标签 title video
<span> 标签:非块状元素,用于文本描述 <style> 标签:内联样式表标签定义样式信息,必须写明type类型为text/css,建议写在head中,不是必须 demo: ...
-
python实战===实现读取txt每一行的操作,账号密码
最近搞到了一批163邮箱的账号和密码,但是里面有部分账号不能用,密码是错的. 以此为背景 人工手动挨个登录检查效率太低! 于是写了下面这个脚本: import linecache import smt ...
-
Java并发编程笔记4-线程池
我们使用线程的时候就去创建一个线程,但是就会有一个问题: 如果并发的线程数量非常多,而且每个线程都是执行一个时间很短的任务就结束了,这样频繁创建线程就会导致大大降低系统的效率,因为频繁创建线程和销毁线 ...
-
Unity 显示FPS(C#语言)
直接上脚本了: using UnityEngine; using System.Collections; public class ShowFPS : MonoBehaviour { //设置帧率 A ...
-
js 动态生成html 触发事件传参字符转义
通常,在使用 JS 动态生成 html 的过程中,会嵌入相应的样式.事件等属性元素,而这时经常会出现所谓的 “单.双引号不够用” 的情况,别急,这时可以利用 html 语言中的转义字符来解决.下面就来 ...