暴力或隨機-hdu-4712-Hamming Distance

題目大意：   求n個20位0、1二進制串中，兩兩抑或最少的1的個數。   解題思路：   兩種解法：   1、20位 一共有1<<20個狀態，先預處理1的個數，並把相同的1的個數的狀態放到一個集合裡。根據0和其它數抑或得相同，1和其它數抑或得反，從小到大枚舉1的個數的狀態P，用其中一個串A來和P相抑或，得到B ，如果B在給定的串中，說明A^B中1的個數為P中1的個數。   這種解法的最壞時間復雜度為C(20,10)*n*20  很暴力，數據很弱。   代碼：

#include<iostream>  
#include<cmath>  
#include<cstdio>  
#include<cstdlib>  
#include<string>  
#include<cstring>  
#include<algorithm>  
#include<vector>  
#include<map>  
#include<set>  
#include<stack>  
#include<list>  
#include<queue>  
#define eps 1e-6  
#define INF 0x3fffffff  
#define PI acos(-1.0)  
#define ll __int64  
#define lson l,m,(rt<<1)  
#define rson m+1,r,(rt<<1)|1  
#pragma comment(linker, "/STACK:1024000000,1024000000")  
using namespace std;  
  
#define Maxn 110000  
//0和a抑或得相同  
//1和a抑或得相反  
bool hav[1<<20];  
vector<int>myv[25]; //myv[i]表示含有i個1的狀態  
int sa[Maxn];  
  
int main()  
{  
   int t,n;  
  
   for(int i=0;i<(1<<20);i++)  
   {  
       int num=0;  
       for(int j=0;j<20;j++)  
          if(i&(1<<j))  
            num++;  
       myv[num].push_back(i); //含1的個數相同的狀態放到一個集合裡  
   }  
   scanf("%d",&t);  
   while(t--)  
   {  
       scanf("%d",&n);  
       memset(hav,false,sizeof(hav));  
       bool flag=false;  
       for(int i=1;i<=n;i++)  
       {  
           scanf("%X",&sa[i]);  
           if(hav[sa[i]])  
              flag=true;  
           else  
              hav[sa[i]]=true;  
       }  
       if(flag)  
       {  
           puts("0");  
           continue;  
       }  
       for(int i=1;i<=20&&!flag;i++)  
            for(int j=1;j<=n&&!flag;j++)  
            {  
                for(int k=0;k<myv[i].size()&&!flag;k++)  
                {  
                    if(hav[sa[j]^myv[i][k]])  
                    {  
                        printf("%d\n",i);  
                        flag=true;  
                    }  
                }  
            }  
   }  
   return 0;  
}  

 
#include<iostream>  
#include<cmath>  
#include<cstdio>  
#include<cstdlib>  
#include<string>  
#include<cstring>  
#include<algorithm>  
#include<vector>  
#include<map>  
#include<set>  
#include<stack>  
#include<list>  
#include<queue>  
#define eps 1e-6  
#define INF 0x3fffffff  
#define PI acos(-1.0)  
#define ll __int64  
#define lson l,m,(rt<<1)  
#define rson m+1,r,(rt<<1)|1  
#pragma comment(linker, "/STACK:1024000000,1024000000")  
using namespace std;  
  
#define Maxn 110000  
int sa[Maxn];  
bool hav[1<<20];  
  
int Cal(int a)  
{  
    int res=0;  
  
    while(a)  
    {  
        if(a&1)  
            res++;  
        a>>=1;  
    }  
    return res;  
}  
int main()  
{  
   int t,n;  
  
   scanf("%d",&t);  
   while(t--)  
   {  
       scanf("%d",&n);  
       memset(hav,false,sizeof(hav));  
       bool flag=false;  
       for(int i=1;i<=n;i++)  
       {  
           scanf("%X",&sa[i]);  
           if(hav[sa[i]])  
              flag=true;  
           else  
              hav[sa[i]]=true;  
       }  
       if(flag)  
       {  
           printf("0\n");  
           continue;  
       }  
       int ans=20;  
      // srand((unsigned)time(NULL));  
       for(int i=1;i<=1000000;i++)  
       {  
           int j=rand()%n+1;  
           int k=rand()%n+1;  
           if(j==k)  
              continue;  
           ans=min(ans,Cal(sa[j]^sa[k]));  
       }  
       printf("%d\n",ans);  
  
  
   }  
   return 0;  
}