【佛山市选2013】JZOJ2020年8月7日提高组T3 海明距离

题目

描述

对于二进制串a，b，他们之间的海明距离是指两个串异或之后串中1的个数。异或的规则为：

0 XOR 0 = 0

1 XOR 0 = 1

0 XOR 1 = 1

1 XOR 1 = 0

计算两个串之间的海明距离的时候，他们的长度必须相同。现在我们给出N个不同的二进制串，请计算出这些串两两之间的最短海明距离。

数据

对于30%的数据有1≤N≤100

对于全部数据，有1≤N≤100000

题解

捕捉到一只翻车的HowarLi

题意

以\(n\)个长度为5的十六进制的形式给出\(n\)个二进制串，求这\(n\)个二进制串中两两之间的最短海明距离

海明距离的定义如题

emmm……

能说什么呢，数据过水将下述骗分大法放走了

这道题的AC算法只有一句话

将16进制转为10进制后取前1000个（\(n\)没有1000就取到\(n\)），然后暴力匹配求最短海明距离

Code

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define inf 2147483647

using namespace std;

int t,n,i,j,k,num,x,s,ans,a[10],c[100005];

char ch;

int main()

{

    freopen("T3.in","r",stdin);

    freopen("T3.out","w",stdout);

    scanf("%d",&t);

    while (t--)

    {

        memset(c,0,sizeof(c));

        scanf("%d",&n);

        for (i=1;i<=n;i++)

        {

            num=0;

            memset(a,0,sizeof(a));

            ch=getchar();

            while ((ch<'0'||ch>'9')&&(ch<'A'||ch>'F')) ch=getchar();

            while ((ch>='0'&&ch<='9')||(ch>='A'&&ch<='F'))

            {

                num++;

                if (ch>='0'&&ch<='9') a[num]=ch-'0';

                if (ch>='A'&&ch<='F') a[num]=ch-'A'+10;

                ch=getchar();

            }

            c[i]=a[5]*1+a[4]*16+a[3]*256+a[2]*4096+a[1]*65536;

        }

        ans=inf;

        sort(c+1,c+n+1);

        for (i=1;i<=min(1000,n);i++)

            for (j=i+1;j<=min(1000,n);j++)

            {

                x=c[i]^c[j];

                s=0;

                for (k=0;k<=19;k++)

                    if ((x&(1<<k))!=0) s++;

                ans=min(ans,s);

            }

        printf("%d\n",ans);

    }

    fclose(stdout);

    fclose(stdout);

    return 0;

}