P9187 [USACO23OPEN] Field Day S 题解

· · 题解

题目大意

​ 现在有 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;
}

谢谢您选择这篇题解！