HDU 4712 Hamming Distance (随机函数)

Hamming Distance

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

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

题意:N个十六进制数,将两个十六进制数转换成二进制数串后逐位异或,求最后得到的二进制串中含有1的最少的个数。

分析:其实这道想了很久就是不知道怎么去优化,因为数据也有10W,然而最后竟然告诉我是用随机数,想想最多也就20个串,每次随机选两个,得到正确答案的几率还是很大的,但不是100%,觉得应该取随机数的次数越大越能保证答案的正确性。

#pragma comprint(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<string>
#include<iostream>
#include<cstring>
#include<cmath>
#include<stack>
#include<queue>
#include<vector>
#include<map>
#include<stdlib.h>
#include<time.h>
#include<algorithm>
#define LL __int64
#define FIN freopen("in.txt","r",stdin)
using namespace std;
const int MAXN=100000+5;
const int MAX=1<<21;
const int INF=0x3f3f3f3f;
int a[MAX+5],num[MAXN];
int kase,n;
void init()
{
    for(int i=0;i<=MAX;i++)
    {
        int cnt=0;
        for(int j=0;j<21;j++)
            if(i & (1<<j))
                cnt++;
        a[i]=cnt;
    }
}
int main()
{
    init();
    scanf("%d",&kase);
    while(kase--)
    {
        scanf("%d",&n);
        for(int i=0;i<n;i++)
            scanf("%x",&num[i]);
        int ans=INF;
        srand( (unsigned)time( NULL ) );
        for(int i=0;i<900000;i++)
        {
            int x=rand()%n;
            int y=rand()%n;
            if(x==y) continue;
            ans=min(ans,a[num[x]^num[y]]);
        }
        printf("%d\n",ans);
    }
    return 0;
}

时间: 08-17

HDU 4712 Hamming Distance (随机函数)的相关文章

hdu 4712 Hamming Distance(随机数法)

d.汉明距离是使用在数据传输差错控制编码里面的,汉明距离是一个概念,它表示两个(相同长度)字对应位不同的数量, 我们以d(x,y)表示两个字x,y之间的汉明距离.对两个字符串进行异或运算,并统计结果为1的个数,那么这个数就是汉明距离. 给出N个串,求出其中最小的汉明距离(其中某2个串的汉明距离是最小的). s.随机数法... c.能不能过,看脸... #include<iostream> #include<stdio.h> #include<string.h> #inc

hduoj 4712 Hamming Distance 2013 ACM/ICPC Asia Regional Online —— Warmup

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 Problem Description (From wikipedia) For bina

461. Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Given two integers x and y, calculate the Hamming distance. Note:0 ≤ x, y < 2^31. Example: Input: x = 1, y = 4 Output: 2 Explanation:

UVa 729 - The Hamming Distance Problem

题目:构造n位01串,其中有m个1的所有组合. 分析:搜索.枚举.可以利用库函数,求解,也可以利用dfs求解:我这里采用位运算计算组合数. 说明:注意库啊! #include <iostream> #include <cstdlib> #include <cstdio> using namespace std; int S[20]; int main() { int T,N,M; while ( cin >> T ) for ( int t = 1 ; t

461. Hamming Distance(leetcode)

The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Given two integers x and y, calculate the Hamming distance. Note:0 ≤ x, y < 2^31. Example: Input: x = 1, y = 4 Output: 2 Explanation:

461. Hamming Distance【数学|位运算】

2017/3/14 15:23:55 The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Given two integers x and y, calculate the Hamming distance. 题目要求:求两个数字二进制位中同一位置不同bit的个数. 解法1  Java    利用1的移位依次匹配是否对

相似算法 ,Java实例9 - 汉明距离 Hamming Distance

Java实例9 - 汉明距离 Hamming Distance http://blog.csdn.net/kindterry/article/details/6581344 /**在信息理论中,两个等长字符串之间的汉明距离 * 是两个字符串对应位置上不同字符的个数, * 换句话说,汉明距离就是将一个字符串替换成另外一个字符串所需要替换的字符长度. *例如,1011101和1001001之间的汉明距离是2, *toned和roses之间的汉明距离是3. *汉明重量是字符串相对于同样长度的零字符串的

729 - The Hamming Distance Problem

// 题意: // 输入两个整数N, H,按照字典序输出所有长度为N,恰好包含H个1的01串 // 规模:1<=H<=N<=16 // 算法A:2^N枚举,输出1的个数为H的.采用递归枚举 // 从bits[d]开始确定,已经用了c0个0和c1个1 #include<cstdio> #include<cstring> #include<iostream> #include<string> #include<algorithm>

LeetCode解题思路:461. Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Given two integers x and y, calculate the Hamming distance. Note:0 ≤ x, y < 231. Example: Input: x = 1, y = 4 Output: 2 Explanation: 1