hdoj 4712 Hamming Distance(靠人品过的)
hdoj 4712 Hamming Distance(靠人品过的)
xindoo
发布于 2021-01-22 12:45:22
发布于 2021-01-22 12:45:22
我先解释一下汉明距离 以下来自百度百科
在信息论中，两个等长字符串之间的汉明距离是两个字符串对应位置的字符不同的个数。换句话说，它就是将 一个字符串变换成另外一个字符串所需要替换的字符个数。 例如：
* 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;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2013-09-08，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读