hdu 4712

发布时间:2017-4-25 5:18:20 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"hdu 4712",主要涉及到hdu 4712方面的内容,对于hdu 4712感兴趣的同学可以参考一下。

http://acm.hdu.edu.cn/showproblem.php?pid=4712 分析: 海明距离就是求两个数相应的位按位与之后,在二进制表示中1的个数,海明距离原理见  http://blog.sina.com.cn/s/blog_663457ed01017bry.html              该题还有一个就是数据量较大不能够用枚举来做,当时也没做出来,然后发现可以用随机数来模拟,又不想rand()产生的是伪随机数,WA~               然后就加了srand()函数; 代码:              //hdu 4712 Hamming Distance #include <iostream> #include <stdlib.h> #include <math.h> #include <string.h> #include <ctype.h> #include <ctime> using namespace std; #define INF 0x3f3f3f3f int cmp[16][16]; char p[1000005][6]; void init() { for(int i=0;i<16;i++) for(int j=0;j<16;j++){ int ans=0; int tmp=i^j; for(int k=0;k<4;k++) if((1<<k)&tmp) ans++; cmp[i][j]=ans; } } int hamdist(int q,int w) { int a,b; int ret = 0; for(int i=0;i<5;i++) { char x = p[q][i]; char y = p[w][i]; if(isdigit(x)) a=x-'0'; else a=x-'A'+10; if(isdigit(y)) b=y-'0'; else b=y-'A'+10; ret += cmp[a][b]; } return ret; } int main() { int T,N; int ans; cin>>T; init(); while(T--){ cin>>N; ans=INF; for(int i=0;i<N;i++) cin>>p[i]; srand((unsigned)time(NULL)); for(int i=1;i<=100000;i++){ int a=rand()%N; int b=rand()%N; if(a==b) continue; int tmp=hamdist(a,b); if(tmp<ans) ans=tmp; } cout<<ans<<endl; } return 0; }

上一篇:安装Tomcat服务,并检验安装是否成功
下一篇:hdu 3259 An interesting mobile game (dfs+bfs+模拟)

相关文章

关键词: hdu 4712

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款