暴力或随机-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;  
}  

补充：软件开发 , C++ ,