自动搬运

查看原文

来自洛谷，原作者为

	slzx2022YuYihan Nearly AFO选手

搬运于2025-08-24 22:46:04，当前版本为作者最后更新于2023-08-09 09:07:36，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Solution

看到此题，相信很多人会想到字典树。但是写到一半，突然发现写不下去了。这道题求的是最多的不同位，而不是异或最大值。异或最大值可以用字典树来实现，而且挺好理解的，可以自行学习一下。接下来，我们对问题进行一个转化。

根据题意，$m$ 为最大的二进制位数，那么有如下定理。

引理：$a_i$ 与 $x$ 的哈明距离加上 $a_i$ 取反与 $x$ 的哈明距离等于 $m$。

证明可以自行脑补一下所以，我们只要知道最小的 $a_i$ 取反与 $x$ 的哈明距离，就能求出答案。时间复杂度 $O(2^mm)$。具体实现还是比较简单的，用状压的思路。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

template<typename T>inline void read(T &x){
	x = 0; T w = 1; char ch = getchar();
	while (!isdigit(ch)){if (ch == '-')	w = -1; ch = getchar();}
	while (isdigit(ch))	x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	x *= w;
}
template<typename T>inline void write(T x){
	if (x < 0)	putchar('-'), x = ~(x - 1);
	if (x > 9)	write(x / 10);
	putchar(x % 10 ^ 48);
}

const int M = 21;

ll n, m, a[1 << M], ham[1 << M];

int main(){
//	freopen(".in", "r", stdin), freopen(".out", "w", stdout);
//	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

	read(n), read(m);
	memset(ham, 0x3f, sizeof ham);
	for (int i = 1; i <= n; ++i)
		read(a[i]), ham[a[i]] = 0;
	for (int i = 0; i < m; ++i)
		for (int j = 0; j < (1 << m); ++j)
			ham[j ^ (1 << i)] = min(ham[j ^ (1 << i)], ham[j] + 1);
	for (int i = 1; i <= n; ++i){
		ll res = ((1 << m) - 1) ^ a[i];//a[i]取反
		write(m - ham[res]), putchar(' '); 
	}

	return 0;
}