Codeforces 1208F Bits And Pieces

题目描述

You are given an array a of n integers.

You need to find the maximum value of a_i|(a_j&a_k) over all triplets (i,j,k) such that i<j<k.

大意

给你一个包含n个整数的序列a

你要在所有满足i<j<k的三元组中找到最大的a_i|a_j&a_k

3<=n<=10⁶

0<=a[i]<=2*10⁶

题解

一，位运算

|指的是二进制后的按位或

如 2|5=7,7|9=15

&指的是二进制后的按位且

如 3&2=2,13&10=8

二、题目

说完了简单的位运算，我们正式进入主题

“按位或”有个特点，就是如果一个数当前位置上是1，则结果当前位置上也一定是1

看上去好废话啊

这样的话，我们就可以枚举更方便确定的a[i]

我们不妨定义a[j]&a[k]的值叫q

那么q一定是a[j]和a[k]的子集（数字的子集是转化为二进制后，每一位都小于等于原数字的数，而不是集合）

因此，我们就可以遍历这些数字的子集，要用dfs执行

当然，别忘了高位优先！

三、dfs深搜

这部分的深搜很像状压DP，我们只需要找出现了两次的子集即可，同时我们还要避免同一个数的子集算了两次

如110的子集010和100的下一个子集都是000

用vis数组记录即可

四、代码

#include<iostream>

using namespace std;

int sum[2000010],a[1000010],vis[2000010],n,ans;

void h(int x,int y){

    if(sum[x]>1||vis[x]==y) return ;

    ++sum[x];

    vis[x]=y;

    for(int i=0;(1<<i-1)<x;i++)

        if(x&(1<<i)) h(x^(1<<i),y);

}

int main(){

    scanf("%d",&n);

    for(int i=1;i<=n;i++) scanf("%d",&a[i]);

    h(a[n],n);

    h(a[n-1],n-1);

    for(int i=n-2;i>=1;i--){

        int k=0;

        for(int j=20;j>=0;j--){

            if(!(a[i]&(1<<j))&&sum[k^(1<<j)]>1) k^=(1<<j);

        }

        ans=max(ans,a[i]|k);

        h(a[i],i);

    }

    printf("%d",ans);

    return 0;

}

巴特西

Codeforces 1208F Bits And Pieces

最新文章

热门文章