HDU 4712 Hamming Distance(随机算法）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4712

解题报告：输入n个数，用十六进制的方式输入的，任意选择其中的两个数进行异或，求异或后的数用二进制表示后1的个数最小的是多少？（n<=100000)

这题看了解题报告，大家都说用随机算法，试过了，随机100000次就过了，50000次都不行，但还是不懂这样怎么可以，唯一的解释就是这个值域也就是结果一共只有21个，

得出正确的结果的可能性很大，但是并不能100%保证结果是对的。无语第一次碰见这种算法。

 1 #include<cstdio>
 2 #include<time.h>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 using namespace std;
 7 const int maxn = 1<<21;
 8 
 9 int num1[maxn+5];
10 int que[100005];
11 void dabiao()
12 {
13     for(int i = 0;i <= maxn;++i)
14     {
15         int t = 0;
16         for(int j = 0;j < 21;++j)
17         if(i & (1 << j)) t++;
18         num1[i] = t;
19     }
20 }
21 int main()
22 {
23     dabiao();
24     int T,n;
25     scanf("%d",&T);
26     while(T--)
27     {
28         scanf("%d",&n);
29         for(int i = 0;i < n;++i)
30         scanf("%x",&que[i]);
31         int ans = 0x7fffffff,suiji = 100000;
32         srand( (unsigned)time( NULL ) );  //不加种子就过不了
33         while(suiji--)
34         {
35             int r1 = rand() % n;
36             int r2 = rand() % n;
37             if(r1 != r2)
38             ans = min(ans,num1[que[r1]^que[r2]]);
39         }
40         printf("%d
",ans);
41     }
42     return 0;
43 }

View Code