AtCoder Beginner Contest 350

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

A - Past ABCs (abc350 A)

题目大意

给定一个形如 ABCXXX的字符串。

XXX是否是\(001 \to 349\)之间,且不能是 \(316\)

解题思路

将后三位转换成数字后判断即可。

神奇的代码
a = int(input().strip()[3:])
if a >= 1 and a <= 349 and a != 316:
    print("Yes")
else:
    print("No")


B - Dentist Aoki (abc350 B)

题目大意

给定\(n\)\(01\)序列。

进行\(q\)次操作,每次操作反转某一位上的 \(01\)

问最后 \(1\)的个数。

解题思路

反转操作的复杂度是\(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<int> a(n, 1);
    while (q--) {
        int x;
        cin >> x;
        --x;
        a[x] ^= 1;
    }
    int ans = accumulate(a.begin(), a.end(), 0);
    cout << ans << '\n';

    return 0;
}



C - Sort (abc350 C)

题目大意

给定一个\(1 \to n\)的排序,通过最多\(n-1\)次操作以下操作将其变得有序。

操作为,交换任意两个数。

输出任意可行的操作次数及其对应的操作步骤。

解题思路

\(i = 1 \to n\),依次考虑将 \(i\)交换到第 \(i\)位。经过 \(n-1\)次操作后则必定有序。

因此需要记录 \(pos[i]\)表示数字 \(i\)所在的位置,每次交换第\(i, pos[i]\) 位,就将\(i\)交换到第 \(i\)位,重复执行\(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;
    cin >> n;
    vector<int> pos(n);
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        --x;
        pos[x] = i;
        a[i] = x;
    }
    vector<array<int, 2>> ans;
    for (int i = 0; i < n; i++) {
        if (a[i] == i)
            continue;
        ans.push_back({i, pos[i]});
        swap(a[i], a[pos[i]]);
        swap(pos[a[i]], pos[a[pos[i]]]);
    }
    cout << ans.size() << '\n';
    for (auto& p : ans) {
        cout << p[0] + 1 << ' ' << p[1] + 1 << '\n';
    }

    return 0;
}



D - New Friends (abc350 D)

题目大意

给定一张无向图,若三点\(x,y,z\),存在:

  • \(x,y\)有连边
  • \(y,z\)有连边
  • \(x,z\)无连边

则连边\(x,z\)

问最多能连多少次边。

解题思路

考虑最简单的一条链的情况\(1 \to 2 \to 3 \to 4\),容易发现可以连的边有

  • \(1 \to 2, 2 \to 3\) => \(1 \to 3\)
  • \(1 \to 3, 3 \to 4\) => \(1 \to 4\)
  • \(2 \to 3, 3 \to 4\) => \(2 \to 4\)

观察\(1\)的新增边的情况,会发现它可以和所有能到达的点连边,即最终情况下,一个连通块内的任意两点都会连边,即变成一张完全图。

因此\(BFS\)得到每个连通块的点数 \(cp\)和边数 \(ce\),最终情况下该连通块会有 \(\frac{cp * (cp - 1)}{2}\) 条边,而已经有\(ce\)条(无向)边,因此可以连 \(\frac{cp * (cp - 1)}{2} - ce\)条边。

所有连通块的连边次数相加即为答案。

神奇的代码
#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<vector<int>> edge(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    LL ans = 0;
    vector<int> vis(n, 0);
    for (int i = 0; i < n; ++i) {
        if (vis[i])
            continue;

        queue<int> team;
        team.push(i);
        vis[i] = 1;
        int cp = 1, ce = 0;
        while (!team.empty()) {
            int u = team.front();
            team.pop();
            for (auto v : edge[u]) {
                ++ce;
                if (vis[v])
                    continue;
                vis[v] = 1;
                team.push(v);
                cp++;
            }
        }

        ans += 1ll * cp * (cp - 1) - ce;
    }
    ans /= 2;
    cout << ans << '\n';

    return 0;
}



E - Toward 0 (abc350 E)

题目大意

给定一个数字\(n\)\(x,y,a\)。通过两类操作,使得\(n\)变为 \(0\)

  • 操作一,花费代价\(x\),使得 \(n = \lfloor \frac{n}{a} \rfloor\)
  • 操作二,花费代价\(y\),掷骰子,等概率掷出\(1 \to 6\)中的一个\(b\),使得 \(n = \lfloor \frac{n}{b} \rfloor\)

问最优情况下,最小期望花费。

解题思路

期望题,根据定义,当前的期望值是所有后继情况的期望值的概率加权。

\(dp[i]\)表示当前数字为 \(x\),将其变为 \(0\)的最小期望花费。

边界条件很明显就是 \(dp[0] = 0\)

虽然是期望,但它问的是最优情况下的最小花费,那就是一个决策最优问题,考虑我的决策是什么。

很显然,决策就是操作一还是操作二,如果我决定执行操作一,会有一个期望值,执行操作二,会有另一个期望值,这两个期望值取最小,就是我做出的最优决策。因此需要分别求出操作一和操作二的期望花费。

根据定义,当前的期望值是所有后继情况的期望值的概率加权。

当我执行操作一后,后继情况只有一个,那就是\(dp[ \lfloor \frac{n}{a} \rfloor ]\),达到这个情况的概率是 \(1\)。因此操作一的期望花费\(cost1 = dp[ \lfloor \frac{n}{a} \rfloor ] + x\)

当我执行操作二后,后继情况有\(6\)个:

  • \(dp[ \lfloor \frac{n}{1} \rfloor ]\)
  • \(dp[ \lfloor \frac{n}{2} \rfloor ]\)
  • \(dp[ \lfloor \frac{n}{3} \rfloor ]\)
  • \(dp[ \lfloor \frac{n}{4} \rfloor ]\)
  • \(dp[ \lfloor \frac{n}{5} \rfloor ]\)
  • \(dp[ \lfloor \frac{n}{6} \rfloor ]\)

到达每一个后继情况的概率都是\(\frac{1}{6}\)

根据期望定义,可以得到操作二的期望花费 \(dp[n] = \frac{\sum_{i=1}^{6} dp[ \lfloor \frac{n}{i} \rfloor ]}{6} + y\)

但注意到\(i=1\)那一项是 \(dp[n]\),与左式是一样的,这会造成循环求值,这里我们将右边的 \(dp[n]\) 移到左边,合并同类项,就可以得到真正的\(cost2 = \frac{\sum_{i=2}^{6} dp[ \lfloor \frac{n}{i} \rfloor ]}{5} + \frac{6}{5}y\)

得到两个操作的期望花费\(cost1,cost2\)后,接下来就是做决策——取花费最小的,作为 \(dp[n]\)的值。这样是转移了。

虽然 \(n\)\(O(10^{18})\),但由于每次都至少\(/2\),最多除以 \(\log\)次就变成 \(0\),总的状态数其实很少,只有\(O(\log_2 * \log_3 * \log_4 * \log_5 * \log_6)\),大概就\(4e7\)的数量级。

从上面的分析可以看出,期望\(dp\)\(dp\)之间的区别仅仅是计算转移代价时需要用到期望定义来算,最终还是根据不同操作之间的代价取最优,还是个决策问题。

神奇的代码
#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);
    LL n;
    int a, x, y;
    cin >> n >> a >> x >> y;
    map<LL, double> dp;
    auto dfs = [&](auto dfs, LL u) -> double {
        if (u == 0)
            return 0.;
        if (dp.find(u) != dp.end())
            return dp[u];
        double cost1 = dfs(dfs, u / a) + x;
        double cost2 = 0;
        for (int i = 2; i <= 6; i++) {
            cost2 += dfs(dfs, u / i);
        }
        cost2 = cost2 / 5 + y * 6. / 5;
        return dp[u] = min(cost1, cost2);
    };
    dfs(dfs, n);
    cout << fixed << setprecision(10) << dp[n] << '\n';

    return 0;
}



F - Transpose (abc350 F)

题目大意

给定一个括号序列\(s\),长度为\(n\),其中也包括大小写字母。

依次处理每个匹配的括号里的字符,将其左右颠倒,并将大小写字母变换。

问最终的字符串。

解题思路

考虑朴素的做法,进行括号匹配,然后处理括号内的字符串,容易发现最坏情况下复杂度是\(O(n^2)\),比如((((((((((asjigjiogjwifjwefckfj))))))))))

注意到同一个字符块执行两次上述变换后相当于没变换,从上述的最坏情况下可以启示我们,我们不需要实际进行变换,仅仅将这一块字符串看作整体,然后打个标记。就跟线段树的懒标记差不多。

比如(((as)(sf))(ef)),我们先将每一块字符串看作整体,从 \(0\)开始标号,则变为(((0)(1))(2)),然后处理每对匹配的括号,比如变成了((34)(2)),然后处理 (34),这里我们就不给34重复打标记,因为那样的复杂度可能会变回原来的\(O(n^2)\),而是将 \(34\)看成一个整体 \(5\),在\(5\)上打标记,最后输出时再传递给 \(34\)。变成 (5(2)),然后是(56),然后是7

就跟线段树的思想一样,我们会发现\(34 \to 5, 2 \to 6, 56 \to 7\),它们的关系形成了一棵树的关系(但可能不是二叉树),然后打标记都是在父亲节点打标记,最后输出时,从根节点开始遍历,不断下放标记,下放到叶子时,再根据标记决定是否倒序输出即可。

神奇的代码
#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;
    s = "(" + s + ")";
    vector<string> info;
    info.push_back("(");
    info.push_back(")");
    string t;
    vector<int> tr;

    for (auto& i : s) {
        if (i == '(' || i == ')') {
            if (!t.empty()) {
                tr.push_back(info.size());
                info.push_back(t);
            }
            t.clear();
            if (i == '(')
                tr.push_back(0);
            else
                tr.push_back(1);
        } else
            t += i;
    }

    vector<vector<int>> edge(info.size());
    stack<int> st;
    for (auto i : tr) {
        if (i == 0) { // (
            st.push(0);
        } else if (i == 1) { // )
            int fa = info.size();
            info.push_back("");
            edge.push_back(vector<int>());
            while (!st.empty() && st.top() != 0) {
                edge[fa].push_back(st.top());
                st.pop();
            }
            st.pop();
            st.push(fa);
        } else {
            st.push(i);
        }
    }
    auto inverse = [](string& s) {
        reverse(s.begin(), s.end());
        for (auto& i : s) {
            if (islower(i))
                i = toupper(i);
            else
                i = tolower(i);
        }
    };
    auto dfs = [&](auto dfs, int u, int d) -> void {
        if (edge[u].empty()) { // leaf
            if (d)
                inverse(info[u]);
            cout << info[u];
            return;
        }
        if (d)
            reverse(edge[u].begin(), edge[u].end());
        for (auto v : edge[u]) {
            dfs(dfs, v, d ^ 1);
        }
    };
    dfs(dfs, info.size() - 1, 1);

    return 0;
}



G - Mediator (abc350 G)

题目大意

给定\(n\)个点,执行下列 \(q\)次操作,分两种,强制在线。

  • 1 u v,连无向边\(u \to v\),连边之前保证\(u,v\)不连通。
  • 2 u v,询问是否有一个点\(x\),使得\(u \to x \to v\)

解题思路

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

神奇的代码


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

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

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

相关文章

  • AtCoder Beginner Contest 310

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

    2024年02月16日
    浏览(27)
  • AtCoder Beginner Contest 325

    感觉错失了上分机会 给定姓和名,输出尊称,即姓+ san 。 按照题意模拟即可。 神奇的代码 给定 (n) 个地区的公司人数和对应的时区,规定上班时间为 (9:00-18:00) ,现召开一小时会议,上班期间的公司可以参加。问订个时间,能参与的人数的最大值。 枚举开会的时间,然后

    2024年02月08日
    浏览(32)
  • 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日
    浏览(45)
  • AtCoder Beginner Contest 331

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

    2024年02月05日
    浏览(35)
  • AtCoder Beginner Contest 301

    给定一个字符串表示高桥和青木每局的获胜情况。 如果高桥获胜局数多,或者两个胜局相等,但高桥率先取得那么多胜场,则高桥获胜,否则青木获胜。 问谁获胜。 按照题意,统计两者的获胜局数比较即可。 如果两者局数相等,可以看最后一局谁胜,青木胜则意味着高桥率

    2024年02月04日
    浏览(52)
  • AtCoder Beginner Contest 332

    坐地铁时口糊了6题,回来写时结果爆 long long , 0 没有逆元,卡了好久 线上购物,买了 (n) 种物品,分别给出它们的单价和数量。 若总价少于 (s) 元,则需要支付 (k) 元邮费,否则包邮。 问总价多少。 求个和判断下是否加邮费即可。 神奇的代码 一个容量为 (G) 的玻璃杯

    2024年02月04日
    浏览(39)
  • AtCoder Beginner Contest 341

    给定 (n) ,输出 (n) 个 (0) 和 (n+1) 个 (1) 交替的字符串。 (101010...) 循环输出即可。 神奇的代码 货币兑换。 (A) 国货币每 (x_a) 钱可兑换 (B) 国货币 (y_a) 钱。 (B) 国货币每 (x_b) 钱可兑换 (C) 国货币 (y_b) 钱。 ... 给定你拥有的每国货币钱数和兑换规则,依次兑换

    2024年02月19日
    浏览(26)
  • AtCoder Beginner Contest 318

    咕咕咕,总力战还没打,凹不过卷狗,躺了.jpg 给定 (n, m, p) ,问有多少个 (i) 满足 (0 m+pi leq n) 减去初始的 (m) ,剩下的就是看 (p) 的倍数个数。 神奇的代码 一个二维空间,有 (n) 个矩形覆盖。 问有多大的空间被覆盖了。重复覆盖算一次。 空间大小只有 (100) ,矩形

    2024年02月10日
    浏览(39)
  • AtCoder Beginner Contest 337

    给定 (n) 场比赛高桥和青木的得分。 问最后是总分,是高桥高还是青木高,还是打平了。 累计比较大小即可。 神奇的代码 给定一个字符串,问是否形如 AAAA..BBBB...CCCC 。 如果形如上述,那么通过 unique 函数去重后就是有序的,因此去重排序比较即可。 当然也可以朴素找出

    2024年01月21日
    浏览(34)
  • AtCoder Beginner Contest 324

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

    2024年02月08日
    浏览(34)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包