AtCoder Beginner Contest 306

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

A - Echo (abc306 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);
    int n;
    string s;
    cin >> n >> s;
    for(auto &i : s)
        cout << i << i;
    cout << '\n';

    return 0;
}



B - Base 2 (abc306 b)

题目大意

给定一个从低位开始的二进制串,将其转为十进制。

解题思路

注意有\(64\)位,得用 unsigned long long

神奇的代码
#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);
    unsigned long long ans = 0;
    unsigned long long ji = 1;
    for(int i = 0; i < 64; ++ i){
        int x;
        cin >> x;
        if (x)
            ans += ji;
        ji <<= 1;
    }
    cout << ans << '\n';


    return 0;
}



C - Centers (abc306 c)

题目大意

给定一个\(1 \sim n\)都出现三次的数组 \(a\)

定义 \(f(x)\)表示 \(x\)第二次出现在 \(a\)的位置。

按照位置的升序输出 \(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;
    cin >> n;
    vector<int> pos(n, -2);
    for(int i = 0; i < 3 * n; ++ i){
        int x;
        cin >> x;
        -- x;
        if (pos[x] == -2){
            pos[x] = -1;
        }else if (pos[x] == -1)
            pos[x] = i;
    }
    vector<int> ans(n);
    iota(ans.begin(), ans.end(), 0);
    sort(ans.begin(), ans.end(), [&](int a, int b){
            return pos[a] < pos[b];
            });
    for(auto &i : ans)
        cout << i + 1 << ' ';
    cout << '\n';


    return 0;
}



D - Poisonous Full-Course (abc306 d)

题目大意

\(n\)个疗程,分为两种:

  • 解毒疗程,增加美味值 \(y\)
  • 中毒疗程,增加美味值 \(y\)

高桥一开始很健康,他接受了解毒疗程后还是很健康,接受中毒疗程就会中毒。中毒状态下接受解毒疗程就恢复健康,如果又接受中毒疗程则会挂。

高桥可以跳过一些疗程,问最后在他没挂的前提下,接受疗程的美味值的和的最大值。

解题思路

注意\(y\)可能会有负数。比较简单的\(dp\),由于中毒下接受中毒疗程会挂,为保证最后我们活着,我们只需保留最后的状态这个信息就好了。

\(dp[i][0/1]\)表示考虑前 \(i\)个疗程后,当前是健康/中毒状态下的最大美味值。

根据当前状态转移即可。

神奇的代码
#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;
    array<LL, 2> dp{0, 0};
    for(int i = 0; i < n; ++ i){
        array<LL, 2> dp2{0, 0};
        LL x, y;
        cin >> x >> y;
        if (x == 0){
            dp2[0] = max(dp[0] + max(y, 0ll), dp[1] + y);
            dp2[1] = dp[1];
        }else{
            dp2[0] = dp[0];
            dp2[1] = max(dp[0] + y, dp[1]);
        }
        dp.swap(dp2);
    }
    cout << *max_element(dp.begin(), dp.end()) << '\n';;

    return 0;
}



E - Best Performances (abc306 e)

题目大意

给定一个数组\(A\),定义其价值为前\(k\)大的数的和。

\(q\)次操作,每次操作令\(A_x = y\)

每次操作后,回答其价值。

操作是持久化的。

解题思路

用两个\(set\),分别维护前 \(k\)大的和剩余的数。

每次操作则修改对应的 \(set\)的值,然后比较 左边的最小值和右边的最大值,如果小于则交换一下这两个数。

每次操作最多就交换两个数,因此复杂度是\(O(q\log 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, k, q;
    cin >> n >> k >> q;
    array<set<pair<int, int>>, 2> num;
    for(int i = 0; i < k; ++ i){
        num[1].insert({0, i});
    }
    for(int i = k; i < n; ++ i){
        num[0].insert({0, i});
    }
    LL ans = 0;
    vector<int> a(n, 0);
    while(q--){
        int x, y;
        cin >> x >> y;
        -- x;
        auto token = make_pair(a[x], x);
        if (num[1].count(token)){
            num[1].erase(token);
            num[1].insert({y, x});
            ans += y - a[x];
        }else{
            num[0].erase(token);
            num[0].insert({y, x});
        }
        a[x] = y;
        while(num[1].size() < k){
            auto l = *num[0].rbegin();
            ans += l.first;
            num[1].insert(num[0].extract(l));
        }
        while(num[1].size() > k){
            auto r = *num[1].begin();
            ans -= r.first;
            num[0].insert(num[1].extract(r));
        }
        while(!num[0].empty() && num[0].rbegin() -> first > num[1].begin() -> first){
            auto l = *num[0].rbegin(), r = *num[1].begin();
            ans += l.first - r.first;
            num[1].insert(num[0].extract(l));
            num[0].insert(num[1].extract(r));
        }
        cout << ans << '\n';
    }

    return 0;
}



F - Merge Sets (abc306 f)

题目大意

对于两个交集为空的集合\(A,B\),定义\(f(A, B)\)为, \(A\)中每个元素在 \(A \cup B\)位置的和。\(A \cup B\)位置即为将其所有数升序排序后的下标(从\(1\)开始)。

现给定俩俩交集均为空的\(n\)个集合 \(s_i\) ,求\(\sum_{1 \leq i < j \leq n} f(s_i, s_j)\)

解题思路

由于\(\sum_{1 \leq i < j \leq n} f(s_i, s_j) = \sum pos(s_{i,x}, s_j)\),分析答案的贡献,发现可以转换成求每个数的贡献。因此我们的视角从枚举集合转移到枚举每个数。

对于第\(i\)个集合的升序排列的第 \(x\)个数 \(s_{i,x}\)(此处下标均从\(0\)开始,同代码一致),我们考虑它会对答案贡献多少。

注意 \(i < j\),这意味着我们只有选择 \(j > i\)的集合 \(s_j\)时,\(s_{i,x}\) 才有贡献。

然后考虑选择了\(s_j\)后, \(s_{i,x}\)的是排第几位。假设 \(s_j\)中有 \(y_j\)个小于 \(s_{i,x}\)的,那么此时 \(s_{i,x}\)的贡献是 \(x + y_j + 1\)。然后将所有\(j > i\)\(s_j\)的这些贡献累加,就是 \(s_{i,x}\)对答案的贡献。

直接累加的复杂度是 \(O(n^2)\),很显然不能这样算。

我们分析这个贡献式子,它可以拆成三部份 \(x, y_j, 1\)。第一项和最后一项会贡献 \(n - i - 1\)次(注意从第\(0\)集合算起)。
而第二项的\(y_j\), 我们可以把\(n \times m\)个数全部丢到数组\(Q\)里排个序,假设\(s_{i,x}\)排在第 \(a\)位,那么 \(\sum_{j > i} y_j\)的值就是在数组\(Q\)中,所有位置\(pos < a\),且位于集合下标 \(j > i\)的数的个数。

显然这是一个二维偏序问题,同abc283f一样。我们可以用树状数组维护关于集合下标的数的个数,然后从小到大遍历\(Q\)数组,依次把每个数加进树状数组中。这样查询一下后缀和,就是\(\sum_{j > i} y_j\)。进而 \(s_{i, x}\)的贡献就是 \(\sum_{j > i}y_j + (x + 1) \times (n - i - 1)\),对于每个数依次这么计算即可。

时间复杂度为\(O(nm \log n)\)

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

template <typename T>
class fenwick {
public:
    vector<T> fenw;
    int n;

    fenwick(int _n) : n(_n) {
        fenw.resize(n);
    }

    void modify(int x, T v) {
        while (x < n) {
            fenw[x] += v;
            x |= (x + 1);
        }
    }

    T get(int x) {
        T v{};
        while (x >= 0) {
            v += fenw[x];
            x = (x & (x + 1)) - 1;
        }
        return v;
    }
};

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<array<int, 2>> a(n * m);
    int pos = 0;
    for(int i = 0; i < n; ++ i){
        for(int j = 0; j < m; ++ j){
            cin >> a[pos][0];
            a[pos][1] = i;
            pos ++;
        }
    }
    sort(a.begin(), a.end(), [](const auto &x, const auto &y){
            return x[0] < y[0];
            });
    fenwick<int> cnt(n);
    LL ans = 0;
    int sum = 0;
    for(int i = 0; i < n * m; ++ i){
        int belong = a[i][1];
        int pre = cnt.get(belong - 1);
        int cur = cnt.get(belong);
        ans += sum - cur + 1ll * (n - belong - 1) * (cur - pre + 1);
        cnt.modify(belong, 1);
        sum ++;
    }
    cout << ans << '\n';

    return 0;
}



G - Return to 1 (abc306 g)

题目大意

给定一张有向图,问能否从\(1\)号点出发,经过 \(10^{10^{100}}\)条边后,回到 \(1\)号点。

解题思路

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

神奇的代码



Ex - Balance Scale (abc306 h)

题目大意

给定一个数组\(A\)

进行 \(m\)次操作,每次操作从 \(A\)中取两个数,然后将它们的大小结果 \(> = <\)之一加入字符串 \(s\)的最后。

问字符串\(s\)可能的情况数量。

解题思路

<++>

神奇的代码



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

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

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

相关文章

  • AtCoder Beginner Contest 344

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

    2024年03月10日
    浏览(56)
  • AtCoder Beginner Contest 339

    给一个网址,问它的后缀是多少。 找到最后的\\\'.\\\'的位置,然后输出后面的字符串即可。 python 可以一行。 神奇的代码 二维网格,上下左右相连,左上原点。初始全部为白色,位于原点,面朝上。 进行 (n) 次操作,每次操作,将当前格子颜色黑白反转,然后 如果原来是白色

    2024年02月19日
    浏览(29)
  • AtCoder Beginner Contest 340

    给定等差数列的 首项 、 末项 、 公差 。 输出这个等差数列。 从 首相 依次累加 公差 到 末项 即可。 神奇的代码 依次进行 (Q) 次操作,分两种。 1 x ,将 x 放到数组 (a) 的末尾。 2 k ,输出数组 (a) 的倒数第 (k) 项。 用 vector 模拟即可,操作 2 可快速寻址访问。 神奇的代

    2024年02月19日
    浏览(32)
  • AtCoder Beginner Contest 307

    给定 (n) 周每天的散步量,求每周七天的散步量的和。 累计求和即可。 神奇的代码 给定 (n) 个字符串 (s) ,问能否选择两个 (i,j) ,满足 (i neq j) ,且 (s_i + s_j) 是个回文串。 只有 (100) 个串,直接 (O(n^2)) 枚举判断即可。 判断回文可以将串反转后与原先的串比较是否

    2024年02月10日
    浏览(26)
  • AtCoder Beginner Contest 346

    给定 (n) 个数,依次输出相邻俩数的乘积。 按照题意模拟即可。 神奇的代码 给定一个由 wbwbwwbwbwbw 无限拼接的字符串。 给定 (w,b) ,问是否由一个子串,其有 (w) 个 w , (b) 个 b 考虑枚举子串的起点,其实只有 (len(wbwbwwbwbwbw)=12) 种情况。 枚举起点后,统计其后的 (w+b

    2024年03月24日
    浏览(28)
  • 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 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)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包