本文共 1089 字，大约阅读时间需要 3 分钟。

题意

$n$个数$a_i$,找到满足$i<j<k$的三元组最大化$a_i|(a_j\&a_k)$

其中$n<1e6$

毫无头绪的样子…

动态维护数组$f[mask]$表示有$f[mask]$个数的子集是$mask$

那么只要$f[mask]>=2$说明存在$a_j\&a_k$为$mask$

从后往前枚举$a_i$,然后去贪心的选择$a_j\&a_k$

具体来说从最高位往低位看,如果$a_i$在当前位为零,那么就看下是否能把这一位选上

那么现在的难点是如何动态维护$f[mask]$

如果对每个数去枚举子集的话太慢了,我们直接去从高位往低位递归所有子集

如果当前的$f[x]$大于$2$了说明不需要往下了,下面都是$x$的子集,一定也都大于$2$

否则,一直递归到底部,然后$f[x]++$

#include 
   
    using namespace std;const int maxn = 1<<22;int a[maxn],ans,f[maxn],n,vis[maxn];void pushdown(int x,int bit){
   	if( f[x]>=2 )	return;	if( bit==-1 )	{
    f[x]++; return; }	pushdown(x,bit-1);//这一位不剥削	if( x&(1<
    
     =0;i--)		if( (x&(1<
     
      <
      
       =2 )	ans |= (1<
       
        > n;	for(int i=1;i<=n;i++)	scanf("%d",&a[i] );	for(int i=n;i>=1;i-- )	{
   		if( i<=n-2 )	ans = max( ans,get( a[i] ) );		pushdown( a[i],20 );	}	printf("%d",ans);}
       
      
     
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/112535664 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！