学步园

语言：C++

描述：这道题其实一开始自己就是错误思维，题目就是通过最少的二进制位表示所有的数，也就是说存在自由组合的问题，不过存在这样的问题：如果一列二进制数被删去后，可以使列数减一来表示了所有的数了，但是有可能列数只会减一，输出的结果就是列数-1了，也就是说其他还有可能的情况都被封锁了。所以，原本的方法出现了错误，虽然测试数据过了，但是uva测试数据过不了，然后不得不根据刘汝佳书上的位向量法改写了一点才AC的

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
int count,P,N,s[110][20];
bool visit[20];
char str[110][20];
void print_subset(int cur)
{
    if(cur==P)
    {
        int c=0;
        for(int i=0; i<cur; i++)
            if(visit[i])
            {
                for(int j=0; j<N; j++)
                    str[j][c]=s[j][i]+'0';
                c++;
            }
        for(int i=0; i<N; i++) str[i][c]=0;
        for(int i=0; i<N-1; i++)
            for(int j=i+1; j<N; j++)
                if(!strcmp(str[i],str[j])) return;
        if(c<count) count=c;
        return ;
    }
    visit[cur]=true;
    print_subset(cur+1);
    visit[cur]=false;
    print_subset(cur+1);
}
int main()
{
    //freopen("a.txt","r",stdin);
    int n,i,j;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d%d",&P,&N);
        memset(str,0,sizeof(str));
        for(i=0; i<N; i++)
            for(j=0; j<P; j++)
                scanf("%d",&s[i][j]);
        count=P;
        print_subset(0);
        printf("%d\n",count);
    }
    return 0;
}