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;
}

总结

本次周赛难度不大，最后一题递归和树的遍历的相关知识没掌握好，这就去恶补！