AtCoder Beginner Contest 346

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

A - Adjacent Product (abc346 A)

题目大意

给定\(n\)个数,依次输出相邻俩数的乘积。

解题思路

按照题意模拟即可。

神奇的代码
#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;
    int la = 0;
    cin >> la;
    for (int i = 1; i < n; i++) {
        int a;
        cin >> a;
        cout << la * a << '\n';
        la = a;
    }

    return 0;
}



B - Piano (abc346 B)

题目大意

给定一个由wbwbwwbwbwbw无限拼接的字符串。

给定\(w,b\),问是否由一个子串,其有 \(w\)w\(b\)b

解题思路

考虑枚举子串的起点,其实只有\(len(wbwbwwbwbwbw)=12\)种情况。

枚举起点后,统计其后的\(w+b\)个字符,看看是否满足上述需求即可。

时间复杂度是 \(O(12(w+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);
    string s = "wbwbwwbwbwbw";
    int w, b;
    cin >> w >> b;
    int len = w + b;
    bool ok = false;
    for (int i = 0; i < s.size(); ++i) {
        map<char, int> cc;
        for (int j = i, cnt = 0; cnt < len; j = (j + 1) % s.size(), ++cnt) {
            cc[s[j]]++;
        }
        if (cc['w'] == w && cc['b'] == b) {
            ok = true;
            break;
        }
    }
    if (ok)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    return 0;
}



C - Σ (abc346 C)

题目大意

给定\(n\)个数 \(a_i\)

\(1 \sim k\)中,不是 \(a_i\)的数的和。

解题思路

先计算\(\sum_{i=1}{k}i = \frac{k(k+1)}{2}\),然后减去 \(a_i\)中出现过的数即可。注意要对 \(a_i\)去重,可以先 \(sort\)\(unique\),或者直接丢到 \(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, k;
    cin >> n >> k;
    vector<int> a(n);
    for (auto& i : a)
        cin >> i;
    LL ans = 1ll * k * (k + 1) / 2;
    for (auto& i : set<int>(a.begin(), a.end())) {
        if (i <= k) {
            ans -= i;
        }
    }
    cout << ans << '\n';

    return 0;
}



D - Gomamayo Sequence (abc346 D)

题目大意

给定一个\(01\)字符串\(s\),对第 \(i\)位翻转需要 \(c_i\)的代价。

定义一个好的字符串,当且仅当只有一个相邻位置上的数字是相同的。

问将字符串变成好的字符串的最小代价。

解题思路

注意到好的字符串的情况数只有\(O(n)\)个,其中 \(n\)是串 \(s\)的长度。因此我们可以枚举所有情况。

枚举相邻数字相同的位置,然后计算变成 \(010101.....\)\(101010...\)这两种情况的代价,所有位置情况代价取最小值即为答案。

如何快速计算代价?考虑到由相邻数字相同的位置左右分割开来的都是固定的\(010101\)\(101010\),因此事先预处理所有前缀和后缀变换成 \(010101\)\(101010\)的代价后,通过前缀代价+后缀代价,就可以\(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;
    string s;
    cin >> n >> s;
    vector<int> c(n);
    for (auto& i : c)
        cin >> i;
    vector<array<LL, 2>> pre(n + 1), suff(n + 1);
    const string expect = "01";
    for (int i = 0; i < n; ++i) {
        pre[i][0] =
            (s[i] == expect[i & 1] ? c[i] : 0) + (i > 0 ? pre[i - 1][0] : 0);
        pre[i][1] =
            (s[i] == expect[~i & 1] ? c[i] : 0) + (i > 0 ? pre[i - 1][1] : 0);
    }
    for (int i = n - 1; i >= 0; --i) {
        suff[i][0] = (s[i] == expect[i & 1] ? c[i] : 0) +
                     (i < n - 1 ? suff[i + 1][0] : 0);
        suff[i][1] = (s[i] == expect[~i & 1] ? c[i] : 0) +
                     (i < n - 1 ? suff[i + 1][1] : 0);
    }
    LL ans = 1e18 + 7;
    ;
    for (int i = 0; i < n - 1; ++i) {
        ans =
            min({ans, pre[i][0] + suff[i + 1][1], pre[i][1] + suff[i + 1][0]});
    }
    cout << ans << '\n';

    return 0;
}



E - Paint (abc346 E)

题目大意

\(h \times w\)的平面,格子初始全为颜色 \(0\)

依次进行 \(m\)次操作,每次操作将某一行或某一列的格子涂成颜色 \(x_i\)

问最后各个颜色的格子数量。

解题思路

朴素的想法,最后统计每块格子的颜色,时间复杂度避免不了为为\(O(hw)\)

考虑到每次操作都是对一行或一列涂色,其涂的格子数是已知的,所以可以直接累计结果。

但这样的问题是,后面的操作会影响到前面的结果,颜色会覆盖,导致先前涂的颜色数量可能会减少。

注意到后面的操作会覆盖前面的操作,如果我们对操作反过来考虑,先考虑最后一次操作,再考虑前一个操作,那么后考虑的操作不会影响先考虑的操作,就不会出现上面的先前涂的颜色会减少的问题。

因此我们对操作倒过来考虑,每次操作所涂的格子数。格子数的求法比较简单,比如一次操作对某一行涂色,其涂得格子数为\(w-\)已经涂过的列操作数。维护一下已经涂过的列和行数量即可。当然还要维护某一列和某一行是否被涂过,后涂的操作是无效的。

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

const int up = 2e5 + 8;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int h, w, m;
    cin >> h >> w >> m;
    vector<array<int, 3>> op(m);
    for (auto& [t, a, x] : op) {
        cin >> t >> a >> x;
        --a;
    }
    vector<LL> cnt(up, 0);
    vector<int> used_row(h, 0);
    vector<int> used_col(w, 0);
    int row = h, col = w;
    reverse(op.begin(), op.end());
    for (auto& [t, a, x] : op) {
        if (t == 1) {
            if (used_row[a])
                continue;
            used_row[a] = 1;
            --row;
            cnt[x] += col;
        } else {
            if (used_col[a])
                continue;
            used_col[a] = 1;
            --col;
            cnt[x] += row;
        }
    }
    cnt[0] += 1ll * h * w - accumulate(cnt.begin(), cnt.end(), 0ll);
    vector<pair<int, LL>> ans;
    for (int i = 0; i < up; ++i) {
        if (cnt[i] != 0)
            ans.emplace_back(i, cnt[i]);
    }
    cout << ans.size() << '\n';
    for (auto& [i, c] : ans) {
        cout << i << " " << c << '\n';
    }

    return 0;
}



F - SSttrriinngg in StringString (abc346 F)

题目大意

给定两个字符串\(s,t\),定义 \(f(s,n)\)表示将字符串 \(s\)重复拼接 \(n\)次。 \(g(t,k)\)表示将 \(t\)的每个字符重复 \(k\)次得到。

给定 \(n\),问最大的 \(k\),使得 \(g(t,k)\)\(f(s,n)\)的子序列。

解题思路

\(k\)越小越好满足, \(k\)越大越难满足是子序列,容易发现\(k\)是否是子序列具有单调性,因此二分\(k\)

二分\(k\)后,就按照匹配子序列那样(就近匹配)的暴力匹配 \(t\)的每个字符即可。只是细节有点多。

匹配 \(t\)的每个字符时,每个字符\(c\)\(k\)个,假设 \(s\)有该字符 \(cnt_c\)个,那先每 \(cnt_c\)\(cnt_c\)个匹配,耗掉 \(\frac{k}{cnt_c}\)\(s\),然后剩下的 \(k \% cnt_c\)\(c\)匹配 新一份的\(s\)的一部分。此时剩下的 字符就匹配\(t\)的下一个字符。

因此二分验证时需要维护信息有:

  • 当前匹配的是 \(t\)的第\(cur\)个字符
  • 当前字符还剩下 \(left\)个要匹配,
  • 当前用了 \(sum\)\(s\)
  • 当前份正匹配到第\(it\)个字符。
神奇的代码
#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;
    string s, t;
    cin >> n >> s >> t;
    vector<vector<int>> pos(26);
    for (int i = 0; i < s.size(); ++i) {
        pos[s[i] - 'a'].push_back(i);
    }
    LL l = 0, r = 1e18;
    auto check = [&](LL x) {
        if (x == 0)
            return true;
        LL sum = 0;
        int cur = 0;
        int it = 0;
        LL left = x;
        while (sum <= n && cur < t.size()) {
            int c = t[cur] - 'a';
            if (pos[c].size() == 0)
                return false;
            if (it == 0) {
                int cnt = pos[c].size();
                LL cost = left / cnt;
                sum += cost;
                left -= cost * cnt;
                LL mod = left % cnt;
                if (mod != 0) {
                    sum += 1;
                    it = (pos[c][mod - 1] + 1) % s.size();
                    left -= mod;
                } else {
                    it = (pos[c].back() + 1) % s.size();
                }
            } else {
                int st = lower_bound(pos[c].begin(), pos[c].end(), it) -
                         pos[c].begin();
                int cnt = pos[c].size() - st;
                if (left > cnt) {
                    left -= cnt;
                    it = 0;
                } else {
                    it = (pos[c][st + left - 1] + 1) % s.size();
                    left = 0;
                }
            }
            if (left == 0) {
                ++cur;
                left = x;
            }
        }
        return sum <= n;
    };
    while (l + 1 < r) {
        LL mid = (l + r) >> 1;
        if (check(mid))
            l = mid;
        else
            r = mid;
    }
    cout << l << '\n';

    return 0;
}



G - Alone (abc346 G)

题目大意

给定\(n\)个数\(a_i\)。问 \((l,r)\)的数量,满足\(a[l..r]\)中有数字仅出现一次。

解题思路

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

神奇的代码



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

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

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

相关文章

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

    给定一个形如 ABCXXX 的字符串。 问 XXX 是否是 (001 to 349) 之间,且不能是 (316) 。 将后三位转换成数字后判断即可。 神奇的代码 给定 (n) 个 (01) 序列。 进行 (q) 次操作,每次操作反转某一位上的 (01) 。 问最后 (1) 的个数。 反转操作的复杂度是 (O(1)) ,因此直接模拟

    2024年04月22日
    浏览(29)
  • 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)
  • AtCoder Beginner Contest 329

    劳累一天不该写题,启发式合并都写错了 给定一个字符串,将每个字符输出出来,中间留个空格。 遍历输出即可。 神奇的代码 给定一个数组,找出次大的数。 遍历一下,从非最大的数求一个最大值即可。 神奇的代码 给定一个字符串,问有多少个连续的子串,其由一个字母

    2024年02月05日
    浏览(74)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包