uva 11205 - The broken pedometer

二进制枚举。暴力的好题，巧用二进制去枚举。

就是求出最少需要多少位可以表示出这些数字并区分，（就是取最少的位数使每一个串数字还是不同）

然后我们把最大范围内每一个二进制的数枚举出来，然后判断最少几位能使上面的01串无重复的表达。

将输入的一串01串用存入一个数中，用二进制看的话就是101010之类的。

具体看代码：

#include<cstdio>
#include<cstring>
const int MAXN=110;
const int MAXNp=(1<<15)+10;
int a[MAXN];
bool vis[MAXNp];
int count(int n){                       //统计该数字中有多少个1，即显示哪几位
    int sum=0;
    while(n){
        if(n & 1) sum++;
        n=n>>1;
    }
    return sum;
}
int main(){
    //freopen("in.txt","r",stdin);
    int T;
    scanf("%d",&T);
    while(T--){
        int P,N,temp;
        scanf("%d%d",&P,&N);
        for(int i=0;i<N;i++){
            scanf("%d",&a[i]);
            for(int j=1;j<P;j++){
                scanf("%d",&temp);
                a[i] = (a[i]<<1)+temp;      //位运算直接将01串存入一个数字中
            }
        }
        int ans=MAXN,up=1<<P;
        for(int i=0;i<up;i++){              //枚举到最大的数，即p位用二进制表示的最大数
            int bits=count(i);
            if(bits>=ans) continue;         //如果显示的1已经大于当前最小值，不用循环
            memset(vis,false,sizeof(vis));
            int j;
            for(j=0;j<N;j++){               //判断显示这么多位是否有重复的字符串
                int pos= a[j] & i;
                if(vis[pos]) break;
                else vis[pos]=true;
            }
            if(j<N) continue;               //如果小于N，则为提前退出循环，继续判断
            ans = bits;
        }
        printf("%d\n",ans);
    }
    return 0;
}

uva 11205 - The broken pedometer,布布扣,bubuko.com

uva 11205 - The broken pedometer

原文：http://blog.csdn.net/u013791747/article/details/20550727