AtCoder Beginner Contest 329

这篇具有很好参考价值的文章主要介绍了AtCoder Beginner Contest 329。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

劳累一天不该写题,启发式合并都写错了

A - Spread (abc329 A)

题目大意

给定一个字符串,将每个字符输出出来,中间留个空格。

解题思路

遍历输出即可。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s;
    cin >> s;
    for (auto& i : s)
        cout << i << ' ';
    cout << '\n';

    return 0;
}



B - Next (abc329 B)

题目大意

给定一个数组,找出次大的数。

解题思路

遍历一下,从非最大的数求一个最大值即可。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& i : a)
        cin >> i;
    cout << *next(set<int>(a.begin(), a.end()).rbegin()) << '\n';

    return 0;
}



C - Count xxx (abc329 C)

题目大意

给定一个字符串,问有多少个连续的子串,其由一个字母组成。

解题思路

对于一个字母c,如果它连续出现了\(x\)个,那么就有 \(x\)个不同长度的由 c组成的字符串。它对答案的贡献就是\(x\)

一共有 \(26\)个字母,对这些字母的贡献累计求和即可。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    string s;
    cin >> s;
    array<int, 26> cnt{};
    char la = 0;
    int num = 0;
    for (auto& i : s) {
        if (i == la) {
            ++num;
        } else {
            cnt[la - 'a'] = max(cnt[la - 'a'], num);
            la = i;
            num = 1;
        }
    }
    if (la) {
        cnt[la - 'a'] = max(cnt[la - 'a'], num);
    }
    cout << accumulate(cnt.begin(), cnt.end(), 0) << '\n';

    return 0;
}



D - Election Quick Report (abc329 D)

题目大意

给定\(n\)个人和 \(m\)个选票。

每个选票投给某个人。

对于 \(i \in [1,m]\),统计前\(i\)张选票,问票数最多的人的标号。同号数求最小。

解题思路

我们需要一个数据结构,它可以根据每个人的票数,动态对这\(n\)个人排序。需要动态更新票数+求最大值。刚好set都可以以log的复杂度内完成这些操作。

set的元素是{票数,标号}这个二元组,这样就可以排序+得到对应的标号。更新一个元素的话,就先删除原来的,把更新后的插入即可。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<int> cnt(n);
    set<pair<int, int>> candi;
    auto remove = [&](int id) { candi.erase({-cnt[id], id}); };
    auto insert = [&](int id) { candi.insert({-cnt[id], id}); };
    for (int i = 0; i < n; ++i)
        insert(i);
    while (m--) {
        int x;
        cin >> x;
        --x;
        remove(x);
        cnt[x]++;
        insert(x);
        cout << candi.begin()->second + 1 << '\n';
    }

    return 0;
}



E - Stamp (abc329 E)

题目大意

给定一个长度为\(n\)的目标串\(s\)和一个长度为\(m\)的盖章串 \(t\)

给定一个长度为\(n\)#串,拿\(t\)去盖章,问能否盖出 \(s\)

解题思路

考虑盖章的性质,每次覆盖都是连续串被覆盖,因此可以认为串\(s\)是由若干个串\(t\)的子串构成的。比如样例一的 ABC B ABC,都是ABC的子串。

但是还有一些要求,考虑两次盖章\(a,b\),它们相互覆盖,由于盖章有先后顺序,因此要么\(a\)的后缀被覆盖了(此时\(b\)是前缀),要么 \(b\)的前缀被覆盖了(此时\(a\)是后缀) ,因此相邻子串,要么前者\(a\)\(t\)的后缀,要么后者\(b\)\(t\)的前缀。比如样例二的AB BC ABC是不可行的,因为子串 ABBC不满足上述的要求,ABCABC相互覆盖,要么前者后覆盖,是ABC C,要么后者后覆盖,是A ABC,始终做不到ABBC

由此设\(dp[i][0/1]\)表示覆盖\(s\)的前 \(i\)个字符,且最后一次覆盖 不是/是 \(t\)的后缀 ,这情况是否存在。初始条件就是\(dp[0][0] = 1\)

转移就枚举\(t\)的子串,如果是 \(t\)的前缀则直接从\(dp[][0/1]\)转移 ,不是前缀则从\(dp[][1]\)转移。

最后答案就是 \(dp[n][1]\)

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    string s, t;
    cin >> n >> m >> s >> t;
    vector<array<int, 2>> dp(n + 1, array<int, 2>{});
    dp[0][0] = 1;
    auto ok = [&](int l, int r, int L, int R) {
        return s.substr(l, r - l + 1) == t.substr(L, R - L + 1);
    };
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < m; ++j) {
            for (int k = j; k < m; ++k) {
                int len = k - j + 1;
                if (len > i)
                    break;
                if (!ok(i - len, i - 1, j, k))
                    continue;
                if (j == 0)
                    dp[i][k == m - 1] |= dp[i - len][0];
                dp[i][k == m - 1] |= dp[i - len][1];
            }
        }
    }
    if (dp[n][1])
        cout << "Yes" << '\n';
    else
        cout << "No" << '\n';

    return 0;
}



反过来思考,从串\(s\)开始考虑最后一次覆盖,它一定是一个完整的\(t\)串。

我们从中找到一个完整的 \(t\)串,将其撤销,那么这些位置的字母就变成 #,相当于通配符,它可以匹配任何字母。为什么可以这样做呢?因为这个位置的字符会被最后的操作覆盖,因此原先是什么字母都无所谓,不会影响最后的结果,所以可以认为是通配符。

然后重复找到可以匹配串\(t\)的子串(其长度显然是\(m\)), 将其改成#。如果最后串\(s\)所有字符都是 #,那么是可行的。

如此暴力找的复杂度是\(O(n^2m)\) 。考虑到如果一个子串被改成了#,那么可能能匹配\(t\)的串只有附近的 \(O(2m)\)个,因此我们只需检索周围的这 \(O(2m)\)个能否匹配,可以匹配则依次类推,就像 BFS一样扩展判断。每个\(m\)长度的子串的判断次数只有 \(m\)次,每次判断的复杂度是\(O(m)\),因此总的复杂度是 \(O(nm^2)\)

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    string s, t;
    cin >> n >> m >> s >> t;
    vector<int> used(n);
    auto ok = [&](int l) {
        if (used[l])
            return false;
        for (int i = l; i < l + m; ++i) {
            if (i >= n)
                return false;
            if (s[i] == '#')
                continue;
            if (s[i] != t[i - l])
                return false;
        }
        return true;
    };
    queue<int> team;
    for (int i = 0; i < n; ++i)
        if (ok(i))
            team.push(i);
    while (!team.empty()) {
        int u = team.front();
        team.pop();
        for (int i = u; i < u + m; ++i)
            s[i] = '#';
        used[u] = 1;
        for (int i = max(u - m + 1, 0); i < min(u + m, n); ++i)
            if (ok(i))
                team.push(i);
    }
    if (ranges::count(s, '#') == n)
        cout << "Yes" << '\n';
    else
        cout << "No" << '\n';

    return 0;
}



F - Colored Ball (abc329 F)

题目大意

\(n\)个箱子,第\(i\)个箱子有一个 \(c_i\)颜色的球。

执行以下\(q\)次操作。

每个操作给定 \(a, b\),将第 \(a\)个箱子里的所有球放入第 \(b\)个箱子里,并输出第 \(b\)个箱子里的颜色数量。

解题思路

直接执行操作的复杂度是\(O(nq)\)。显然通过不了。

注意操作是一个合并,单纯的只有合并没有分裂的话,可以采用启发式合并,即合并的时候,始终保持数量小的合并到数量大的

由于要输出颜色数量,因此可以用setunordered_set来维护一个箱子的球颜色。合并的时候将size小的set的元素插入到size大的set,由于可能会\(b \to a\),在此情况下 swap两个set即可。

注意setswap\(O(1)\)的。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, q;
    cin >> n >> q;
    vector<set<int>> cnt(n);
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        cnt[i].insert(x);
    }
    while (q--) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        bool swapp = false;
        if (cnt[a].size() > cnt[b].size()) {
            swapp = true;
            swap(a, b);
        }
        cnt[b].insert(cnt[a].begin(), cnt[a].end());
        cout << cnt[b].size() << '\n';
        cnt[a].clear();
        if (swapp)
            cnt[a].swap(cnt[b]);
    }

    return 0;
}



G - Delivery on Tree (abc329 G)

题目大意

给定一棵二叉树,有\(m\)个球,初始在节点 \(s_i\),最终要去 \(t_i\)\(1\)号点有篮子,最多装\(k\)个球。

现在要移动篮子,装球,放球,不超过篮子容量,最终每个球都在对应的\(t_i\),要求每条边最多经过两次。

问移动方案数。

解题思路

<++>文章来源地址https://www.toymoban.com/news/detail-746900.html

神奇的代码



到了这里,关于AtCoder Beginner Contest 329的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • AtCoder Beginner Contest 324

    在高铁上加训! 给定 (n) 个数,问是否都相等。 判断是不是全部数属于第一个数即可。或者直接拿 set 去重。 神奇的代码 给定一个数 (N) ,问是否能表示成 (2^x3^y) 。 指数范围不会超过 (64) ,花 (O(64^2)) 枚举判断即可。 神奇的代码 给定一个字符串 (t) 和若干个字符串

    2024年02月08日
    浏览(33)
  • AtCoder Beginner Contest 310

    感觉F又双叒叕写复杂了 点杯咖啡,要 (p) 元,但可以用一个优惠券,使得咖啡只要 (q) 元,但你需要额外购买 (n) 个商品中(价格为 (a_i) )的一个。 问点杯咖啡的最小价格。 考虑直接买还是使用优惠券,使用优惠券的话就选 (n) 个商品中价格最小的。 两种情况取最小

    2024年02月16日
    浏览(26)
  • AtCoder Beginner Contest 311

    给定一个字符串,问最短的一个前缀,包含 A B C 这三个字符。 注意到这个前缀的末尾字母一定是这三个字母中的一个,因此答案就是这三个字母出现位置最早的最大值。 神奇的代码 给定 (n) 个人的 (d) 天的空闲与否的情况,问最长的连续天,这 (n) 个人都空闲。 我们找

    2024年02月16日
    浏览(37)
  • AtCoder Beginner Contest 331

    给定一年的月数和一月的天数,以及当天日期,问次日的日期。 一个简单的进制加法运算,超出进制数则向前加一。 神奇的代码 给定 (6,8,12) 根胡萝卜的价格。 问买至少 (n) 根胡萝卜的最小花费。 由于 (n) 只有 (100) ,花 (O(n^3)) 枚举这三类胡萝卜的购买次数,取花费最

    2024年02月05日
    浏览(32)
  • AtCoder Beginner Contest 349

    (n) 个人游戏,每局有一人 (+1) 分,有一人 (-1) 分。 给定最后前 (n-1) 个人的分数,问第 (n) 个人的分数。 零和游戏,所有人总分是 (0) ,因此最后一个人的分数就是前 (n-1) 个人的分数和的相反数。 神奇的代码 对于一个字符串,如果对于所有 (i geq 1) ,都有恰好

    2024年04月13日
    浏览(55)
  • AtCoder Beginner Contest 300

    给定一个元素互不相同的数组 (c) 和 (a,b) ,找到 (i) 使得 (c_i = a + b) 直接 for 循环寻找即可。 神奇的代码 给定两个矩阵 (A,B) ,问能否对 (A) 进行若干次变换操作得到 (B) 。 变换分两种,一种是将第一列放到最后一列,另一种是将第一行放到最后一行。 范围不大,直

    2024年02月01日
    浏览(48)
  • AtCoder Beginner Contest 320

    给定 (a,b) ,输出 (a^b + b^a) 。 因为数不超过 (10) ,可以直接用 pow 计算然后转成 (int) 。不会有精度损失。 神奇的代码 给定一个字符串 (s) ,求长度最长的回文串。 因为长度只有 (100) ,可以直接枚举子串,然后暴力判断是不是回文串(翻转后是否和自身相同),复杂

    2024年02月08日
    浏览(34)
  • AtCoder Beginner Contest 327

    2023.11.08 update: 更新了G 给定一个字符串 (s) ,问是否包含 ab 或 ba 。 遍历判断即可。 神奇的代码 给定 (b) ,问是否存在 (a) 使得 (a^a = b) 。 由于指数爆炸的缘故, (a) 的范围不会很大,枚举 (a) ,看 (b % a) 是否为 (0) ,然后用 (b) 不断除以 (a) ,看最后除的次数是

    2024年02月06日
    浏览(44)
  • AtCoder Beginner Contest 314

    怎么好多陌生单词 审核怎么这么逆天,半小时还没审完 给定 (pi) 的值以及数 (n) ,要求保留 (n) 位小数输出,不四舍五入。 字符串形式储存然后截取末尾即可。 神奇的代码 (n) 个人玩轮盘赌游戏,简单说就是一个转盘有 (37) 个数字以及一个箭头,箭头会等概率停在某

    2024年02月13日
    浏览(36)
  • AtCoder Beginner Contest 326

    100楼层,一次可以上最多两层,或下最多三层。 给定两楼层,问能否一次到达。 比较大小,然后判断其差是是不是在 (2) 或 (3) 内即可。 神奇的代码 给定一个 (n) ,问不小于 (n) 的形如 (326) 的数字是多少。 形如 (326) 的数字,即数位有 (3) ,且百位 (times) 十位

    2024年02月08日
    浏览(33)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包