自动搬运

查看原文

来自洛谷，原作者为

	wangyizhi 昨夜西风凋碧树。独上高楼，望尽天涯路。

搬运于2025-08-24 22:58:51，当前版本为作者最后更新于2025-03-12 21:12:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

很神奇的一个题目！

但感觉可以蓝？

题目分析

固定原序列，则就是序列 $0,1,...,2^n-1$ 在上面滚动

考虑对于第 $i$ 位，原序列就是：

其中，每个循环节长 $2^{i+1}$。

我们可以先暴力计算出第一串 $0$ 从 $0$ 开始的值，然后开始滚动这串数。

注意到滚动一次之后，只会有 $2^{n-i}$ 个数发生了改变，这几个数我们也可以暴力更新答案。

但是我们发现，事实上我们只需要求出第一串 $0$ 在第一个循环节内的结果就行了。

因此总的时间复杂的只有 $O(2^{n+1})$。

最后做个类似前缀和的东西就做完了。

AC Code

可能常数有点大。。。

//by wangyizhi(571247)
#include<bits/stdc++.h>
//#include<bits/extc++.h>
using namespace std;
using ll=long long;
using ld=long double;
#define int ll
using pii=pair<int,int>;
//bool Mst;
int n,a[1<<20],f[20][1<<20];
int solve1()
{
	memset(f,0,sizeof(f));
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<(1<<n);j++) f[i][0]+=((a[j]^j)&(1<<i));
		for(int j=1;j<(1<<(i+1));j++)
		{
			f[i][j]=f[i][j-1];
			for(int k=j-1;k<(1<<n);k+=(1<<(i+1))) f[i][j]-=(a[k]&(1<<i)),f[i][j]+=(a[k]&(1<<i))^(1<<i);//将0改为1
			for(int k=(j-1)^(1<<i);k<(1<<n);k+=(1<<(i+1))) f[i][j]-=(a[k]&(1<<i))^(1<<i),f[i][j]+=(a[k]&(1<<i));//将1该为0
		}
	}
	int ans=0;
	for(int i=1;i<n;i++) for(int j=0;j<(1<<(i+1));j++) f[i][j]+=f[i-1][j&((1<<i)-1)];
	for(int i=0;i<(1<<n);i++) ans=max(ans,f[n-1][i]);
	return ans;
}
int solve2()
{
	memset(f,0,sizeof(f));
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<(1<<n);j++) f[i][0]+=((a[j]&j)&(1<<i));
		for(int j=1;j<(1<<(i+1));j++)
		{
			f[i][j]=f[i][j-1];
			for(int k=j-1;k<(1<<n);k+=(1<<(i+1))) f[i][j]+=(a[k]&(1<<i));
			for(int k=(j-1)^(1<<i);k<(1<<n);k+=(1<<(i+1))) f[i][j]-=(a[k]&(1<<i));
		}
	}
	int ans=0;
	for(int i=1;i<n;i++) for(int j=0;j<(1<<(i+1));j++) f[i][j]+=f[i-1][j&((1<<i)-1)];
	for(int i=0;i<(1<<n);i++) ans=max(ans,f[n-1][i]);
	return ans;
}
int solve3()
{
	memset(f,0,sizeof(f));
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<(1<<n);j++) f[i][0]+=((a[j]|j)&(1<<i));
		for(int j=1;j<(1<<(i+1));j++)
		{
			f[i][j]=f[i][j-1];
			for(int k=j-1;k<(1<<n);k+=(1<<(i+1))) f[i][j]+=(a[k]&(1<<i))^(1<<i);
			for(int k=(j-1)^(1<<i);k<(1<<n);k+=(1<<(i+1))) f[i][j]-=(a[k]&(1<<i))^(1<<i);
		}
	}
	int ans=0;
	for(int i=1;i<n;i++) for(int j=0;j<(1<<(i+1));j++) f[i][j]+=f[i-1][j&((1<<i)-1)];
	for(int i=0;i<(1<<n);i++) ans=max(ans,f[n-1][i]);
	return ans;
}
//bool Med;
signed main()
{
//	cerr<<"Memory Size: "<<abs((&Med)-(&Mst))/1024.0/1024<<" MB\n";
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=0;i<(1<<n);i++) cin>>a[i];
	cout<<solve1()<<" "<<solve2()<<" "<<solve3()<<"\n";
	return 0;
}