hdu 4712 Hamming Distance 随机化算法

缘起

日常水题 ~ hdu 4712 Hamming Distance

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
给定你N（N<=1e5）个长度为5的16进制串. 要求出这些16进制串转换为2进制串之后最小的 Hamming 距离.

【输入】
多样例, 第一行是样例数. 然后每个样例开始于一个N(2<=N<=1e5), 即16进制串的个数.然后是N行，
每行都是一个长度为5的16进制串. 例如12345表示的二进制串是00010010001101000101

【输出】
对每个样例，输出最小的两个16进制串之间的Hamming距离. 所谓Hamming距离指的是两个16进制串转换为2进制
串之后, 这两个二进制串做亦或运算之后, 1的个数.

【样例输入】
2
2
12345
54321
4
12345
6789A
BCDEF
0137F

【样例输出】
6
7

【限制】
3s

注意, n个长度为20的01比特串. 两两亦或的话, 可以多达 O(n^2)种可能, 但是20很小啊~ 这意味着，这多达O(n^2)种可能其实只有20种取值. 所以我们随机选取10w种组合, 取最小就是答案了~ 可以说，本题如果想到了, 就是一道水题~ 没想到, 卧槽~ 好难啊~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
//#include "stdafx.h"
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <ctype.h>
#include <algorithm>
using namespace std;
//#define LOCAL

int n;
char a[100005][6];

int f(char c)
{
	return isdigit(c)?(c^48):c-'A'+10;
}

int zz(int x, int y) // 求a[x]和a[y]亦或的结果
{
	int ans = 0; 
	for (int i = 0,xx,yy;i<5;i++)
	{
		xx = f(a[x][i]);
		yy = f(a[y][i]);
		xx^=yy;
		while(xx)
		{
			ans+=xx&1;
			xx>>=1;
		}
	}
	return  ans;
}

int kk()
{
	int ans = 25;
	for (int i = 0,x,y;i<150000; i++) // 15w次随机选择,次数少了的话会wa
	{
		x = rand()%n, y = rand()%n;
		if (x==y) // x==y的话, 那就是0, 肯定不能这样啦~
		{
			continue;
		}
		ans = min(ans, zz(x,y));
	}
	return ans;
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	srand((int)(time(0)));
	int kase;
	scanf("%d", &kase);
	while(kase--)
	{
		scanf("%d", &n);
		for (int i = 0;i<n;i++)
		{
			scanf("%s", a[i]);
		}
		printf("%d\n", kk());
	}
	return 0;
}

ac结果

Status Accepted
Time 748ms
Memory 2328kB
Length 950
Lang C++
Submitted 2019-10-14 21:55:15
Shared
RemoteRunId 30923425