题意：

有n个长为m的各不相同的二进制数(允许存在前导0)，别人已经事先想好n个数中的一个数W，你要猜出这个数。

每次只可以询问该数的第K为是否为1.

问采用最优询问策略，则最少需要询问多少次能保证猜到。

比如有1100 和 0110两个数，只需要询问第一或第三位数是否为1，即可猜中，因此答案为1.

分析：

d(s, a)表示已经询问了的集合s，在已经询问了的集合中W中为1的集合为a，还需要询问多少次。

如果下一次询问第k位，则询问次数为：

　　

然后取所有k里的最小值即可。

 

预处理：

对于每个s和a，可以先把满足条件的数的个数记录下来，保存在cnt[s][a]里。

 

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 using namespace std; 5  6 const int maxm = 12, maxn = 130; 7 char object[maxn][maxm + 10]; 8 int d[1<
         
          <
          
           = 1 && cnt[s2][a2] >= 1)27             {28                 int need = max(dp(s2, a2), dp(s2, a)) + 1;29                 ans = min(ans, need);30             }31         }32     }33     return ans;34 }35 36 int main()37 {38     //freopen("in.txt", "r", stdin);39     while(scanf("%d%d", &m, &n) && n)40     {41         ++kase;42         for(int i = 0; i < n; ++i)43             scanf("%s", object[i]);44         memset(vis, 0, sizeof(vis));45         memset(cnt, 0, sizeof(cnt));46         for(int i = 0; i < n; ++i)47         {48             int feature = 0;49             for(int f = 0; f < m; ++f)50                 if(object[i][f] == '1') feature |= (1 << f);51             for(int s = 0; s < (1<