hihocoder 1496 寻找最大值(高维前缀最大次大值)

时间:2023-01-08 08:38:25

【题目链接】 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 寻找最大值(高维前缀最大次大值)的更多相关文章

  1. Hihocoder 1496 寻找最大值(状态压缩 &plus; 高位前缀和)

    题目链接  Hiho 1496 设$f[i]$为二进制集合包含$i$的最大的两个数,这个东西用高维前缀和维护. 高位前缀和转移的具体方案 :枚举每一位,然后枚举每个集合,大的转移到小的. 注意合并的时 ...

  2. hihocoder 1496 寻找最大值

    题解: 注意到$ai$只有$1e6$这件事情肯定要枚举和这个有关的东西 考虑枚举$ai\&aj$的值就可以了 那么这个集合一定是ai,aj的子集 于是我们对每个集合从大到小枚举丢掉一位转移就行 ...

  3. HihoCoder 1496:寻找最大值(思维DP)

    http://hihocoder.com/problemset/problem/1496 题意:中文. 思路:一开始做有一种想法,把所有的数都变成二进制后,最优的情况肯定是挑选所有数中最高位的1能同时 ...

  4. MATLAB寻找数组前k个大值

    有时候我们需要寻找数组的前k个大值并按照顺序输出, 在C语言可以通过快速排序等算法,快速求得,这里用matlab写了一个比较简单实用的程序(适用于数组长度不是特别大的情况). function [va ...

  5. HihoCoder - 1496:寻找最大值(高维前缀和&vert;&vert;手动求子集)

    描述 给定N个数A1, A2, A3, ... AN,小Ho想从中找到两个数Ai和Aj(i ≠ j)使得乘积Ai × Aj × (Ai AND Aj)最大.其中AND是按位与操作. 小Ho当然知道怎么 ...

  6. LOJ2542 PKUWC2018 随机游走 min-max容斥、树上高斯消元、高维前缀和、期望

    传送门 那么除了D1T3,PKUWC2018就更完了(斗地主这种全场0分的题怎么会做啊) 发现我们要求的是所有点中到达时间的最大值的期望,\(n\)又很小,考虑min-max容斥 那么我们要求从\(x ...

  7. Luogu3175 HAOI2015 按位或 min-max容斥、高维前缀和、期望

    传送门 套路题 看到\(n \leq 20\),又看到我们求的是最后出现的位置出现的时间的期望,也就是集合中最大值的期望,考虑min-max容斥. 由\(E(max(S)) = \sum\limits ...

  8. hihocoder1496(高维前缀和)

    题意:给定N个数A1, A2, A3, ... AN,小Ho想从中找到两个数Ai和Aj(i ≠ j)使得乘积Ai × Aj × (Ai AND Aj)最大.其中AND是按位与操作. 第一行一个整数N( ...

  9. &lbrack;luogu 3175&rsqb; &lbrack;HAOI2015&rsqb;按位或&lpar;min-max容斥&plus;高维前缀和&rpar;

    [luogu 3175] [HAOI2015]按位或 题面 刚开始你有一个数字0,每一秒钟你会随机选择一个[0,2^n-1]的数字,与你手上的数字进行按位或运算.问期望多少秒后,你手上的数字变成2^n ...

随机推荐

  1. 原生JS实战:分享一个首页进度加载动画!

    本文是苏福的原创文章,转载请注明出处:苏福CNblog:http://www.cnblogs.com/susufufu/p/5871134.html 该程序是本人的个人作品,写的不好,可以参考,但未经 ...

  2. 【WEB】初探Spring MVC框架

    Spring MVC框架算是当下比较流行的Java开源框架.但实话实说,做了几年WEB项目,完全没有SpringMVC实战经验,乃至在某些交流场合下被同行严重鄙视“奥特曼”了.“心塞”的同时,只好默默 ...

  3. 【BZOJ】【3207】花神的嘲讽计划 I

    字符串Hash+可持久化线段树 好神奇的转化…… 蒟蒻一开始还去想AC自动机去了……然而由于a[i]的范围是小于等于n,怎么也想不出一个时间复杂度合理的方法 膜拜了题解0.0原来是字符串Hash! 首 ...

  4. Firefox 32 支持 Public Key Pinning 对抗中间人攻击。

    Firefox 32 支持 Public Key Pinning 对抗中间人攻击.8月28日消息,即将发布的Firefox 32将支持Public Key Pinning机制,以防止中间人攻击.Pub ...

  5. mysql SQL&lowbar;MODE设置

    1.1.   SQL_MODE设置 在生产环境中强烈建议将这个值设置为严格模式,这样有些问题可以在数据库的设计和开发阶段就能实现,而如果在生产环境下运行数据库后发现这类问题,那么修改的代价将变得十分巨 ...

  6. html系列教程--span style 及表格标签 title video

    <span> 标签:非块状元素,用于文本描述 <style> 标签:内联样式表标签定义样式信息,必须写明type类型为text/css,建议写在head中,不是必须 demo: ...

  7. python实战&equals;&equals;&equals;实现读取txt每一行的操作,账号密码

    最近搞到了一批163邮箱的账号和密码,但是里面有部分账号不能用,密码是错的. 以此为背景 人工手动挨个登录检查效率太低! 于是写了下面这个脚本: import linecache import smt ...

  8. Java并发编程笔记4-线程池

    我们使用线程的时候就去创建一个线程,但是就会有一个问题: 如果并发的线程数量非常多,而且每个线程都是执行一个时间很短的任务就结束了,这样频繁创建线程就会导致大大降低系统的效率,因为频繁创建线程和销毁线 ...

  9. Unity 显示FPS(C&num;语言)

    直接上脚本了: using UnityEngine; using System.Collections; public class ShowFPS : MonoBehaviour { //设置帧率 A ...

  10. js 动态生成html 触发事件传参字符转义

    通常,在使用 JS 动态生成 html 的过程中,会嵌入相应的样式.事件等属性元素,而这时经常会出现所谓的 “单.双引号不够用” 的情况,别急,这时可以利用 html 语言中的转义字符来解决.下面就来 ...