C++ 算法竞赛、01 周赛篇 | AcWing 第1场周赛

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

AcWing 第1场周赛

竞赛 - AcWing

3577 选择数字

3577. 选择数字 - AcWing题库

朴素

暴力两层循环

#include <cstdio>
#include <iostream>
#include <unordered_set>

using namespace std;

const int N = 101;
int a[N], b[N];

int main() {
    int n, m;
    cin >> n;
    unordered_set<int> s;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        s.insert(a[i]);
    }
    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> b[i];
        s.insert(b[i]);
    }
    // ^ 两层遍历
    for (int i = 0; i < n; i++)
        for (int k = 0; k < m; k++) {
            if (!s.count(a[i] + b[k])) {
                cout << a[i] << " " << b[k] << endl;
                return 0;
            }
        }

    return 0;
}

优美

两个数组的最大值相加一定是新数

#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

const int N = 101;
int a[N], b[N];

int main() {
    int n, m, a_max = 0, b_max = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a_max = max(a[i], a_max);
    }
    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> b[i];
        b_max = max(b[i], b_max);
    }
    cout << a_max << " " << b_max;
    return 0;
}

3578 ⭐最大中位数

3578. 最大中位数 - AcWing题库

整数二分问题。求中位数,并依次递增,计算所需的操作次数。求最后一个操作次数总和 <= k 的中位数值

  • 如果 mid - a[i] < 0 ,意味着该数比中位数大,不需要操作
  • int 范围 2.174e9,二分过程中计算 (l+r) 可能超过 2.174e9,改用 long 存储
#include <algorithm>
#include <iostream>

using namespace std;

const int N = 2e5 + 10;
int a[N], n;
long k;

long check(long mid) {
    long res = 0;
    for (int i = n >> 1; i < n; i++) {
        res += (mid - a[i] > 0 ? mid - a[i] : 0);
    }
    return res;
}

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    sort(a, a + n);
    long l = a[n >> 1], r = 2e9;
    while (l < r) {
        long mid = l + r + 1 >> 1;
        if (check(mid) <= k)
            l = mid;
        else
            r = mid - 1;
    }
    cout << l;
    return 0;
}

2579 ⭐⭐数字移动

AcWing 3579. 数字移动 - AcWing

每个点的出度和入度都为 1,每组交换都会形成一个闭环。每个环的节点数就是每个元素回到原来位置需要经过的交换次数

采用并查集维护各个连通块(环)的连通性,然后在并查集的根节点额外维护该并查集的节点个数

难点文章来源地址https://www.toymoban.com/news/detail-695074.html

  • 合并两个根节点的时候,把其中一个根节点维护的并查集元素数量s[pu]累加到另一个并查集的根节点中
  • 最后输出包含 i 的连通块数量,也就是 s[find(i)]
#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;
const int N = 2e5 + 10;
int p[N], s[N];  // s 记录每个连通块的数量
int t, n;

int find(int u) {
    if (p[u] != u) p[u] = find(p[u]);
    return p[u];
}

int main() {
    cin.tie(0);
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            p[i] = i;
            s[i] = 1;
        }
        for (int u = 1; u <= n; u++) {
            int x;
            cin >> x;
            int px = find(x), pu = find(u); 
            if (px != pu) { // 使px跟pu在同一个连通块
                s[px] += s[pu];
                p[pu] = px;
            }
        }
        for (int i = 1; i <= n; i++) {
            cout << s[find(i)] << " ";
        }
        cout << endl;
    }

    return 0;
}

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

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

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

相关文章

  • 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)
  • C++ 算法竞赛、06 周赛篇 | AcWing 第97场周赛

    4944. 热身计算 - AcWing题库 4944. 热身计算 - AcWing题库 4945. 比大小 - AcWing题库 考查K进制转换十进制 4946. 叶子节点 - AcWing题库 无向边要开两倍点数的数组,见常量 M cnt 统计每个有效叶子节点的个数 st 记录遍历过的点,让每个点只遍历一次 dfs count 统计还有几条边没走,0 条则为

    2024年02月09日
    浏览(38)
  • 【蓝桥杯集训·周赛】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

领红包