uoj#370【UR #17】滑稽树上滑稽果

低智选手果然刷不动uoj

首先考虑一下构造一棵树显然是骗你玩的，按位与这个东西越做越小，挂到链的最下面显然不会劣于挂到之前的某一个点下面，所以我们只需要求一个排列使得答案最小就好了

设\(A=\max(a_i)\)，发现最优答案不可能要劣于反复对一个数取\(\rm and\)的答案，我们就有了一个\(O(nA)\)的暴力，设\(dp_i\)表示当前的\(\rm and\)和为\(i\)，把这个\(i\)变成\(0\)的最小代价

但是有可能最后的\(\rm and\)和也不是\(0\)，于是我们把所有\(a_i\)都共有的二进制位\(k\)都求出来，在把每一个\(a_i\)消去这些数位，即和\(k\)异或一下，最后的\(\rm and\)和就一定为\(0\)；在答案加上\(n\times k\)就好了

这样的话转移非常简单，我们枚举一个\(a_j\)，\(dp_i=\min(dp_{i\ \rm and \ a_j }+i\ \rm and \ a_j)\)即可

最后答案是\(\min(dp_{a_i}+a_i)\)

注意到\(i\ \rm and \ a_j\)一定是\(i\)的子集，考虑枚举\(i\)的子集\(j\)，现在只需要判断是否存在一个\(a_k\)满足\(i\ \rm and\ \ a_k=j\)

从集合的角度来考虑，我们可以把上面那个条件拆成\(j\)是\(a_k\)的子集，并且\(a_k\)是\(j\bigoplus i\)在全集补集中的子集，我们用\(\rm fwt\)处理一下就可以知道是否有一个\(a_k\)是\(i\bigoplus j\)在全集补集中的子集，但并没有办法判断\(j\)是否为\(a_k\)的子集

但是想一想发现我们没有必要判断\(j\)是否为\(a_k\)的子集，只管转移就好了

观察转移式\(dp_i=\min(dp_j+j)\)，显然\(j\)越小越好，如过存在\(a_k\)是\(i\bigoplus j\)在全集补集中的子集，但是\(a_k\)并不是\(j\)的子集，那么一定会有一个更小的\(i\)的子集是这个\(a_k\)的子集，那个转移一定更优

于是复杂度就是\(O(3^{\log A})\)

#include<bits/stdc++.h>

#define re register

#define LL long long

#define min(a,b) ((a)<(b)?(a):(b))

#define max(a,b) ((a)>(b)?(a):(b))

inline int read() {

	char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();

	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;

}

const int maxn=1e5+5;

int n,a[maxn],vis[1<<18+1],k,T,len;

LL dp[1<<18+1],ans;

int main() {

	n=read();

	for(re int i=1;i<=n;i++) a[i]=read(),T=max(T,a[i]);

	len=1;while(len<T) len<<=1;len--;

	for(re int i=1;i<=n;i++) vis[a[i]]=1;

	for(re int i=2;i<=len+1;i<<=1)

		for(re int ln=i>>1,l=0;l<len;l+=i)

			for(re int x=l;x<l+ln;++x) vis[x+ln]|=vis[x];

	k=a[1];for(re int i=2;i<=n;i++) k&=a[i];

	for(re int i=1;i<=n;i++) a[i]^=k;

	memset(dp,20,sizeof(dp));

	ans=dp[0];dp[0]=0;

	for(re int i=1;i<=T;i++)

		for(re int j=i;j;j=(j-1)&i)

			if(vis[len^j]&&dp[i^j]+(i^j)<dp[i]) dp[i]=dp[i^j]+(i^j);

	for(re int i=1;i<=n;i++)

		ans=min(ans,dp[a[i]]+a[i]);

	printf("%lld\n",1ll*n*k+ans);

	return 0;

}

巴特西

uoj#370【UR #17】滑稽树上滑稽果

最新文章

热门文章