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;}