正題

題目鏈接:https://www.luogu.com.cn/problem/CF1553H

---

題目大意

給出$n$個在$[0,2^n)$范圍內的數字序列$a$。

對于每個$x\in [0,2^n)$求
$$\underset{i=j}{\min }|a_{i}xorx?a_{j}xorx|$$

$2\le n\le 2^k,1\le k\le 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}xorx$最大并且$a_{j}xory$最小轉移到$x$即可。

考慮如何快速找這兩個數字，設$m{x}_{x,d},m{i}_{x,d}$表示上述所示情況下$xxora$的最大值/最小值，這兩個的轉移十分顯然。
$$m{x}_{x,d}=max\{m{x}_{x,d?1},m{x}_{y,d?1}+2^d\}$$
$$m{i}_{x,d}=min\{m{i}_{x,d?1},m{i}_{y,d?1}+2^d\}$$

時間復雜度：$O(2^{k}k)$

---

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; }

總結

以上是生活随笔為你收集整理的CF1553H-XOR and Distance【dp】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。