【2022 NOIP 模拟赛 19】卷积之王 做题记录

给出长度为 $2^k$ 的两个序列 $a_{[0,2^k-1]}$ 和 $b_{[0,2^k-1]}$，求一个长度为 $2^k$ 的序列 $c_{[0,2^k-1]}$，满足 $c_p=\max\limits_{i|j=p}\{a_i+b_j\}$。

$1\le k\le 17$。

考虑枚举 $i$，不难发现，$i$ 为 $1$ 的二进制位 $j$ 都能随便选。那么只要用某种方法求出 $mx_x$ 表示 $i$ 为 $1$ 的二进制位可以乱选且其他二进制位和 $x$ 一致的 $j$ 中最大的 $b_j$，就可以更新 $c_{i|x}$。

不难发现，只要在枚举 $i$ 的第 $p$ 位为 $1$ 时，枚举 $i$ 的补集的子集 $j$，令 $mx_{j|i}\to \max(mx_{j|i},mx_{j|i-2^p})$ 即让这一位为 $1$ 的 $mx$ 加上这一位为 $0$ 的 $mx$ 的贡献就可以快速维护 $mx$。

维护 $mx$ 的时间复杂度是 $O(3^k)$ 的，更新答案的时间复杂度也是 $O(3^k)$ 的，足以通过此题。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int S=300005;

int k,n;
long long a[S],b[S];
long long mx[20][S],ans[S];

void slove(int pos,int cnt,int sta)
{
	int inv=n-1^sta;
	if(pos==k)
	{
		for(int T=inv;;T=inv&(T-1))
		{
			ans[T|sta]=max(ans[T|sta],a[sta]+mx[cnt][T|sta]);
			if(T==0) break;
		}
		return;
	}
	slove(pos+1,cnt,sta);
	sta|=1<<pos;
	inv=n-1^sta;
	for(int T=inv;;T=inv&(T-1))
	{
		mx[cnt+1][T|sta]=max(mx[cnt][T|sta],mx[cnt][T|sta^(1<<pos)]);
		if(T==0) break;
	}
	slove(pos+1,cnt+1,sta);
}

int main()
{
	scanf("%d",&k);
	n=1<<k;
	for(int i=0;i<=n-1;i++) scanf("%lld",&a[i]);
	for(int i=0;i<=n-1;i++) scanf("%lld",&b[i]),mx[1][i]=b[i];
	slove(0,1,0);
	for(int i=0;i<=n-1;i++) printf("%lld ",ans[i]);
	printf("\n");
	return 0;
}