HDUOJ---Hamming Distance(4712)

Hamming Distance

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65535/65535 K (Java/Others) Total Submission(s): 916    Accepted Submission(s): 335

Problem Description

(From wikipedia) For binary strings a and b the Hamming distance is equal to the number of ones in a XOR b. For calculating Hamming distance between two strings a and b, they must have equal length. Now given N different binary strings, please calculate the minimum Hamming distance between every pair of strings.

Input

The first line of the input is an integer T, the number of test cases.(0<T<=20) Then T test case followed. The first line of each test case is an integer N (2<=N<=100000), the number of different binary strings. Then N lines followed, each of the next N line is a string consist of five characters. Each character is '0'-'9' or 'A'-'F', it represents the hexadecimal code of the binary string. For example, the hexadecimal code "12345" represents binary string "00010010001101000101".

Output

For each test case, output the minimum Hamming distance between every pair of strings.

Sample Input

2

2

12345

54321

4

12345

6789A

BCDEF

0137F

Sample Output

6

7

Source

2013 ACM/ICPC Asia Regional Online —— Warmup

 随机算法,第一次接触......

这里需要具备的知识是:(1)16进制的输入输出...... (2)查了以下资料,有关汉明距离的算法:

对于两个字串...可以是数组,字符,求其汉明距离的是对两个字串求异或^。。。

该部分的代码为:

/*
  ussigned dist(unsigned a, unsigned b)
  {
    int val=a^b,da=0;
    while(val)
    {
     val ^= val -1;
     da++;
    }
    return 0;
  }
*/

随机算法需要知道的几个函数srand(),rand(),---》头文件为stdlib.h

时间的头文件为time.h-----time();

所以代码为:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<ctime>
 5 #include<algorithm>
 6 #define maxn 100000
 7 using namespace std;
 8 int dist(int a,int b)   //gongshi
 9 {
10     int val=a^b,distance=0;
11     while(val)
12     {
13         ++distance;
14         val &= val - 1 ;
15     }
16  return distance;
17 }
18 int Hex[maxn+1];
19 int main()
20 {
21     int t,i,n,min,x,y,c,cnt;
22 //time_t t1;
23     scanf("%d",&t);
24     while(t--)
25     {
26      scanf("%d",&n);
27      for(i=0;i<n;i++)
28      scanf("%X",&Hex[i]);
29         srand((unsigned)time(NULL));
30      for(cnt=i=0;i<maxn;i++)
31      {
32          x=rand()%n;
33          y=rand()%n;
34          if(x!=y)
35          {
36            c=dist(Hex[x],Hex[y]);
37            if(cnt==0||min>c)
38               min=c,cnt=1;
39            else
40                 if(min==0) break;
41          }
42      }
43      printf("%d\n",min);
44     }
45  return 0;
46 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏美团技术团队

HDFS NameNode内存详解

前言 《HDFS NameNode内存全景》中,我们从NameNode内部数据结构的视角,对它的内存全景及几个关键数据结构进行了简单解读,并结合实际场景介绍了N...

48160
来自专栏程序员互动联盟

一个程序员的奋斗历程

也许,你还为你的未来感到迷茫,也许,你还对程序员的历程感到神奇.就让我们来看看这位程序员的奋斗历程好了. 这些日子我一直在写一个实时操作系统内核,已有小成了,...

47480
来自专栏杨建荣的学习笔记

关于连续登录的问题探究

经常会在数据统计中取筛选连续性的数据,比如筛选连续三个月都登录的用户, 数据形式如下: 1 111 222 333 2 111 3 111 222 4 111 ...

366120
来自专栏腾讯研究院的专栏

大数据时代商业银行的策略

  尽管大数据对商业银行的影响目前而言还比较小,但从发展趋势看,要充分认识大数据的颠覆性影响。各银行必须未雨绸缪,早做布局,从管理体系建设、具体运用模式方面不...

432130
来自专栏机器学习AI算法工程

整站40万条房价数据并行抓取,可更换抓取城市

这次的爬虫是关于房价信息的抓取,目的在于练习10万以上的数据处理及整站式抓取。 数据量的提升最直观的感觉便是对函数逻辑要求的提高,针对Python的特性,谨慎...

37250
来自专栏程序员互动联盟

老码农拍着脑袋总结的法子

1.扎实的基础。数据结构、离散数学、编译原理,这些是所有计算机科学的基础,如果不掌握他们,很难写出高水平的程序。据我的观察,学计算机专业的人比学其他专业的人更能...

394150
来自专栏Ryan Miao

ArrayList源码阅读

前言 数组是我们最常用最简单的数据结构,Java里对数组做了一个简单的包装,就是ArrayList,提供自动扩容的功能。 最常用法 list在我们日常代码中最为...

30280
来自专栏程序员互动联盟

【答疑释惑】C语言里面栈和堆的区别

很多初学者朋友对C语言里面的堆和栈理解的不是太清楚,模模糊糊。他们到底有哪些区别呢?我认为主要从以下几根方面来了解他们的不同之处: 1,变量位置:栈和堆都是程...

438120
来自专栏程序员互动联盟

【编程入门】C语言堆栈入门——堆和栈的区别

在计算机领域,堆栈是一个不容忽视的概念,我们编写的C语言程序基本上都要用到。但对于很多的初学着来说,堆栈是一个很模糊的概念。堆栈:一种数据结构、一个在程序运行时...

62360
来自专栏机器学习AI算法工程

知乎观点收集:关于机器学习和数据挖掘找工作

甲:数据挖掘 很多地方招聘还是挺喜欢这样专业的,但是前提是你得过笔试关。 为了笔试,学习C和数据结构 数据挖掘的时候学习算法和推理机制等,看看数据分析,神经网络...

51970

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励