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

发布时间:2016-12-11 10:34:42 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"暴力或随机-hdu-4712-Hamming Distance",主要涉及到暴力或随机-hdu-4712-Hamming Distance方面的内容,对于暴力或随机-hdu-4712-Hamming Distance感兴趣的同学可以参考一下。

题目链接: 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; }

上一篇:spring [email protected]
下一篇:百度地图api接口poi检索示例----并在信息框显示经纬度

相关文章

相关评论