HDU 4712 Hamming Distance(随机算法）

时间：2022-06-25 15:24:48

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

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

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

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

 #include<cstdio>

 #include<time.h>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 const int maxn = <<;

 int num1[maxn+];

 int que[];

 void dabiao()

 {

     for(int i = ;i <= maxn;++i)

     {

         int t = ;

         for(int j = ;j < ;++j)

         if(i & ( << j)) t++;

         num1[i] = t;

     }

 }

 int main()

 {

     dabiao();

     int T,n;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d",&n);

         for(int i = ;i < n;++i)

         scanf("%x",&que[i]);

         int ans = 0x7fffffff,suiji = ;

         srand( (unsigned)time( NULL ) );  //不加种子就过不了

         while(suiji--)

         {

             int r1 = rand() % n;

             int r2 = rand() % n;

             if(r1 != r2)

             ans = min(ans,num1[que[r1]^que[r2]]);

         }

         printf("%d\n",ans);

     }

     return ;

 }

相关文章