C++ 算法竞赛、06 周赛篇 | AcWing 第97场周赛

这篇具有很好参考价值的文章主要介绍了C++ 算法竞赛、06 周赛篇 | AcWing 第97场周赛。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

看不懂我的,也可以看这个题解

  • 用入度来找叶子节点(叶子节点的入度是 1)
  • 每个节点都验证一遍连续长度是否满足情况,存储其状态
    • 最后需要遍历一次所有节点统计满足条件的叶子节点数量

AcWing 4946. 叶子节点(树的遍历) - AcWing文章来源地址https://www.toymoban.com/news/detail-708478.html

到了这里,关于C++ 算法竞赛、06 周赛篇 | AcWing 第97场周赛的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C++ 算法竞赛、05 周赛篇 | AcWing 第85场周赛

    竞赛 - AcWing 4791. 死或生 - AcWing题库 简单题 4792. 最大价值 - AcWing题库 贪心,先找到最大价值的字母,往最后面插最大的 4793. 危险程度 - AcWing题库 把图分成若干个连通块,每个连通块假设有 k 个点,最多会反应 k - 1 次 因此题目转变为求连通块数量,假设为 t,答案就是 (2^

    2024年02月09日
    浏览(42)
  • C++ 算法竞赛、07 周赛篇 | AcWing 第120场周赛

    竞赛 - AcWing 5146. 最大GCD - AcWing题库 不难发现,最大公约数的条件是 (GCD(lfloor frac{n}{2} rfloor ,lfloor frac{n}{2} rfloor * 2)) 5147. 数量 - AcWing题库 不含 4 和 7 以外 (Rightarrow) 只含 4 和 7,每位只有两种情况,最多到 1e9,即 (2^9) 个情况,爆搜枚举即可 AcWing 5148. 字符串匹配 -

    2024年02月08日
    浏览(41)
  • C++ 算法竞赛、08 周赛篇 | AcWing 第94场周赛 ⭐

    4870. 装物品 - AcWing题库 4870. 装物品 - AcWing题库 巨简单题 4871. 最早时刻 - AcWing题库 考查堆优化版迪杰斯特拉变形 越早到达,越早离开 = 每个点维护一个最早到达时刻 如果 delay 小于 0,就不能用迪杰斯特拉算法 4872. 最短路之和 - AcWing题库 最终结果可能是 (500^2 * 10^5) 可能会

    2024年02月08日
    浏览(49)
  • 【蓝桥杯集训·周赛】AcWing 第94场周赛

    4870. 装物品 已知,每个背包最多可以装 5 件物品。 请你计算, 要装下 x 件物品最少需要多少个背包 。 输入格式 一个整数 x。 输出格式 一个整数,表示所需背包的最少数量。 数据范围 所有测试点满足 1≤x≤10 6 。 输入样例1 : 输出样例1 : 输入样例2 : 输出样例2 : 我的

    2023年04月08日
    浏览(41)
  • AcWing.第121场周赛

    以下是acwing第121场比赛的abc三题 竞赛 - AcWing 5149. 简单计算 - AcWing题库 直接模拟,用floor()函数来实现下取整 5150. 顶牛 - AcWing题库 如果没出现a[i][j] = 1 || a[i][j] =  3,那么代表i牛是满足题目条件的; 这样模拟即可! 5151. 程序调用 - AcWing题库 用hsah表实现模拟,否则会超时!!!

    2024年02月07日
    浏览(38)
  • 【算法】力扣第 284 场周赛(最短代码)

    看数据范围 1 = nums.length = 1000 ,直接暴力 2行 搞定 看数据范围 1 = n = 1000 ,每个工件最多只覆盖4个单元格,直接哈希+暴力, 2行搞定 这题比较吃细节,推荐大家看一下灵茶山艾府大佬的题解, 1行 就搞定了 三次dijkstra,可可也是看了题解之后才做出来, 15行 解法👇 T4罚坐一

    2024年02月13日
    浏览(47)
  • 第380场周赛挑战:二分,数位dp和KMP算法的综合运用

    比赛地址 卡在第三题了,应该看看第4题kmp套模版的 二分查找 : findMaximumNumber 函数使用二分查找法来查找符合条件的最大 num 。它初始化左边界 left 为 0,右边界 right 为 (k + 1) (x - 1) 。这个右边界是一个估计值,确保 num 的上界足够高。二分查找在满足条件 left + 1 right 的情况

    2024年02月02日
    浏览(56)
  • 软通杯算法竞赛--周赛题目(一)

    目录 一、S属性大爆发 二、日期杯 三、 三人行必由我师  四、集合之差 五、咱们计算机不懂烷烃 六、适度跑步健康长寿 测试用例 输出案例 输入案例: 输出案例: 输入案例: 输出案例: 输入案例:  输出案例: 测试案例: 输出案例: 输入输出案例:  

    2024年02月05日
    浏览(41)
  • 【力扣周赛】第 352 场周赛

    第 352 场周赛 2760. 最长奇偶子数组 提示: 1 = nums.length = 100 1 = nums[i] = 100 1 = threshold = 100 因为数据范围特别小,所以怎么暴力都是无所谓的。 继续优化 可以发现,每个满足条件的子数组是不会重叠的, 所以在枚举 l 的时候,每次可以将下一个 l 设置成 r。 代码如下: 2761. 和

    2024年02月12日
    浏览(35)
  • 【力扣周赛】第357场周赛

    题目描述 描述:你的笔记本键盘存在故障,每当你在上面输入字符 ‘i’ 时,它会反转你所写的字符串。而输入其他字符则可以正常工作。 给你一个下标从 0 开始的字符串 s ,请你用故障键盘依次输入每个字符。 返回最终笔记本屏幕上输出的字符串。 示例 1: 示例 2: 提示

    2024年02月13日
    浏览(34)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包