HDU4712—–Hamming Distance——超级大水题

本文出自：http://blog.csdn.net/dr5459

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

题目意思：

海明距离：任意两个树异或后二进制含1的个数

要你求出最小的海明距离

解题思路：

因为数的格式是固定的，所以可以预处理16进制中任意两个数的异或1的个数

这样在求的时候，可以在O(5)内求出

至于怎么去求所有的，看的群里的思路，随机10W次，而且要保证随机的两个数不同，我随机了6W次

然后就A了，就A了，真的被吓到了，下面上代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<ctime>
#include<cstdlib>
using namespace std;int cmp[16][16];char data[1000005][6];int fun(int q,int w)
{
    int a,b;
    int ret = 0;
    for(int i=0;i<5;i++)
    {
        char x = data[q][i];
        char y = data[w][i];
        if(x>='0' && x<='9')
            a=x-'0';
        else
            a=x-'A'+10;        if(y>='0' && y<='9')
            b=y-'0';
        else
            b=y-'A'+10;        ret += cmp[a][b];
    }
    return ret;
}int main()
{
    for(int i=0;i<=15;i++)
    {
        for(int j=0;j<=15;j++)
        {
            int ans=0;
            int tmp = i^j;
            for(int k=0;k<4;k++)
                if((1<<k) & tmp)
                    ans++;
            //cout<<i<<" "<<j<<" "<<ans<<endl;
            cmp[i][j] = ans;
        }
    }    int n;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%s",data[i]);        int ans = 0x3f3f3f3f;
        srand( (unsigned)time( NULL ) );
        for(int i=1;i<=60000;i++)
        {
            int a = rand()%n+1;
            int b = rand()%n+1;
            if(a==b)
                b = b%n+1;
            int tmp = fun(a,b);
            if(tmp < ans)
                ans = tmp;
        }        cout<<ans<<endl;
    }    return 0;
}