http://acm.hdu.edu.cn/showproblem.php?pid=4712
Hamming Distance
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others) Total Submission(s): 1610 Accepted Submission(s): 630
2
12345
54321
4
12345
6789A
BCDEF
0137F
7
分析：
输入n个数，用十六进制的方式输入的，任意选择其中的两个数进行异或，求异或后的数用二进制表示后1的个数最小的是多少？（n<=100000)
这题看了解题报告，大家都说用随机算法，试过了，随机100000次就过了，50000次都不行，但还是不懂这样怎么可以，唯一的解释就是这个值域也就是结果一共只有21个，
得出正确的结果的可能性很大，但是并不能100%保证结果是对的。无语第一次碰见这种算法。
首先，算汉明距离就是二进制异或以后的1的个数，统计1的个数用x&=x-1很快很神奇。
用if(x&1) {count++; x>>=1;} 在位数比较多的时候会慢一些。
然后就是看题解学到的神奇的“随机”！ 来取到“任意的两个” 1w次wa，但是10w次就不会，20组testcase ，不会超时。
队友用随机函数在hduoj上交了五次（WA了4次）A了。也是醉啦 ，，，
AC代码：
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
int a[]; int main()
{
int tes,i,j,k,res,ans;
scanf("%d",&tes);
while(tes--)
{
int n;
scanf("%d",&n);
for(i=;i<n;i++)
scanf("%X",&a[i]); //16进制读取 res=; //结果初始为最大20
for(i=;i<=;i++)
{
j=rand()%n; //随机函数
k=rand()%n;
if(j==k)
continue;
ans=;
int tmp=a[j]^a[k]; //抑或
while(tmp) //抑或算1的个数，保存到ans中
{
if(tmp&)
ans++;
tmp>>=;
}
if(ans<res)
res=ans;
}
cout<<res<<endl;
}
return ;
}
网上贴的都是随机算法做的，下面找了一个非随机的思想。
题意：给你n个(n<=1e5)数a0~a(n-1)（ai<(1<<20)） 要你求这n个数中转化为二进制后任意两个数中最小的汉明距离 \\ wiki百科：汉明距离
例如：a0 = 00000000010000000000 a1 = 00000000000000000001 a2 = 00000000000000000011
则答案为1 ， 因为 a1^a2 = 00000000000000000010 其中1的个数为1，则答案为1
思路：
先说下随即算法的思路：首先当n比较小的时候，直接暴力枚举每两个数，求最小的汉明距离即可；当n比较大时，每次直接随即选出两个数a，b，求出汉明距离选取最小的即可。
因为ai<(1<<20)，说明最终解一定<=20，解的范围很小，所以随即算法成功的几率还是很高的。
======================================================================================
首先要利用汉明距离的一个性质，二进制字符串的汉明距离也等于 n 维超正方体两个顶点之间的曼哈顿距离，其中n 是两个字串的长度。
我们先令(a,b)表示二进制字符a，b的汉明距离！！
怎么解释那个性质呢，就是比如有a，b，c三个二进制字符，其中(a,b)==(b,c)==1，那么(a,c) = (a,b)+(b,c) = 2
再加入一个d，假设(c,d)==1，且(d,a)!=1且(d,b)!=1，那么(d,a) = (a,b)+(b,c)+(c,d) = 3; (d,b) = (b,c)+(c,d) = 2;
（对于这个性质我一开始也是猜测，然后写了个小程序简单验证了一下，再后来仔细看汉明距离的wiki百科的时候才发现上面写着有。。。
怪不得题目上面一开始就表明了(From WIKI)。。。 ）
有了这个性质接下来的事情就比较简单了
因为a<(1<<20)，所以先把这(1<<20)个数当成(1<<20)个结点，然后把其汉明距离为1的结点连接起来，把边的长度设为1，
这样两个数的汉明距离即为这个图上两点间的最短路长度
如此一来，我们就可以把给出的n个数当成n个起点，然后在图上进行搜索，搜出任意两起点间最短的距离
搜索的方法就类似于多向BFS，具体的实现见代码
PS：多向BFS在搜索时，搜索到一个解并不能马上返回，需要把当前这一层的结点搜索完毕，然后返回一个最优值
比如下面这个图
可以尝试模拟一下，其中1，2，3表示搜索起点，当搜索到4号结点的时候，如果先行搜索红色边的话，则返回值是4，而正确解应该是3
AC代码：
#include <iostream>
#include <cstring>
#include <stdio.h>
#include <math.h>
#include <fstream>
#include <algorithm>
#include <stack>
#include <vector>
#include <queue>
using namespace std; #define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,j,k) for(int i=j;i<=(k);i++)
#define ll long long
#define base 20
#define maxn (1<<base)+10
/*
ifstream fin("1");
#define cin fin
*/
int a[],n; int Hash(char c){
if(c>=''&&c<='') return c-'';
return +c-'A';
}
void Input(int k){
char s[];
cin >> s;
int st = ;
REP(i,) {
st *= ;
st += Hash(s[i]);
}
a[k] = st;
} int dis[maxn],color[maxn];//dis表示距离，color相当于把从每个起点开始的搜索路径染色
queue <int> q;
int Solve(){
while(!q.empty()) q.pop();
memset(color,-,sizeof(color));
memset(dis,-,sizeof(dis));
REP(i,n){
if(dis[a[i]] != -) return ;
dis[a[i]] = ;
color[a[i]] = i;
q.push(a[i]);
}
int ans = 2e9,floor = 2e9; // ans 是答案 floor表示的是限定得到解的层数
while(!q.empty()){
int u = q.front(); q.pop();
REP(i,base){
int v = (u^(<<i));
if(dis[v] == -){
dis[v] = dis[u] + ;
color[v] = color[u];
// 只有当v的层数小于floor 才将其加入待搜队列
if(dis[v] <= floor) q.push(v);
}
else if(dis[v] != -){
if(color[v] == color[u]) continue; // 颜色相同则直接忽略
// return dis[v]+dis[u]+1; 直接返回是错误的！！！
ans = min(ans,dis[v]+dis[u]+);
floor = min(floor,dis[u]);
}
}
}
return ans;
} int main(){
int test;
cin >> test;
while(test --){
cin >> n;
memset(a,-,sizeof(a));
REP(i,n) Input(i);
cout << Solve() << endl;
}
}