自动搬运

查看原文

来自洛谷，原作者为

	IamZZ 博士，无须担心，答案就藏在下一次尝试中！

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

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

以下是正文

题目大意

​ 现在有 $N(2\leq N\leq10^5)$ 个长度为 $C(1\leq C\leq18)$ 的字符串，由字符 G 与 H 组成。

​ 求 $N$ 个字符串中与第 $i$ 个字符串最大的汉明距离了。

题解思路

​ 首先，一个挺好的思路，我们可以先把每个字符串按二进制转换成数，便于处理。

​ 我们发现，与数 $x$ 最大的汉明距离难以处理，而最小汉明距离却不难，考虑如何转化。

​ 对于 $x$，与之最大的汉明距离其实就是 $C$ 减去与 $2^C-1-x$（$x$ 的反码）最小的汉明距离。

​ 试着证明一下，我们现在已知有一个数与 $x$ 的反码有最小的汉明距离 $k$ 。

​ 那这个数与 $x$ 的汉明距离就要将原本需要取反的 $k$ 位保持不变，另外相同的 $C-k$ 位却需要取反了，汉明距离也变成了 $C-k$。

​ 现在题目似乎更明了了，我们首先要预处理出 $0 \sim 2^C-1$ 所有数能找到的最小汉明距离（$f$）。

​ 先把输入的数（字符串）最小值设为 $0$，别的数就可以按照位枚举，依次转移。

​ 之后的输出按照上面的结论就可以啦~

​ 时间复杂度 $\Theta(2^C·C)$

题解代码

#include<cstdio>
using namespace std;
int c,n,f[1000001],m,o[100001],v;
char s[21];
int min(int a,int b)
{
	if(a<b)
	  return a;
	return b;
}
int main()
{
	int i,j;
	scanf("%d%d",&c,&n);
	for(i=0;i<=(1<<c)-1;++i)
	  f[i]=99999999;
	for(i=1;i<=n;++i)
	{
		scanf("%s",s+1);
		for(j=1;j<=c;++j)
		{
			v=0;
			if(s[j]=='G')
			  v=1;
			o[i]=o[i]<<1|v;
		}
		f[o[i]]=0;
	}
	for(j=1;j<=c;++j)
	{
		for(i=0;i<=(1<<c)-1;++i)
		  f[(1<<j-1)^i]=min(f[(1<<j-1)^i],f[i]+1);
	}
	for(i=1;i<=n;++i)
	{
		m=c-f[(1<<c)-1^o[i]];
		printf("%d\n",m);
	}
	return 0;
}

谢谢您选择这篇题解！