leetcode 第277场周赛

T1 元素计数

for for，水题莫忘暴力

T4 基于陈述统计最多好人数

题意简述

好人说真话，坏人不确定。给出$statements[i][j]$表示$i$号人对$j$号人的好坏评价，$0$坏$1$好。求好人最多有几个。

算法分析

由于总人数$n<=15$，直接二进制枚举所有人的好坏情况，判断有无冲突即可。

代码实现

class Solution {
public:
    int maximumGood(vector<vector<int>>& statements) {
        int n = statements.size();
        int ans = 0;
        for (int mask = 1; mask < (1 << n); ++mask) {
            bool check = [&]() {
                for (int i = 0; i < n; ++i) {
                    for (int j = 0; j < n; ++j) {
                        if (i == j) {
                            continue;
                        }
                        if (statements[i][j] == 0) {
                            if ((mask & (1 << i)) && (mask & (1 << j))) {
                                return false;
                            }
                        }
                        else if (statements[i][j] == 1) {
                            if ((mask & (1 << i)) && !(mask & (1 << j))) {
                                return false;
                            }
                        }
                    }
                }
                return true;
            }();
            if (check) {
                ans = max(ans, __builtin_popcount(mask));
            }
        }
        return ans;
    }
};
Copy