CF1553H 题解 - XOR and Distance
x义x
·
·
题解
题解区 LaTeX 炸了，请移步 github pages 或 luogu 博客 观看。
题目大意.
现在有一列在 [0,2^k) 间的整数 a_i，你要对任意 x\in[0,2^k) 求出
\min_{i,j}|(a_i\oplus x)-(a_j\oplus x)|
官方正解十分恶心，但评论区一个老哥的解法着实很惊艳。
我们强制每个 x 只能使用那些，与 x 相比只有最低的 d 位可能不同的元素。
设 f(d,x) 为此时的答案，\text{minv}(d,x) 为这些元素中与 x 异或值的最小值，\text{maxv} 亦然。
现在从 d 转移到 d+1，令 x,y 为两个仅第 d+1 位不同的位置。（x<y）
$$
\text{minv}(d+1,x)=\min(\text{minv}(d,x),\text{minv}(d,y)+2^d\text)
$$
$$
\text{maxv}(d+1,x)=\max(\text{maxv}(d,x),\text{maxv}(d,y)+2^d\text)
$$
考虑 $f(d+1, x)$。元素对有三类：均处于 $(d,x)$ 中，均处于 $(d,y)$ 中，一个处于 $(d,x)$ 一个处于 $(d,y)$ 中。
- 对于第一类，直接使用 $f(d,x)$。
- 对于第二类，我们不难发现 $(a_i\oplus y)-(a_j\oplus y)=(a_i\oplus x)-(a_j\oplus x)$。直接使用 $f(d,y)$。
- 对于第三类，不难发现 $(a_j\oplus x)=(a_j\oplus y)+2^d\ge 2^d>(a_i\oplus x)$，故直接使用 $\text{minv}(d,y)$ 和 $\text{maxv}(d,x)$ 即可。
代码如下。
```cpp
#include<bits/stdc++.h>
using namespace std;
int n, k;
const int maxn = 1 << 19;
const int inf = 0x3f3f3f3f;
int f[maxn], v0[maxn], v1[maxn];
int main() {
scanf("%d%d", &n, &k);
for (int x = 0; x < 1 << k; x++)
f[x] = inf,
v0[x] = inf,
v1[x] = -inf;
while (n--) {
int x; scanf("%d", &x);
v0[x] = v1[x] = 0;
}
for (int i = 0; i < k; i++)
for (int y = 0; y < 1 << k; y++) if ((y >> i) & 1) {
int x = y ^ (1 << i);
// printf("%d : %d %d\n", i, x, y);
f[x] = f[y] = min(f[x], f[y]);
f[x] = min(f[x], v0[y] - v1[x] + (1 << i));
f[y] = min(f[y], v0[x] - v1[y] + (1 << i));
int v0x = v0[x], v0y = v0[y], v1x = v1[x], v1y = v1[y];
v0[x] = min(v0x, v0y + (1 << i));
v0[y] = min(v0y, v0x + (1 << i));
v1[x] = max(v1x, v1y + (1 << i));
v1[y] = max(v1y, v1x + (1 << i));
}
for (int x = 0; x < 1 << k; x++) printf("%d ", f[x]);
}
```