AcWing 第97场周赛
4944. 热身计算 - AcWing题库
4944 热身计算
4944. 热身计算 - AcWing题库
#include <bits/stdc++.h>
using namespace std;
int a, b;
int main() {
cin >> a >> b;
cout << min(a, b);
cout << " " << abs(a - b) / 2;
return 0;
}
4945 比大小
4945. 比大小 - AcWing题库
考查K进制转换十进制
#include <bits/stdc++.h>
using namespace std;
int const N = 15;
int x, y, n, m;
int nums[N];
int main() {
long long res_a = 0, res_b = 0;
cin >> n >> x;
for (int i = 1; i <= n; i++) {
cin >> nums[i];
}
long long t = 1;
for (int i = n; i >= 1; i--) {
res_a += nums[i] * t;
t *= x;
}
cin >> m >> y;
for (int i = 1; i <= m; i++) {
cin >> nums[i];
}
t = 1;
for (int i = m; i >= 1; i--) {
res_b += nums[i] * t;
t *= y;
}
if (res_a > res_b)
puts(">");
else if (res_a < res_b)
puts("<");
else
puts("=");
return 0;
}
4946 叶子节点
4946. 叶子节点 - AcWing题库
- 无向边要开两倍点数的数组,见常量 M
- cnt 统计每个有效叶子节点的个数
- st 记录遍历过的点,让每个点只遍历一次
- dfs
- count 统计还有几条边没走,0 条则为叶子节点
- 遍历所有子节点,根据子节点颜色分两种情况
- 黑色:更新最大长度,连续长度+1
- 白色:不更新最大长度,连续长度置 0
#include <bits/stdc++.h>
using namespace std;
int const N = 1e5 + 10, M = 2e5 + 10;
int h[N], e[M], ne[M], idx;
int color[N];
int n, m;
void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; }
int cnt;
bool st[N];
void dfs(int u, int black_max, int black_now) {
st[u] = true;
int count = 0;
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (st[j]) continue;
count++;
if (color[j])
dfs(j, max(black_max, black_now + 1), black_now + 1);
else
dfs(j, black_max, 0);
}
if (!count)
if (black_max <= m) cnt++;
}
int main() {
cin >> n >> m;
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i++) cin >> color[i];
for (int i = 1; i <= n; i++) {
int x, y;
cin >> x >> y;
add(x, y);
add(y, x);
}
dfs(1, 0, color[1]);
cout << cnt;
return 0;
}
看不懂我的,也可以看这个题解文章来源:https://www.toymoban.com/news/detail-708478.html
- 用入度来找叶子节点(叶子节点的入度是 1)
- 每个节点都验证一遍连续长度是否满足情况,存储其状态
- 最后需要遍历一次所有节点统计满足条件的叶子节点数量
AcWing 4946. 叶子节点(树的遍历) - AcWing文章来源地址https://www.toymoban.com/news/detail-708478.html
到了这里,关于C++ 算法竞赛、06 周赛篇 | AcWing 第97场周赛的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!