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

时间：2024-07-08 18:03:44

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=4712

题目大意：

求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;

}

2、因为最终结果肯定在1~20之间，结果域较小。得到结果的概率较大，所以随机两个串的标号，直接计算就可以，随机1000000次。预处理会减少枚举次数。

代码：

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

}

相关文章