C++ 算法竞赛、05 周赛篇 | AcWing 第85场周赛
AcWing 第85场周赛
4791 死或生
简单题
#include <bits/stdc++.h>
using namespace std;
int a[3][2];
int n;
int main() {
cin >> n;
while (n--) {
int t, x, y;
cin >> t >> x >> y;
a[t][0] += x;
a[t][1] += y;
}
if (a[1][0] < a[1][1])
puts("DEAD");
else
puts("LIVE");
if (a[2][0] < a[2][1])
puts("DEAD");
else
puts("LIVE");
return 0;
}
4792 最大价值
贪心,先找到最大价值的字母,往最后面插最大的
#include <bits/stdc++.h>
using namespace std;
int const N = 30;
int price[N];
int main() {
string str;
int k;
cin >> str >> k;
int m = -0x3f3f3f3f;
for (int i = 0; i < 26; i++) {
cin >> price[i];
m = max(m, price[i]);
}
long long res = 0;
for (int i = 0; i < str.size(); i++) {
res += price[str[i] - 'a'] * (i + 1);
}
for (int i = 1; i <= k; i++) {
res += m * (i + str.size());
}
cout << res;
return 0;
}
4793 危险程度
把图分成若干个连通块,每个连通块假设有 k 个点,最多会反应 k - 1 次
因此题目转变为求连通块数量,假设为 t,答案就是 \(2^{n-t}\)
为求 t,从 n 开始,每合并一点就减一,剩余的数量就是连通块的数量(想象多个连通块,各个连通块只有根节点没有被合并)
#include <bits/stdc++.h>
using namespace std;
int const N = 5e2 + 10;
int p[N];
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int n, m;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) p[i] = i;
int cnt = n;
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
a = find(a), b = find(b);
if (a != b) {
p[a] = b;
cnt--;
}
}
cout << (1ll << n - cnt);
return 0;
}
下面是算每个连通块元素个数的解法
#include <bits/stdc++.h>
using namespace std;
int const N = 5e2 + 10;
int p[N], nums[N];
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int n, m;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
p[i] = i;
nums[i] = 1;
}
long long res = 1;
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
a = find(a), b = find(b);
if (a != b) {
p[a] = b;
nums[b] += nums[a];
nums[a] = 0;
}
}
for (int i = 1; i <= n; i++)
if (nums[i] > 1) res = res << nums[i] - 1;
cout << res;
return 0;
}