Readme

2732.Find-a-Good-Subset-of-the-Matrix

我们将每行用一个最多含5 bit的二进制数编码来表示它的每个列位置是0还是1. 为了增大复杂度，我们令列数是5.

首先，我们考虑两种特殊情况。如果有一行的编码是0，那么它自身组成的集合就符合条件。另外，如果有两行的编码的“交集”为零，那么这两行组成的集合也符合条件。

接下来考虑，如果任何两行的state的交集都不为0，那么会出现什么情况。

我们可以知道，想要有解，至少存在一行，最多含有两个bit 1. 理由是，如果所有的行都存在三个或以上的bit 1，那么无论选取哪些k行，总的bit 1的数就是大于等于3k，但是根据题意“任何一列的bit 1的数目不能超过行数的一半”，即总的bit 1的数目不能超过0.5k*5=2.5k，从而产生矛盾。不失一般性地，我们可以令某一行的编码是b00011。

回到之前的前提，“如果任何两行的编码的交集都不为0”，那么其他选取的k-1行里，在第0和1的位置上至少有一个bit 1。于是总体的这k行里，就有了至少k+1个bit 1。这就说明了在第0和1的位置上，不可能有任何一列的bit 1的个数少于等于floor(k/2)。得到矛盾，因此“任何两行的编码交集都不为0”情况下，是不可能有解的。

综上，我们只需要考察之前所述的两种特殊情况即可找出解，或者判定无解。对于第二种特殊情况，我们建立编码->行号的映射，就可以知道对于行A而言，是否存在与之符合条件的行B了。