LeetCode-2397 Maximum Rows Covered by Columns

Description

给定一个\(n\)行\(m\)列的01矩阵\(matrix\)，以及一个整数\(x\)。

你可以选取\(x\)个列，如果这些列能完全覆盖某行全部的1，那就认为是命中该行。

求最多的命中行数。

NOTE: 如果该行是全0，也算命中。

Constraints

\(1 \le n, m \le 12\)
\(1 \le x \le m\)
\(0 \le matrix[i][j] \le 1\)

Solution

~~答案具有单调性，直接二分答案。~~

我是傻逼。直接取max就好了枚举个屁的答案。

写都写了，还是贴出来吧，下次做题记得带脑子。

Code

class Solution {
public:
    int maximumRows(vector<vector<int>>& matrix, int numSelect) {
        int row = matrix.size();
        int col = matrix[0].size();
        int lo = 0, hi = row;

        vector<int> needs(row);
        for(auto &need : needs) {
            auto &mi = matrix[distance(needs.data(), &need)];
            need = accumulate(mi.begin(), mi.end(), 0);
        }

        auto for_set = [&](int S, auto cond, int target) {
            for(int s = 0; s < S; ++s) {
                if(cond(s, target)) return true;
            }
            return false;
        };

        auto cond = [&](int s, int target) {
            auto popcount = [c = 0, t = 0](auto v) mutable {
                while(t = v&-v) c++, v-=t;
                return c;
            };
            if(popcount(s) != numSelect) return false;
            int cnt[15] {};
            for(int i = 0; i < col; ++i) {
                if(s >> i & 1 ^ 1) continue;
                for(int j = 0; j < row; ++j) {
                    cnt[j] += matrix[j][i];
                }
            }
            for(auto &need : needs) {
                auto idx = distance(needs.data(), &need);
                target -= (cnt[idx] == need);
            }
            return target <= 0;
        };

        auto check = [&](int target) {
            return for_set(1 << col, cond, target);
        };

        while(lo < hi) {
            auto mid = lo + (hi - lo + 1) / 2;
            if(check(mid)) lo = mid;
            else hi = mid - 1;
        }
        return lo;
    }
};

Link

LeetCode-2397 Maximum Rows Covered by Columns