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
",ans);
56     }
57     return 0;
58 }

View Code

　　下面是一份看上去更简洁更暴力的代码，是我从网上找的，因为很久之前找的，所以都不知道出处了。

　　它的思想是这样的：因为是p位二进制，所以范围在0 ~ 2^p 。并且p是不大于15的。所以可以直接枚举。对于i属于[0,2^p ],如果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
",ans);
    }
    return 0;
}

View Code