暴力或随机-hdu-4712-Hamming Distance - c++编程基础

TOP

暴力或随机-hdu-4712-Hamming Distance

2014-11-23 22:08:38 【大中小】浏览:9633次

题目大意：

求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  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#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];  
vectormyv[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< 
    
  
    
   
  
   2、因为最终结果肯定在1~20之间，结果域较小。得到结果的概率较大，所以随机两个串的标号，直接计算就可以，随机1000000次。预处理会减少枚举次数。
   
  
    
   
  
   代码：


 
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#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;  
}


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】

上一篇：HDU 4708 Rotation Lock Puzzle	下一篇：C++ Primer学习笔记2--c++标准库..