首页 > ACM题库 > HDU-杭电 > HDU 4712-Hamming Distance[解题报告]HOJ
2015
09-17

HDU 4712-Hamming Distance[解题报告]HOJ

Hamming Distance

问题描述 :

(From wikipedia) For binary strings a and b the Hamming distance is equal to the number of ones in a XOR b. For calculating Hamming distance between two strings a and b, they must have equal length.
Now given N different binary strings, please calculate the minimum Hamming distance between every pair of strings.

输入:

The first line of the input is an integer T, the number of test cases.(0<T<=20) Then T test case followed. The first line of each test case is an integer N (2<=N<=100000), the number of different binary strings. Then N lines followed, each of the next N line is a string consist of five characters. Each character is ’0′-’9′ or ‘A’-'F’, it represents the hexadecimal code of the binary string. For example, the hexadecimal code "12345" represents binary string "00010010001101000101".

输出:

The first line of the input is an integer T, the number of test cases.(0<T<=20) Then T test case followed. The first line of each test case is an integer N (2<=N<=100000), the number of different binary strings. Then N lines followed, each of the next N line is a string consist of five characters. Each character is ’0′-’9′ or ‘A’-'F’, it represents the hexadecimal code of the binary string. For example, the hexadecimal code "12345" represents binary string "00010010001101000101".

样例输入:

2
2
12345
54321
4
12345
6789A
BCDEF
0137F

样例输出:

6
7

题目地址: http://acm.hdu.edu.cn/showproblem.php?pid=4712

首先,算汉明距离就是二进制异或以后的1的个数,统计1的个数用x&=x-1很快很神奇。

用if(x&1)  {count++;    x>>=1;}  在位数比较多的时候会慢一些。

然后就是看题解学到的神奇的“随机”!  来取到“任意的两个”  1w次wa,但是10w次就不会,20组testcase ,不会超时;

真的ac了,很神奇

代码:

#include<iostream>
#include<ctime>
#include<algorithm>
#include<cstdlib>
#include<cstdio>

using namespace std;

int a[100005];

int hamming(int x,int y)
{
    x=x^y;
    int count=0;
    while(x)
    {
       x&=x-1;
       count++;
    }
    return   count;
}

int min(int &a,int &b)
{
    return  a<b?a:b;
}
int main()
{
   int T;
   cin>>T;

   srand(time(0));
   int n;
  while(cin>>n)
  {
    for(int i=0;i<n;i++)
      scanf("%x",&a[i]);
    int  test=100000;
    int x,y;
    int ans=100;
    while(test--)
    {
        x=rand()%n;
        y=rand()%n;

        while(x==y)
        x=rand()%n;

        ans=min(ans,hamming(a[x],a[y]));
    }

    cout<<ans<<endl;
  }


}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/jingqi814/article/details/11880325