首页 > 代码库 > HDU 4217 Hamming Distance 随机化水过去
HDU 4217 Hamming Distance 随机化水过去
Hamming Distance
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 1569 Accepted Submission(s): 616
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.
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
2212345543214123456789ABCDEF0137F
Sample Output
67
这道题的正常做法是O（n^2）的，很显然这个做法会大大方方的T掉
但是我们可以用随机化，然后悄悄不说话的水过去= =
#include <iostream>#include <stdio.h>#include <algorithm>#include <string.h>#include <time.h>using namespace std;#define N 100000char str[N+10][10];int mark[20][20]; //make中存 i^j 的1的个数int arr[]={0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4}; //0-F 中1的个数int charToHex(char ch) //将0-F字符转换成10进制数计算{ if(isdigit(ch)) return ch-‘0‘; return ch-‘A‘+10;}void getMark() //求mark数组{ int i,j,s; for(i=0;i<16;i++) { for(j=i;j<16;j++) { s=i^j; mark[i][j]=mark[j][i]=arr[s]; } }}int geths(int x,int y) //求x到y的Hamming distance{ int i,sum=0; for(i=0;i<5;i++) { int xx = charToHex(str[x][i]); int yy = charToHex(str[y][i]); sum+=mark[xx][yy]; } return sum;}int main(){ int t; getMark(); scanf("%d",&t); while(t--) { int n; scanf("%d",&n); int i; for(i=0;i<n;i++) { scanf("%s",str[i]); } srand(time(NULL)); int x,y,mins=100; for(i=0;i<900000;i++) //随机900000次基本能过，在不超时的前提下，随机次数越多越好 { x=rand()%n; y=rand()%n; if(x==y) continue; int temp = geths(x,y); if(mins>temp) mins=temp; } printf("%d\n",mins); } return 0;}/*2212345543214123456789ABCDEF0137F*/
HDU 4217 Hamming Distance 随机化水过去
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。