8

hdoj 4712 Hamming Distance(靠人品过的)

 3 years ago
source link: https://zxs.io/article/173
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
hdoj 4712 Hamming Distance(靠人品过的)

我先解释一下汉明距离  以下来自百度百科

在信息论中，两个等长字符串之间的汉明距离是两个字符串对应位置的字符不同的个数。换句话说，它就是将 一个字符串变换成另外一个字符串所需要替换的字符个数。 例如：
* 1 与 0 之间的汉明距离是 1。
* 214 与 214 之间的汉明距离是 0。
* "abcd" 与 "aacd" 之间的汉明距离是 1。
汉明重量是字符串相对于同样长度的零字符串的汉明距离，也就是说，它是字符串中非零的元素个数：对于二进制字符串来说，就是 1 的个数，所以 11101 的汉明重量是 4。

汉明距离在信息论、密码学等方向有很重要的应用。

这个题是让你求n个数两两之间最小的汉明距离，而且规定了每个数是长度为5的16进制数，可以想到求出最大的值为20，最小为10。 没想到什么好的算法，看了人家的解题报告，依靠RP，随机找1000000对点求最小值，不过还是过了。

#include<algorithm>
#include<stdio.h>
#include <stdlib.h>
#define inf 1000000007

using namespace std;

int M[100005];
int count(int x,int y)
{
    int sum=0,p=x^y;
    while (p)
        sum+=p%2,p>>=1;
    return sum;
}

int main()
{
    int T,y,n,d,i,j,x;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d",&n);
        for (i=1;i<=n;i++)
        {
            scanf("%X", &M[i]);
        }
        int ans=inf;
        for (i=1;i<=1000000;i++)
        {
            x=rand()%n+1;
            y=rand()%n+1;
            if (x==y) continue;
            ans=min(ans,count(M[x],M[y]));
        }
        printf("%d\n",ans);
    }
    return 0;
}

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK