arc100 E Or Plus Max

题目描述

There is an integer sequence of length $2N$: $A_0,A_1,…,A_{2N−1}$. (Note that the sequence is $0$-indexed.) For every integer K satisfying $1≤K≤2N−1$, solve the following problem: Let i and j be integers. Find the maximum value of $A_i+A_j$ where $0≤i<j≤2N−1$ and $(i\ or\ j)≤K$. Here, or denotes the bitwise OR. Constraints $1≤N≤18$ $1≤A_i≤10^9$ All values in input are integers.

输入

Input is given from Standard Input in the following format: $N$ $A_0 A_1 … A_{2^N−1}$

输出

Print $2N−1$ lines. In the $i$-th line, print the answer of the problem above for $K=i$.

题目要求的是$ans[k]=\max_{0\leq i<j\leq 2^n-1,i \mid j\leq k}a[i]+a[j]$ ,但是我们容易求得的是$ans’[k]=\max_{0\leq i<j\leq 2^n-1,i \mid j==k}a[i]+a[j]$.

$ans’[k]$可以取出所有满足$i\mid k=k$的$a[i]$的最大值和次大值,加和即可.

那么怎么维护每个k所对应的最大值和次大值呢?直接枚举子集的话是时间复杂度是$3^n$的,可以用高维前缀和搞一下.

时间复杂度$O(n*2^n)$

#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=(1<<18)+3;
int a[maxn],m1[maxn],m2[maxn];
int main() {
	int n;
	scanf("%d", &n);
	const int N=(1<<n);
	for(int i = 0; i < N; ++i) scanf("%d", a+i),m1[i]=a[i],m2[i]=-inf;
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < N; ++j) {
			if(j&(1<<i)) {
				int k=(j^(1<<i));
				if(m1[k]>m1[j]) m2[j]=max({m2[j],m1[j],m2[k]}),m1[j]=m1[k];
				else m2[j]=max({m2[j],m1[k],m2[k]});
			}
		}
	}
	int ans=0;
	for(int i = 1; i < N; ++i) {
		ans=max(ans,m1[i]+m2[i]);
		printf("%d\n", ans);
	}
	return 0;
}