首页 > 代码库 > uva11205 The broken pedometer 子集生成
uva11205 The broken pedometer 子集生成
PS:此题我在网上找了很久的题解，发现前面好多题解的都是没有指导意义的。后来终于找到了一篇好的题解。
好的题解的链接：http://blog.csdn.net/u013382399/article/details/23516051
我在他的解题的基础上，有了自己的理解。
题意：
有n(100以内)个位数为p(15以内)的二进制数，最少需要几个二进制位就可以把他们区分开。
题目分析：
数据较小，用的是暴力的方法，就是枚举每一个二进制位取或不取。就是相当于是枚举矩阵的列。
刘汝佳的小白书120页提到的子集生成就是这样的枚举。这道题我用了位向量法。
对于此题，某一列（一个二进制位或者说是某一盏灯）取或不取可以这样理解。不取就认为所有的n个数中这一位数是相同的，可以是全部赋值为1也可以是0。
然后就是判断这n个数中有没有重复的数。转化为字符串好比较，当然也可以是转化为进制数比较（原来的数认为是二进制数）。
我根据这个意思，自己写了一份代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<map> 6 using namespace std; 7 8 int n,p,cur; 9 int ans;10 int a[110][20];11 char s[110][20];12 bool vis[20];13 map<string,int > st;14 int DFS(int x)15 {16 if(x==p)17 {18 int t=0;19 for(int i=0;i<n;i++)20 for(int j=0;j<p;j++)21 if(vis[j]){t++;s[i][j]=a[i][j]+48;}22 else s[i][j]=48;23 for(int i=0;i<n;i++) s[i][p]=0;24 st.clear();25 for(int i=0;i<n;i++)26 {27 //puts(s[i]);28 if(!st[s[i]]) st[s[i]]=1;29 else return 0;30 }31 t/=n;32 ans=min(t,ans);33 return 0;34 }35 vis[x]=0;36 DFS(x+1);37 vis[x]=1;38 DFS(x+1);39 return 1;40 }41 int main()42 {43 //freopen("test.txt","r",stdin);44 int cas;45 scanf("%d",&cas);46 while(cas--)47 {48 scanf("%d%d",&p,&n);49 for(int i=0;i<n;i++)50 for(int j=0;j<p;j++)51 scanf("%d",&a[i][j]);52 ans=p;53 memset(vis,0,sizeof(vis));54 DFS(0);55 printf("%d\n",ans);56 }57 return 0;58 }
下面是一份看上去更简洁更暴力的代码，是我从网上找的，因为很久之前找的，所以都不知道出处了。
它的思想是这样的：因为是p位二进制，所以范围在0 ~ 2p 。并且p是不大于15的。所以可以直接枚举。对于i属于[0,2p ],如果n个数中每个数 & i的结果没有重复，就代表i是一个可能的解，只要把i这个数二进制位为1的个数求出来，就是一个可能的答案。最后取最小值。这个的原理，我不知道，但是可以编程来验证。
#include<iostream>#include<cstring>#include<cstdio>#include<cmath>#include<algorithm>#include<set>using namespace std;int a[110];int p,n;set<int > s;int main(){ //freopen("test.txt","r",stdin); int ca,i,j,k,ans,t,flag,r; scanf("%d",&ca); while(ca--) { memset(a,0,sizeof(a)); scanf("%d%d",&p,&n); for(i=0;i<n;i++) for(j=0;j<p;j++) { scanf("%d",&t); a[i]=a[i]*2+t; } ans=15; for(i=0;i<(1<<p);i++) { flag=0; s.clear(); for(j=0;j<n;j++) { t=i&a[j]; if(s.find(t)!=s.end()) {flag=1;break;} s.insert(t); } if(!flag) { r=0; for(k=0;k<p;k++) if(i&(1<<k)) r++; if(r<ans) ans=r; } } printf("%d\n",ans); } return 0;}
uva11205 The broken pedometer 子集生成
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。