AtCoder Beginner Contest 303

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

A - Similar String (abc303 a)

题目大意

给定两个字符串,问这两个字符串是否相似。

两个字符串相似,需要每个字母,要么完全相同,要么一个是1一个是l,要么一个是0一个是o

解题思路

按照题意模拟即可。

可以将全部1换成l,全部0换成o,再判断相等。

神奇的代码
#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, t;
    cin >> n >> s >> t;
    replace(s.begin(), s.end(), '1', 'l');
    replace(s.begin(), s.end(), '0', 'o');
    replace(t.begin(), t.end(), '1', 'l');
    replace(t.begin(), t.end(), '0', 'o');
    if (s == t)
        cout << "Yes" << '\n';
    else 
        cout << "No" << '\n';

    return 0;
}



B - Discord (abc303 b)

题目大意

给定mn的排列,问有多少对\((i, j),i < j\)没在这\(m\)个排列里作为相邻元素出现。

解题思路

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;
    set<array<int, 2>> qwq;
    auto add = [&](int x, int y){
        int l = min(x, y), r = max(x, y);
        qwq.insert({l, r});
    };
    for(int i = 0; i < m; ++ i){
        int la = -1;
        for(int j = 0; j < n; ++ j){
            int x;
            cin >> x;
            if (j)
                add(la, x);
            la = x;
        }
    }
    cout << n * (n - 1) / 2 - qwq.size() << '\n';

    return 0;
}



C - Dash (abc303 c)

题目大意

二维迷宫,当前\((0,0)\),生命值h。给定关于 \(LRUD\)的操作序列, 一次移动消耗一生命值。生命值为负则失败。给定\(m\)个生命值恢复物品坐标,当生命值小于 \(k\)时可以消耗该物品,恢复生命值至\(k\)

问能否执行完给定的操作序列。

解题思路

按照题意模拟即可,可以用set储存物品下标。

注意物品只能用一次,所以使用的话记得erase

神奇的代码
#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, h, k;
    string s;
    cin >> n >> m >> h >> k >> s;
    set<array<int, 2>> item;
    for(int i = 0; i < m ; ++ i){
        int x, y;
        cin >> x >> y;
        item.insert({x, y});
    }
    auto ok = [&](){
        int x = 0, y = 0;
        for(auto &i : s){
            if (i == 'L')
                x --;
            else if (i == 'R')
                x ++;
            else if (i == 'U')
                y ++;
            else if (i == 'D')
                y --;
            else {
                assert(0);
            }
            -- h;
            auto good = item.find({x, y});
            if (h < 0)
                return false;
            if (good != item.end() && h < k){
                h = k;
                item.erase(good);
            }
        }
        return true;
    };
    if (ok())
        cout << "Yes" << '\n';
    else 
        cout << "No" << '\n';

    return 0;
}



D - Shift vs. CapsLock (abc303 d)

题目大意

在键盘上输入aA串。三个操作,一个是按键a,一个是按键Shift+a,一个是按键caplock,效果同正常输入一样,分别耗时\(x,y,z\)

问输入给定aA串所花费的最小时间。

解题思路

\(dp[i][0/1]\)表示输入完前 \(i\) 个字符,当前caplock灯不亮(亮)的最小花费时间。

然后枚举上一次灯是否亮转移即可。注意一些特别情况,比如当前caplock灯亮的,输入a,可以是shift+a,也可以是caplock+a+caplock

神奇的代码
#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 x, y, z;
    string s;
    cin >> x >> y >> z >> s;
    array<LL, 2> dp{0, z};
    for(auto &i : s){
        array<LL, 2> dp2{0, 0};
        if (i == 'a'){
            dp2[0] = min(dp[0] + min(z + y + z, x), dp[1] + min(x, y) + z);
            dp2[1] = min(dp[0] + min(x, y) + z, dp[1] + min(z + x + z, y));
        }else{
            dp2[0] = min(dp[0] + min(z + x + z, y), dp[1] + min(x, y) + z);
            dp2[1] = min(dp[0] + min(x, y) + z, dp[1] + min(z + y + z, x));
        }
        dp.swap(dp2);
    }
    cout << min(dp[0], dp[1]) << '\n';
    return 0;
}



E - A Gift From the Stars (abc303 e)

题目大意

一开始有一些菊花图,然后随便选了两个度数为\(1\)的不相连通的点,连了一条边。最终得到了一棵树。

现给定这棵树,还原出原来的菊花图,以升序告诉每个菊花图的边数。

解题思路

考虑最边缘(度数为一)的点,其相邻点必定是菊花图的中心。

然后该中心旁边的旁边的点又是另外一个中心的旁边点。即另一个中心与该中心的距离为3。

即我们先去掉所有度数为\(1\)的点, 然后度数变成\(1\)的点就是一个菊花图的中心。

再去除度数为 \(1\)的点,剩下的度数为 1的点就是上述中心的相邻点。

再去除度数为 \(1\)的点,就相当于把最外围的菊花图去掉了,局面变成了一开始的样子,即此时再去除度数为\(1\)的点,然后度数变成 \(1\)的点就是另一个菊花图的中心。

因此对这棵树作一遍拓扑排序,与最外围(叶子)的距离 对 \(3\)取模为 \(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<vector<int>> edges(n);
    vector<int> du(n, 0);
    for(int i = 0; i < n - 1; ++ i){
        int u, v;
        cin >> u >> v;
        -- u, -- v;
        edges[u].push_back(v);
        edges[v].push_back(u);
        du[u] ++;
        du[v] ++;
    }
    queue<int> team;
    vector<int> dis(n, -1);
    for(int i = 0; i < n; ++ i)
        if (du[i] == 1){
            dis[i] = 0;
            team.push(i);
        }
    vector<int> ans;
    while(!team.empty()){
        auto u = team.front();
        team.pop();
        if (dis[u] % 3 == 1){
            ans.push_back(edges[u].size());
        }
        for(auto &v : edges[u]){
            if (dis[v] != -1)
                continue;
            du[v] --;
            if (du[v] == 1){
                dis[v] = dis[u] + 1;
                team.push(v);
            }
        }
    }
    sort(ans.begin(), ans.end());
    for(auto &i : ans)
        cout << i << ' ';
    cout << '\n';

    return 0;
}



F - Damage over Time (abc303 f)

题目大意

一个怪物\(h\)血。你有 \(n\)个技能,每回合仅选择一个释放。第 \(i\)个技能可以对怪物造成持续\(t_i\)回合的伤害,每回合伤害 \(d_i\)

问将怪物血量变为 \(0\)或以下,最少需要的回合数。

解题思路

初看此题,对于怎么选择技能感觉比较棘手,原因在于技能是持续伤害而不是一次性的。比如一个技能持续伤害10回,但可能5回合后怪物就死了,这样该技能实际伤害量只有一半。因此在考虑选择技能的时候不能仅考虑\(t_i \times d_i\)的值。尽管如此,对于如何选取技能仍没有头绪。

细想上述的棘手点,因为持续回合不确定,导致选择的技能实际造成的伤害是不确定的。如果我们确定了一个持续回合,比如我就打 \(x\)回合,然后看怪物的血量是否变为\(0\)或以下,那么,假设当前是第\(i\)轮的话, 我用什么技能,其实际造成的伤害是确定的,此时那我肯定是贪心地选择造成伤害最大的一个技能。

因此可以枚举持续的回合数\(x\),然后从第一回合考虑依次使用什么技能。但因为回合数最多高达\(10^{18}\),因此不能枚举。但注意到回合数与怪物剩余血量之间存在单调性,因此我们可以二分这个回合数,然后计算一下怪物的血量能否变为 \(0\)或以下。

假设枚举的回合数为 \(x\),当前处在第 \(i\)回合,也就是说接下来使用的技能伤害最多持续\(t = x - i + 1\)回合。我们考虑使用什么技能。

根据技能生效的回合数\(t_i\)\(d\)的关系,可以将技能分成两类:

  • 剩余回合能完整造成伤害的,即造成伤害数为\(t_i \times d_i\)(即 \(t_i \leq t\)
  • 剩余回合不能完整造成伤害的,即造成伤害数为\(t \times d_i\)(即 \(t_i > t\)

将技能按照\(t_i\)升序排序,前一类是\(t_i \leq t\) ,我们预处理一个关于\(t_i \times d_i\)的前缀最大值。后一类因为 \(t\)是固定的,因此就要找一个满足\(t_i > t\)最大的\(d_i\),因此再处理一个关于\(d_i\)的后缀最大值。

对于当前回合使用的技能,就取这两类技能中造成伤害值较大的那个。

由于回合数高达\(10^{18}\),一回合一回合考虑会超时,因此考虑能否多回合地考虑。

如果此时伤害值较大的第一类技能,那么包括这回合之后的回合,我们肯定是一直使用这个技能(因为它始终是第一类技能(能完整造成伤害)中伤害最大的,而第二类技能的伤害会随着\(t\)减少而更少,不会比第一类伤害值大),直到剩下的回合数不足以该技能完整造成伤害,再重新考虑,即持续使用\(cnt = t - t_i + 1\)次,造成\(cnt \times t_i \times d_i\)的伤害。之后该技能变成了第二类。

而如果伤害值较大的是第二类技能,那么包括这回合之后的回合,我们还是一直使用这个技能(因为它始终是第二类技能(不能完整造成伤害)中伤害最大的),但由于随着不断的使用,其造成的伤害会越来越少(剩余回合\(t\)不断变小),因此直到其伤害值小于第一类技能的最大值,再重新考虑,即持续使用\(cnt = t - \lfloor \frac{max_1}{d_i} \rfloor\)次,造成\(d_{max} \times (t + t - 1 + t - 2 + \cdots + t - cnt + 1) = d_{max} \times \frac{(t + t - cnt + 1)cnt}{2}\)伤害。其中\(max_1\)是第一类技能造成伤害的最大值。

这样每个技能最多考虑两次(一次第一类,一次第二类),因此验证的复杂度为\(O(n)\)

总的时间复杂度就是 \(O(n\log n)\)

由于回合数有\(O(10^{18})\),技能总伤害也有\(O(10^{18})\),验证时可能会超 long long范围,因此得开__int128

神奇的代码
#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;
    LL h;
    cin >> n >> h;
    vector<array<LL, 3>> spell(n); // t * d, t, d
    for(auto &i : spell){
        cin >> i[1] >> i[2];
        i[0] = i[1] * i[2];
        i[1] = -i[1];
    }
    sort(spell.begin(), spell.end(), [](const auto& a, const auto&b){
            return a[1] > b[1]; // t, small first
        });
    vector<array<LL, 3>> premax(n);
    premax[0] = spell[0];
    for(int i = 1; i < n; ++ i){
        premax[i] = max(premax[i - 1], spell[i]);
    }
    auto check = [&](LL x){
        int pos = n - 1;
        __int128 cur = h;
        LL sufmax = 0;
        while(cur > 0 && x > 0){
            while(pos >= 0 && -premax[pos][1] > x){
                sufmax = max(sufmax, spell[pos][2]);
                -- pos;
            }
            if (pos < 0 || premax[pos][0] < __int128(1) * sufmax * x){
                __int128 down = 0;
                if (pos >= 0)
                    down = premax[pos][0] / sufmax;
                __int128 cnt = x - down;
                __int128 sum = cnt * (x - cnt + 1 + x) / 2 * sufmax;
                cur -= sum;
                x -= cnt;
            }else{
                __int128 cnt = x - -premax[pos][1] + 1;
                cur -= cnt * premax[pos][0];
                x -= cnt;
            }
        }
        return cur <= 0;

    };
    LL l = 0, r = 1e18;
    while(l + 1 < r){
        LL mid = (l + r) >> 1;
        if (check(mid))
            r = mid;
        else 
            l = mid;
    }
    cout << r << '\n';

    return 0;
}



G - Bags Game (abc303 g)

题目大意

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

解题思路

<++>

神奇的代码



Ex - Constrained Tree Degree (abc303 h)

题目大意

给定一个集合,其元素范围在\(1 \sim n - 1\)内。

问有多少棵\(n\)个节点的数,其每个节点的度数都属于该集合里。

解题思路

<++>

神奇的代码



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

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

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

相关文章

  • AtCoder Beginner Contest 348

    给定 (n) ,输出 (ooxooxoox...) ,长度为 (n) 。 按题意模拟即可。 神奇的代码 给定 (n) 个点,对每个点,求出与其距离最远的点的下标。 (n) 只有 (100) ,对于每个点,花 (O(n)) 遍历每个点最大化距离,时间复杂度为 (O(n^2)) 。 神奇的代码 (n) 个豌豆,每个豌豆有美味值

    2024年04月08日
    浏览(42)
  • AtCoder Beginner Contest 314

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

    2024年02月13日
    浏览(40)
  • AtCoder Beginner Contest 335

    给定一个字符串,将最后一位改成 4 。 模拟即可。 神奇的代码 给定 (n) ,按字典序输出非负整数 (i,j,k) ,使得 (i+j+kleq n) (n) 只有 (21) ,直接 (O(n^3)) 枚举判断即可。 神奇的代码 二维网格,贪吃蛇,移动,进行 (q) 次操作,分两种 指定贪吃蛇下一步移动的方向 指定

    2024年01月19日
    浏览(32)
  • AtCoder Beginner Contest 322

    给定一个字符串,找到最先出现 ABC 的位置。 直接查找判断即可。 神奇的代码 给定字符串 s 和 t ,问 s 是不是 t 的前缀和后缀。 根据前后缀定义判断即可。这里试了下 python 神奇的代码 (n) 天,有 (m) 天会放烟花。 问每一天,距离未来最近的放烟花的天数。 两个双指针一

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

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

    2024年02月04日
    浏览(55)
  • AtCoder Beginner Contest 330

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

    2024年02月05日
    浏览(116)
  • AtCoder Beginner Contest 318

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

    2024年02月10日
    浏览(40)
  • AtCoder Beginner Contest 334

    给定两个数 (b,g(b neq g)) ,如果 (b) 大则输出 Bat ,否则输出 Glove 。 比较大小输出即可。 神奇的代码 给定 (a,m,l,r) ,问有多少个整数 (k) 满足 (l leq a + mk leq r) . 对不等式化简一下即为 (frac{l - a}{m} leq k leq frac{r - a}{m}) 的整数个数。 答案就是 (lfloor frac{r - a}{m} r

    2024年02月04日
    浏览(36)
  • AtCoder Beginner Contest 349

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

    2024年04月13日
    浏览(56)
  • AtCoder Beginner Contest 328

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

    2024年02月05日
    浏览(37)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包