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