Hamming Distance(随机算法)

http://acm.hdu.edu.cn/showproblem.php?pid=4712

题意：计算任意两个十六进制的数异或后1的最少个数。

思路：用随机数随机产生两个数作为下标，记录这两个数异或后1的个数，输出1的个数最少是多少。

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <time.h>
 4 #include <math.h>
 5 
 6 using namespace std;
 7 const int N=100002;
 8 const int INF=1<<29;
 9 int f[N];
10 int main()
11 {
12     int t;
13     scanf("%d",&t);
14     while(t--)
15     {
16         int n,ans = INF;
17         scanf("%d",&n);
18         for (int i = 0; i < n; i ++)
19             scanf("%x",&f[i]);
20         srand((unsigned)time(NULL));
21         for (int i = 0; i < N*10; i ++)
22         {
23             int a = rand()%n;
24             int b = rand()%n;
25             if (a==b)
26                 continue ;
27             int t = f[a]^f[b];
28             int temp = __builtin_popcount(t);
29             ans = min(ans,temp);
30         }
31         printf("%d
",ans);
32     }
33     return 0;
34 }

View Code