1. Toy模板网首页
  2. > Toy博客

AtCoder Beginner Contest 324

9月前 作者：~Lanly~ 分类：Toy博客 阅读(32) 违法举报

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

在高铁上加训！

A - Same (abc324 A)

题目大意

给定\(n\)个数，问是否都相等。

解题思路

判断是不是全部数属于第一个数即可。或者直接拿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;
    cin >> n;
    vector<int> a(n);
    for (auto& i : a)
        cin >> i;
    cout << (set<int>(a.begin(), a.end()).size() == 1 ? "Yes" : "No") << '\n';

    return 0;
}

B - 3-smooth Numbers (abc324 B)

题目大意

给定一个数\(N\)，问是否能表示成 \(2^x3^y\)。

解题思路

指数范围不会超过\(64\)，花 \(O(64^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);
    LL n;
    cin >> n;
    auto check = [&]() {
        for (int i = 0; i < 64; ++i) {
            LL x = (1ll << i);
            for (int j = 0; j < 64; ++j) {
                if (x > n)
                    break;
                if (x == n)
                    return true;
                x *= 3;
            }
        }
        return false;
    };
    if (check())
        cout << "Yes" << '\n';
    else
        cout << "No" << '\n';

    return 0;
}

C - Error Correction (abc324 C)

题目大意

给定一个字符串\(t\)和若干个字符串 \(s\)。问有哪些 \(s\)，满足以下四个条件中的一个：

  • \(s = t\)
  • \(s\)在某处增加一个字母得到 \(t\)
  • \(s\)在某处删除一个字母得到 \(t\)
  • \(s\)在某处修改一个字母得到 \(t\)

解题思路

第一个就判断是否逐位相等。

第二个和第三个其实是一样的，就是两者长度是否差\(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;
    string s;
    cin >> n >> s;
    vector<int> ans;
    auto check2 = [](const string& l, const string& r) {
        if (r.size() - l.size() != 1)
            return false;
        int x = 0, y = 0;
        while (x < l.size()) {
            while (y < r.size() && r[y] != l[x])
                ++y;
            if (y < r.size()) {
                ++x;
                ++y;
            } else
                break;
        }
        return x == l.size();
    };
    auto check = [&](const string& t) {
        if (s.size() == t.size()) {
            int cnt = 0;
            for (int i = 0; i < s.size(); ++i)
                cnt += (s[i] != t[i]);
            return cnt <= 1;
        }
        if (s.size() < t.size())
            return check2(s, t);
        else
            return check2(t, s);
    };
    for (int i = 1; i <= n; ++i) {
        string t;
        cin >> t;
        if (check(t))
            ans.push_back(i);
    }
    cout << ans.size() << '\n';
    for (auto& i : ans)
        cout << i << ' ';
    cout << '\n';

    return 0;
}

D - Square Permutation (abc324 D)

题目大意

给定一个数字串\(s\)，将每一个数位排序，问能排出多少种数，其为平方数。

解题思路

注意到串长度只有\(13\)，我们可以枚举每一个平方数\(x\)，只有 \(\sqrt{10^{13}\)个，然后判断数字串 \(s\)能否表示出这个数\(x\)即可。

因为数字串 \(s\)可以排列，因此问数字串能否表示出这个数 \(x\)，其实就是问这两个的每个数位数字的个数是否相等。

注意计算\(x\)的数位数字时要把前导零补上去。

神奇的代码
#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;
    string s;
    cin >> n >> s;
    vector<int> cnt(10, 0);
    for (auto& i : s)
        cnt[i - '0']++;
    LL ans = 0;
    int up = ceil(sqrt(9999999999999ll));
    auto solve = [&](LL x) {
        vector<int> num(10, 0);
        int sz = 0;
        while (x) {
            num[x % 10]++;
            x /= 10;
            ++sz;
        }
        if (sz > n)
            return 0;
        num[0] += (n - sz);
        return int(num == cnt);
    };
    for (int i = 0; i < up; ++i) {
        ans += solve(1ll * i * i);
    }
    cout << ans << '\n';

    return 0;
}

E - Joint Two Strings (abc324 E)

题目大意

给定\(n\)个字符串 \(s_i\)和一个字符串 \(t\)，长度为\(m\)，问有多少组 \((i, j)\)，使得拼接串 \(s_is_j\)包含 \(t\)这个子序列。

解题思路

我们先枚举\(s_i\)，贪心匹配这个子序列 \(t\)，它可能不能完全匹配上，但能匹配 \(t\)的前 \(x\)位。

那剩下的\(m-x\)位就交给 \(s_j\)匹配，如果 \(s_j\)能至少匹配 \(t\)的后面\(m-x\)位，则拼接串\(s_is_j\) 就包含\(t\)这个子序列。

因此对于字符串\(s_i\)，它能匹配串 \(t\)的前 \(x\)位，我们要找出串 \(s_j\)的数量，可以匹配串 \(t\)的至少后\(m-x\)位，这个数量就是当前串\(s_i\)的贡献。即 \((i,*)\)的数量。

而对于字符串\(s_j\)能匹配 \(t\)的后面多少位，其实把它们反串一下贪心匹配即可。

因此就预处理每个串能匹配串\(t\)的 前缀位数和后缀位数，然后枚举每个串的匹配的前缀位数，找到要完全匹配\(t\)需要的后缀位数，大于该位数的都可以作为\(j\)的候选，累计数量即可。因此把后缀位数的个数预处理一下即可。

神奇的代码
#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;
    string t;
    cin >> n >> t;
    int len = t.size() + 1;
    vector<int> cnt(len, 0), invcnt(len, 0);
    string invt = t;
    reverse(invt.begin(), invt.end());
    auto check = [](const string& s, const string& t, vector<int>& cnt) {
        int l = 0, r = 0;
        while (l < s.size()) {
            while (r < t.size() && s[l] != t[r])
                ++r;
            if (r < t.size()) {
                ++l;
                ++r;
            } else
                break;
        }
        cnt[l]++;
    };
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        check(t, s, cnt);
        reverse(s.begin(), s.end());
        check(invt, s, invcnt);
    }
    LL ans = 0;
    reverse(invcnt.begin(), invcnt.end());
    partial_sum(invcnt.begin(), invcnt.end(), invcnt.begin());
    for (int i = 0; i < len; ++i) {
        ans += 1ll * cnt[i] * invcnt[i];
    }
    cout << ans << '\n';

    return 0;
}

F - Beautiful Path (abc324 F)

题目大意

给定一张有向无环图，边有两种边权\(b,c\)，求一条从 \(1\)到 \(n\)的路径，使得 \(\frac{\sum b}{\sum c}\) 最大。

解题思路

初想时发现最短路的想法不太行，即时刻保留比值最大的往后扩展并不会最优的，比如此时同样是\(\frac{4}{2}, \frac{8}{4}\) ，后者值的变化的程度不如前者，又比如\(\frac{100}{99},\frac{1}{2}\)，后者受\(b\)的权值影响更大 ，万一下一条边权是\((100,0)\)，显然原先较小的权值会变得更大。

注意到这是一个分式形式，属于典型的\(0/1\)规划问题。我们可以二分答案\(l\)，判断是否可行，即 \(\frac{\sum b}{\sum c} \geq l\)，即\(\sum b - l\sum c \geq 0\)，即边权为 \(b - lc\)，问是否有条 \(1 \to n\)的路径，其边权和非负。

因为是有向无环图，设\(dp[i]\)表示到达 点\(i\)时的最大边权和 ，拓扑排序\(dp\)即可。

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

const int inf = 2e9;
const double eps = 1e-10;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<array<int, 4>> edges;
    vector<vector<int>> G(n);
    vector<int> du(n);
    vector<int> inque(n);
    for (int i = 0; i < m; ++i) {
        int u, v, b, c;
        cin >> u >> v >> b >> c;
        --u, --v;
        G[u].push_back(edges.size());
        edges.push_back({u, v, b, c});
    }
    queue<int> team;
    team.push(0);
    inque[0] = 0;
    while (!team.empty()) {
        int u = team.front();
        team.pop();
        for (auto& i : G[u]) {
            int v = edges[i][1];
            du[v]++;
            if (!inque[v])
                team.push(v);
            inque[v] = 1;
        }
    }
    auto check = [&](double x) {
        vector<double> dp(n, -inf);
        dp[0] = 0;
        team.push(0);
        auto dd = du;
        auto B = [](int b) { return b; };
        auto C = [&x](int c) { return c * x; };
        while (!team.empty()) {
            int u = team.front();
            team.pop();
            for (auto& i : G[u]) {
                auto [_, v, b, c] = edges[i];
                dp[v] = max(dp[v], dp[u] + B(b) - C(c));
                --dd[v];
                if (dd[v] == 0)
                    team.push(v);
            }
        }
        return dp[n - 1] >= -eps;
    };
    double l = 0, r = 2e9;
    while (l + eps < r) {
        double mid = (l + r) / 2;
        if (check(mid))
            l = mid;
        else
            r = mid;
    }
    cout << fixed << setprecision(12) << l << '\n';

    return 0;
}

G - Generate Arrays (abc324 G)

题目大意

给定一个关于\(n\)的排列，视为序列\(0\)，依次执行 \(m\)次操作，分两种：

  • \(1 s x\)，将序列\(s\)的第 \(x\)个元素之后的元素（不包括第 \(x\)个）删除，放到一个新序列，相对位置不变。
  • \(2 s x\)，将序列\(s\)中比\(x\)大的元素删除，放到一个新序列，相对位置不变。

问每次操作后，新生成的序列的元素个数。

解题思路

考虑暴力，我们用两个set维护一个序列，一个按下标排序，一个按值排序。这样每个操作都可以在log时间内找到分界点。

如果暴力将要删除的点移到新队列里面，复杂度最高可达 \(O(nm)\)。

考虑到每次都是将 \(x\)个数分成 \(y\) 和\(x-y\) 个数，如果按照启发式合并的思想（每次将小的合并到大的），我们采用启发式分裂（将数量较少的部分分裂出去），那么复杂度就是\(O(n\log n)\)。注意到 set的swap是\(O(1)\)的。

操作一可以直接得到分裂的两个序列的元素个数。

操作二可以先 lower_bound知道对应元素的位置，然后两头指针begin(), end()不断往中间靠，从而知道分裂的两个序列的元素个数大小关系。文章来源地址https://www.toymoban.com/news/detail-711010.html

神奇的代码
#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;
    int q;
    cin >> q;
    vector<set<array<int, 2>>> pos(q + 1), val(q + 1);
    for (int i = 0; i < n; ++i) {
        pos[0].insert({i, a[i]});
        val[0].insert({a[i], i});
    }
    auto solve = [&](set<array<int, 2>>& l, set<array<int, 2>>& r,
                     set<array<int, 2>>& ansl, set<array<int, 2>>& ansr,
                     int x) {
        auto it = l.lower_bound({x, 0});
        auto lpt = l.begin(), rpt = l.end();
        for (; lpt != it && rpt != it; lpt = next(lpt), rpt = prev(rpt))
            ;
        if (rpt == it) {
            for (; it != l.end();) {
                ansr.insert(r.extract({(*it)[1], (*it)[0]}));
                ansl.insert(*it);
                it = l.erase(it);
            }
        } else {
            auto node = *it;
            for (auto pt = l.begin(); *pt != node;) {
                ansr.insert(r.extract({(*pt)[1], (*pt)[0]}));
                ansl.insert(*pt);
                pt = l.erase(pt);
            }
            l.swap(ansl);
            r.swap(ansr);
        }
        return ansl.size();
    };
    for (int i = 1; i <= q; ++i) {
        int t, s, x;
        cin >> t >> s >> x;
        int ans = 0;
        if (t == 1) {
            int l = x, r = max(0, int(pos[s].size()) - x);
            set<array<int, 2>>::iterator it;
            if (l <= r) {
                for (it = pos[s].begin(); l > 0; it = next(it), l -= 1)
                    ;
            } else {
                for (it = pos[s].end(); r > 0; it = prev(it), r -= 1)
                    ;
            }
            if (it == pos[s].end())
                x = n;
            else
                x = (*it)[0];
            ans = solve(pos[s], val[s], pos[i], val[i], x);
        } else {
            ans = solve(val[s], pos[s], val[i], pos[i], x + 1);
        }
        cout << ans << '\n';
    }

    return 0;
}

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

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

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 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)

  • AtCoder Beginner Contest 344

    给定一个字符串，包含两个 | ，将 | 和两个 | 之间的字符消去。 按照题意模拟即可。 Python 比较简洁。 神奇的代码 给定 (n) 个数，倒序输出。 储存这 (n) 个数，然后倒着输出即可。 神奇的代码 给定三个数组 (a,b,c) ，回答 (q) 次询问。 每次询问，给定 (x) ，问能否从三

    2024年03月10日
    浏览(50)

  • AtCoder Beginner Contest 302

    给定怪物的血量 (a) 和你每次攻击扣除的血量 (b) ，问打多少次怪物才会死。 答案即为 (lceil frac{a}{b} rceil = lfloor frac{a + b - 1}{b} rfloor) 神奇的代码 给定一个二维网格，格子上有字母，找到一连串位置，使得其字符串为 (snuke) ，要求这一连串位置俩俩相邻，即有共边或

    2024年02月05日
    浏览(69)

  • AtCoder Beginner Contest 305

    给定一个数字 (x) ，输出一个数字，它是最接近 (x) 的 (5) 的倍数。 令 (y = x % 5) ，如果 (y leq 2) ，那答案就是 (x - y) ，否则就是 (x + 5 - y) 。 神奇的代码 给定 (ABCDEFG) 的相邻距离，给定两个字母，问它们的距离。 累加距离即可。 神奇的代码 二维平面，有一个矩形

    2024年02月08日
    浏览(52)

  • 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日
    浏览(25)

  • AtCoder Beginner Contest 328

    给定 (n) 个数字和一个数 (x) 。 问不大于 (x) 的数的和。 按找要求累计符合条件的数的和即可。 神奇的代码 给定一年的月数和一个月的天数。 问有多少对 ((i,j)) ，表示第 (i) 个月的第 (j) 日， (i,j) 的数位上每个数字都是一样的。 范围只有 (O(100^2)) ，枚举所有的

    2024年02月05日
    浏览(34)

  • AtCoder Beginner Contest 330

    给定 (n) 个学生的分数，以及及格分 (x) ，问多少人及格了。 依次判断即可。 神奇的代码 回答 (n) 个问题，每个问题给定 (a,l,r) ，问函数 (f(x) = |x - a|) 在 ([l,r]) 的最小值。 全定义域下，最小值显然在 (x=a) 取得。绝对值函数图像是 (V) 型。 现在限定在 ([l,r]) ，则

    2024年02月05日
    浏览(115)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包