正题
题目链接:https://www.luogu.com.cn/problem/CF1553H
题目大意
给出\(n\)个在\([0,2^n)\)范围内的数字序列\(a\)。
对于每个\(x\in[0,2^n)\)求
\[\min_{i\neq j}\ |a_i\ xor\ x-a_j\ xor\ x|
\]
\(2\leq n\leq 2^k,1\leq k\leq 19\)
解题思路
一个很妙的想法，考虑一个数字\(a\)与\(x\)有最多只有前\(d\)位不同的情况，记答案为\(f_{x,d}\)。
考虑这个答案的性质，对于\(x\)找一个一个与它恰好第\(d\)位不同的\(y\)考虑转移，首先显然是从\(min\{f_{x,d-1},f_{y,d-1}\}\)处进行一个转移（因为只多了第\(d\)位可以不同，而此时这两种转移就包括了两个点集内的情况）。
但是还有一种转移有可能是在\(x\)的集合和\(y\)的集合中各自选一个数字，我们可以各自找到两个分别在\(x/y\)的集合中的数字\(a_i\ xor\ x\)最大并且\(a_j\ xor\ y\)最小转移到\(x\)即可。
考虑如何快速找这两个数字，设\(mx_{x,d},mi_{x,d}\)表示上述所示情况下\(x\ xor\ a\)的最大值/最小值，这两个的转移十分显然。
\[mx_{x,d}=max\{mx_{x,d-1},mx_{y,d-1}+2^d\}
\]
\[mi_{x,d}=min\{mi_{x,d-1},mi_{y,d-1}+2^d\}
\]
时间复杂度：\(O(2^kk)\)
code
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1<<19;
int n,k,mx[N],mi[N],f[N];
int main()
{
scanf("%d%d",&n,&k);
memset(mx,0xcf,sizeof(mx));
memset(mi,0x3f,sizeof(mi));
memset(f,0x3f,sizeof(f));
for(int i=1,x;i<=n;i++){
scanf("%d",&x);
mx[x]=mi[x]=0;
}
int MS=(1<<k);
for(int i=0;i<k;i++){
for(int s=MS-1;s>=0;s--)
if((s>>i)&1){
int t=s^(1<<i);
f[s]=f[t]=min(f[s],f[t]);
f[s]=min(f[s],mi[t]+(1<<i)-mx[s]);
f[t]=min(f[t],mi[s]+(1<<i)-mx[t]);
int mxt=mx[t],mit=mi[t];
int mxs=mx[s],mis=mi[s];
mx[s]=max(mx[s],mxt+(1<<i));
mi[s]=min(mi[s],mit+(1<<i));
mx[t]=max(mx[t],mxs+(1<<i));
mi[t]=min(mi[t],mis+(1<<i));
}
}
for(int i=0;i<MS;i++)
printf("%d ",f[i]);
return 0;
}