4944. 热身计算 - AcWing题库
给定两个正整数 $ a,b $，请你分别计算 $ \min(a,b) $ 以及 $ \lfloor \frac{|a-b|}{2} \rfloor $ 的值。
$ \lfloor \frac{|a-b|}{2} \rfloor $ 表示不大于 $ \frac{|a-b|}{2} $ 的最大整数。
输入格式
共一行，包含两个正整数 $ a,b $。
输出格式
共一行，输出两个整数，分别表示 $ \min(a,b) $ 以及 $ \lfloor \frac{|a-b|}{2} \rfloor $。
数据范围
所有测试点满足 $ 1 \le a,b \le 100 $。
输入样例1：
3 1
输出样例1：
1 1
输入样例2：
2 3
输出样例2：
2 0
输入样例3：
7 3
输出样例3：
3 2
没啥好说的，签到题
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
int a, b;
cin >> a >> b;
cout << min(a, b) << " " << (abs(a - b) / 2) << endl;
return 0;
}
4945. 比大小 - AcWing题库
给定一个 $ n $ 位 $ b_x $ 进制数 $ X $ 和一个 $ m $ 位 $ b_y $ 进制数 $ Y $。
$ X $ 和 $ Y $ 都为正整数，且都不含前导 $ 0 $。
请你比较它们的大小。
输入格式
第一行包含两个整数 $ n,b_x $。
第二行包含 $ n $ 个整数 $ x_1,x_2,…,x_n $，表示 $ X $ 的各位数字，它们按照从最高有效位到最低有效位的顺序给出。
第三行包含两个整数 $ m,b_y $。
第四行包含 $ m $ 个整数 $ y_1,y_2,…,y_m $，表示 $ Y $ 的各位数字，它们按照从最高有效位到最低有效位的顺序给出。
$ X $ 和 $ Y $ 的各位数字在输入中均按十进制表示给出。
输出格式
共一行：
- 如果 $ X < Y $，则输出
<。 - 如果 $ X > Y $，则输出
>。 - 如果 $ X = Y $，则输出
=。
数据范围
前 $ 6 $ 个测试点满足 $ 2 \le b_x,b_y \le 16 $。
所有测试点满足 $ 1 \le n,m \le 10 \(，\) 2 \le b_x,b_y \le 40 \(，\) b_x \neq b_y \(，\) 0 \le x_i < b_x \(，\) 0 \le y_i < b_y $。
输入样例1：
6 2
1 0 1 1 1 1
2 10
4 7
输出样例1：
=
输入样例2：
3 3
1 0 2
2 5
2 4
输出样例2：
<
输入样例3：
7 16
15 15 4 0 0 7 10
7 9
4 8 0 3 1 5 0
输出样例3：
>
下午刚复习了a进制转化为b进制的题目哈哈哈，正好直接用，不过说实话，写高精度确实代码量多一些。
#include<bits/stdc++.h>
using namespace std;
int n,a,m,b;
vector<int> number;
vector<int> number2;
vector<int> get(vector<int>number,int a)
{
vector<int> res;
while(number.size())
{
int r = 0;
for(int i = number.size() - 1; i >= 0; i--)
{
number[i] += r * a;
r = number[i] % 10;
number[i]/=10;
}
res.push_back(r);
while(number.size() && number.back() == 0 )number.pop_back();
}
reverse(res.begin(),res.end());
return res;
}
int main()
{
cin>>n>>a;
for (int i=0;i<n;i++)
{
int x;
cin>>x;
number.push_back(x);
}
cin>>m>>b;
for (int i=0;i<m;i++)
{
int x;
cin>>x;
number2.push_back(x);
}
reverse(number.begin(),number.end());
reverse(number2.begin(),number2.end());
vector<int>res = get(number,a);
vector<int>ans = get(number2,b);
if (res.size() > ans.size()) {
puts(">");
} else if (res.size() < ans.size()) {
puts("<");
} else {
for (int i = 0; i < res.size(); i++) {
if (res[i] > ans[i]) {
puts(">");
return 0;
} else if (res[i] < ans[i]) {
puts("<");
return 0;
}
}
puts("=");
}
return 0;
}
4946. 叶子节点 - AcWing题库
给定一棵 $ n $ 个节点的树，节点编号 $ 1 \sim n $。
$ 1 $ 号节点为树的根节点。
每个节点要么是黑色的，要么是白色的。
对于一个叶子节点，如果从该节点到根节点的路径（包括两端节点）中有超过 $ m $ 个黑色节点连续的排列在一起，则称该节点为无效叶子节点。
有效叶子节点数量 = 总叶子节点数量 - 无效叶子节点数量
请你统计，给定树中有效叶子节点的数量。
输入格式
第一行包含两个整数 $ n,m $。
第二行包含 $ n $ 个整数 $ a_1,a_2,…,a_n $，其中 $ a_i $ 表示第 $ i $ 个节点的颜色，$ 1 $ 表示黑色，$ 0 $ 表示白色。
接下来 $ n-1 $ 行，每行包含两个整数 $ x,y $，表示节点 $ x $ 和节点 $ y $ 之间存在一条无向边。
保证输入给定的是一棵树。
输出格式
一个整数，表示给定树中有效叶子节点的数量。
数据范围
前 $ 6 $ 个测试点满足 $ 2 \le n \le 10 $。
所有测试点满足 $ 2 \le n \le 10^5 \(，\) 1 \le m \le n \(，\) 0 \le a_i \le 1 \(，\) 1 \le x,y \le n \(，\) x \neq y $。
输入样例1：
4 1
1 1 0 0
1 2
1 3
1 4
输出样例1：
2
输入样例2：
7 1
1 0 1 1 0 0 0
1 2
1 3
2 4
2 5
3 6
3 7
输出样例2：
2
确实是一道基础的树的遍历问题，但考试时没维护好连续黑色点的数量这个关键性质，地柜还是掌握的不行。
/*
cnt：存储从这个节点开始往上数，连续黑色节点的个数
valid：是否已经存在了连续黑色节点的情况
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010, M = N * 2;
int n, m;
int h[N], w[N], e[M], ne[M], idx;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
int dfs(int u, int fa, int cnt, bool valid)
{
if (w[u]) cnt ++ ;
else cnt = 0;
if (cnt > m) valid = false;
//变量 sons 记录有多少个儿子，如果没有儿子，那么这个就是叶子结点
int res = 0, sons = 0;
//变量 res 表示以u节点为根的子树中有效的叶子节点数量，先把它赋值为0，然后不断用后续的代码来累加
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (j == fa) continue;
sons ++ ;
res += dfs(j, u, cnt, valid);
}
if (!sons && valid) res ++ ;
return res;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
memset(h, -1, sizeof h);
for (int i = 0; i < n - 1; i ++ )
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b), add(b, a);
}
//表示从节点u开始，fa表示u的父亲节点，cnt表示从根节点到u节点中的黑色节点数量，valid表示从根节点到u节点的路径中有无黑色节点数量超过m个的情况，函数返回值表示u节点及其子节点中有效叶子节点的数量。
printf("%d\n", dfs(1, -1, 0, true));
return 0;
}
总结
本次周赛难度不大，最后一题递归和树的遍历的相关知识没掌握好，这就去恶补！