从二进制枚举 follow up 到二分图判定，有点意思
这次周赛前三题比较水，第四题看到数据范围想到二进制枚举之后也不难做
不过我在评论区看到有人提到了 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;
}
}
腾讯云开发者
