从二进制枚举 follow up 到二分图判定，有点意思

ACM算法日常

发布于 2022-02-10 00:59:44

40300

代码可运行

文章被收录于专栏：ACM算法日常ACM算法日常

运行总次数：0

代码可运行

这次周赛前三题比较水，第四题看到数据范围想到二进制枚举之后也不难做

不过我在评论区看到有人提到了 T4 对应的 follow-up 题，是 codeforces div2 的 D 题，涉及到了图论建模和二分图判定，一起来看一看吧

涉及知识点：哈希表，二进制枚举，二分图判定

5989. 元素计数

给你一个整数数组 nums，统计并返回在 nums 中同时具有一个严格较小元素和一个严格较大元素的元素数目。

题解

计算所有不等于严格小和严格大的元素个数即可，遍历一遍就行，时间复杂度 $\mathcal{O}(n)$

// cpp11
class Solution {
public:
    int countElements(vector<int>& nums) {
        int mini = *min_element(nums.begin(), nums.end());
        int maxx = *max_element(nums.begin(), nums.end());
        int ans = 0;
        for (auto& i: nums) {
            if (i > mini && i < maxx) ans++;
        }
        return ans;
    }
};

5991. 按符号重排数组

给定一个下标从 0 开始的整数数组 nums，数组长度 $n$ 为偶数，由数目相等的正整数和负整数组成

你需要重排 nums 中的元素，使修改后的数组满足下述条件

任意连续的两个整数符号相反
对于符号相同的所有整数，保留它们在 nums 中的顺序
重排后数组以正整数开头。

返回修改后的数组

数据规定 $1\leq n\leq 2\cdot 10^5$

题解

用两个数组存放正数和负数，然后遍历一遍放到答案数组即可，时间复杂度 $\mathcal{O}(n)$

// cpp11
class Solution {
public:
    vector<int> rearrangeArray(vector<int>& nums) {
        vector<int> pos, neg;
        for (auto& i: nums) {
            if (i > 0) pos.push_back(i);
            else neg.push_back(i);
        }
        int n = static_cast<int>(pos.size());
        vector<int> ans;
        for (int i = 0; i < n; ++i) {
            ans.push_back(pos[i]);
            ans.push_back(neg[i]);
        }
        return ans;
    }
};

5990. 找出数组中的所有孤独数字

给定一个长度为 $n$ 的整数数组，请你返回数组中所有只出现了一次，且相邻数都不在数组中的元素数据规定 $1\leq n\leq 10^5$

题解

直接哈希表模拟即可，时间复杂度 $\mathcal{O}(n)$

// cpp11
class Solution {
public:
    vector<int> findLonely(vector<int>& nums) {
        unordered_map<int, int> mp;
        for (auto& i: nums) mp[i]++;
        vector<int> ans;
        for (auto& i: nums) if (mp[i] == 1 && !mp[i - 1] && !mp[i + 1]) ans.push_back(i);
        return ans;
    }
};

5992. 基于陈述统计最多好人数

给定 $n$ 个人，可能是好人也可能是坏人，好人一定说真话，坏人不一定说真话

每个人都对另外 $n - 1$ 个人有一个陈述，分别为

$0$ 表示坏人
$1$ 表示好人
$2$ 表示不了解于是我们得到一个 $n\times n$ 的矩阵，表示各个陈述，根据这个陈述表格，请你计算好人的最大可能的数量

数据规定 $1\leq n\leq 15$

题解

这个数据范围一看就是进制枚举，一开始看错题目了，以为坏人的陈述要么全真要么全假，于是弄了三进制枚举，结果 wa 了

事实上，坏人的每一条陈述都可能为真，也可能为假，但是好人的每一条陈述一定为真，所以我们根据好人的陈述来判断就行

考虑二进制枚举，枚举每个人为好人的情况，然后根据好人的陈述判断枚举是否自洽，枚举的过程维护好人的最大值即可，时间复杂度 $\mathcal{O}(n^2\cdot 2^n)$

// cpp11
class Solution {
public:
    int maximumGood(vector<vector<int> >& sta) {
        int n = static_cast<int>(sta.size());
        int ans = 0;
        for (int i = 0; i < (1 << n); ++i) {
            bool flag = true;
            int cnt = 0;
            for (int j = 0; j < n; ++j) {
                if ((i >> j) & 1) {  // j 是好人
                    for (int k = 0; k < n; ++k) {
                        if (sta[j][k] == 2) continue;
                        if (sta[j][k] != ((i >> k) & 1)) {
                            flag = false;
                            break;
                        }
                    }
                    ++cnt;
                }
                if (!flag) break;
            }
            if (flag) ans = max(ans, cnt);
        }
        return ans;
    }
};

「T4 follow up」如果坏人说的话一定为假呢？

给定 $n$ 个人，和 $m$ 条关系，每一条关系由 $i,\ j,\ k$ 组成，表示 $i$ 说 $j$ 是好人/坏人， $k = 0,\ 1$

如果 $i$ 是好人，那么他说的话一定为真话
如果 $i$ 是坏人，那么他说的话一定为假话

根据这 $m$ 条陈述计算最大的好人数量，如果陈述有矛盾，输出 $-1$ 数据规定 $1\leq n\leq 2\cdot 10^5,\ 1\leq m\leq 5\cdot 10^5$

题解

我们发现

如果 $i$ 说 $j$ 是坏人，那么无论 $i$ 是好人还是坏人，他和 $j$ 的身份一定不同
如果 $i$ 说 $j$ 是好人，那么无论 $i$ 是好人还是坏人，他和 $j$ 的身份一定相同

我们可以根据上面的观察建图

如果 $i$ 说 $j$ 是坏人，那么 $i,\ j$ 直接连边
否则设置一个中间点 $y$ ，将 $i$ 和 $y$ 以及 $y$ 和 $j$ 连接起来

由此我们可以得到一张含有多个强连通分量的图，我们对图上每一个强连通分量做二分图判定即可

二分图判定可以在 dfs 的过程用黑白染色算法来做

对于每一个强连通分量，如果二分图判定失败，那么意味着整体矛盾，答案输出 $-1$

否则我们将每一个二分图中较多的那一块置为好人，求和即可，时间复杂度 $\mathcal{O}(n + m)$

// cpp11
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 7;
const int M = 5e5 + 7;
int t, n, m, flag, fake;
vector<int> c(2), color(N + M);
unordered_map<int, vector<int>> g;

void dfs(int u) {
    c[color[u]] += (u <= n);
    for (auto &i: g[u]) {
        if (color[i] == -1) {
            color[i] = color[u] ^ 1, dfs(i);
        }
        else if (color[i] == color[u]) {
            flag = 1;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin >> t;
    while (t--) {
        cin >> n >> m;
        g.clear();
        for (int i = 0; i <= n + m; ++i) color[i] = -1;
        flag = 0, fake = n + 1;
        for (int i = 1; i <= m; ++i) {
            int a, b;
            string type;
            cin >> a >> b >> type;
            if (type == "imposter") {
                g[a].push_back(b);
                g[b].push_back(a);
            } else {
                g[a].push_back(fake);
                g[fake].push_back(a);
                g[b].push_back(fake);
                g[fake].push_back(b);
                fake++;
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            if (color[i] == -1) {
                color[i] = 0;
                c[0] = 0, c[1] = 0;
                dfs(i);
                ans += max(c[0], c[1]);
            }
        }
        if (flag) ans = -1;
        cout << ans << endl;
    }
}