首页 > 其他分享 >AtCoder ABC 368题解

AtCoder ABC 368题解

时间：2024-08-25 18:28:03浏览次数：13  
标签：AtCoder ABC 火车 int 题解 tree using id 200005

前言

本题解部分思路来自于网络。

A - Cut

题目大意

有 \(n\) 张卡片叠在一起，从上到下给出 \(n\) 卡片的编号，将 \(k\) 张卡片从牌堆底部放到顶部后，从上到下输出卡片的编号。

解题思路

按照题意模拟即可。

code

#include <bits/stdc++.h>
using namespace std;
int a[105];
int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
    }
    for (int i = n - k + 1, I = 1; I <= n; I++, i++) {
        printf("%d ", a[i]);
        if (i == n) i = 0;
    }
    puts("");
    return 0;
}

B - Decrease 2 max elements

题目大意

给定一个长度为 \(N\) 的正整数序列 \(A=(A_1,A_2,...,A_N)\) ，求在进行几次操作之后序列 \(A\) 中只剩下了一个或更少的正整数。

  • 将序列 \(A\) 降序排序，再将序列的前两位减去 \(1\) 。

解题思路

因为数据较小，所以直接按题意模拟即可。

code

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    scanf("%d", &n);
    priority_queue<int> que;
    for (int i = 1, a; i <= n; i++) {
        scanf("%d", &a);
        que.push(a);
    }
    int a, b, cnt = 0;
    while (n > 1) {
        a = que.top();
        que.pop();
        b = que.top();
        que.pop();
        if (a - 1 <= 0) n--;
        if (b - 1 <= 0) n--;
        que.push(a - 1);
        que.push(b - 1);
        cnt++;
    }
    printf("%d\n", cnt);
    return 0;
}

C - Triple Attack

题目大意

有 \(N\) 个敌人排成一排，每个敌人都有固定的生命值。重复以下操作，直到所有敌人的生命值为 \(0\) 或更少。使用初始化为 \(0\) 的 \(T\) ：

  • \(T\) 增加 \(1\) ，然后攻击最前面的生命值大于 \(0\) 的敌人。若 \(T\) 是三的倍数，则敌人生命值减少 \(3\) ，否则减少 \(1\) 。

求当所有敌人的生命值为 0 或更少时，\(T\) 的值。

解题思路

因为数据过大，所以这道题不能用模拟。

因为 \(T\) 每加 \(3\) ，敌人的生命值就少 \(5\) ，所以可以先从最前面的生命值大于 0 的敌人的生命值中扣去尽可能多的 \(5\) ，再模拟扣除剩下的生命值。

code

#include <bits/stdc++.h>
using namespace std;
int h[200005];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", h + i);
    }
    long long cnt = 0, t = 0;
    for (int i = 1; i <= n; i++) {
        if (t != 0) {
            if (h[i] == 1) {
                t--;
                cnt++;
                continue;
            }
            if (h[i] == 2) {
                if (t == 1) {
                    cnt++;
                    t--;
                    continue;
                } else {
                    cnt += 2;
                    t -= 2;
                    continue;
                }
            }
            h[i] -= t + 2;
            cnt += t;
            t = 0;
        }
        if (h[i] <= 0) continue;
        cnt += h[i] / 5 * 3;
        h[i] %= 5;
        if (h[i] <= 0) continue;
        if (h[i] <= 3) {
            t = 3 - h[i];
            cnt += h[i];
        } else {
            t = 0;
            cnt += 3;
        }
    }
    printf("%lld\n", cnt);
    return 0;
}

D - Minimum Steiner Tree

题目大意

给定一个图和一个长度为 \(K\) 的序列 \(V=(V_1,V_2,...,V_k)\) 。考虑从图中删除一些节点和边得到一棵树，使得这棵树中包含所有 \(K\) 个指定节点 \(V_1,V_2,...,V_n\) 且节点数最少。

解题思路

先从一个被指定的节点开始深度优先搜索。遍历到第 \(i\) 个节点时，如果这个节点下面没有被指定的节点，则这个节点没有必要存在，否则保留这个节点。

code

#include <bits/stdc++.h>
using namespace std;
vector<int> a[200005];
int tag[200005];
int ans = 0;
int dfs(int u, int fa) {
    int flag = tag[u];
    for (int i : a[u]) {
        if (i == fa) continue;
        flag |= dfs(i, u);
    }
    ans += flag;
    return flag;
}
int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1, t, b; i <= n - 1; i++) {
        scanf("%d%d", &t, &b);
        a[t].push_back(b);
        a[b].push_back(t);
    }
    int root;
    for (int i = 1; i <= k; i++) {
        scanf("%d", &root);
        tag[root] = 1;
    }
    dfs(root, 0);
    printf("%d\n", ans);
    return 0;
}

E - Train Delay

题目大意

给定 \(n\) 个城市， \(m\) 趟火车的始发城市和终到城市，预定始发时间和预定终到时间和第一趟火车的延误时间。求每一趟火车延误多少时间才能使得：

  • 任意两个数 \(i,j(1 \leqslant i < j \leqslant m)\) ，如果第 \(i\) 趟火车可以换乘第 \(j\) 趟火车，则延误后第 \(i\) 趟火车也可以换乘第 \(j\) 趟火车。

解题思路

先生成一个长度为 \(2m\) 操作序列 \(M\) ，序列的每一位都代表一趟火车始发/终到。按事件的发生时间进行排序，终到记录优先。

之后遍历 \(M\) ，对于每一条记录：

  • 如果这条记录是始发记录，则这趟火车的延误时间应该是这趟火车的始发城市目前最后一趟到达的火车的到达时间减去这趟火车的始发时间。

  • 如果这条记录是终到记录，则这趟火车的延误时间再前面已经计算，所以应当更新这趟火车的终到城市目前最后一趟到达火车的到达时间。

最后就得出了每一趟火车的延误时间

code

#include <bits/stdc++.h>
using namespace std;
int a[200005], b[200005], s[200005], t[200005];
int x[200005], d[200005];
struct Node {
    int id, st, time;
    Node(int a, int b, int c)
    : id(a)
    , st(b)
    , time(c) {}
    Node()
    : id(0)
    , st(0)
    , time(0) {}
};
vector<Node> q;
int main() {
    int n, m;
    scanf("%d%d%d", &n, &m, &x[1]);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d%d", a + i, b + i, s + i, t + i);
        q.emplace_back(i, 0, s[i]);
        q.emplace_back(i, 1, t[i]);
    }
    sort(q.begin(),
         q.end(),
         [](const Node &i, const Node &j) {
             if (i.time != j.time) return i.time < j.time;
             if (i.st != j.st) return i.st > j.st;
             return i.id < j.id;
         });
    for (int i = 0; i < 2 * m; i++) {
        if (q[i].st) {
            d[b[q[i].id]] =
                max(d[b[q[i].id]], q[i].time + x[q[i].id]);
        } else {
            x[q[i].id] =
                max(x[q[i].id], d[a[q[i].id]] - s[q[i].id]);
        }
    }
    for (int i = 2; i <= m; i++) {
        printf("%d ", x[i]);
    }
    puts("");
    return 0;
}

F - Dividing Game

题目大意

给定一个长度为 \(N\) 数组 \(A=(A_1,A_2,...,A_N)\) ，两个人 Anna 和 Bruno 用这个数组玩游戏。

他们轮流进行以下操作，Anna 先行。

  • 从数组 \(A\) 中选择一个数，把这个数替换成他的一个因数，但这个因数不能是它本身。

如果某个人无法再进行操作，则这个人就输给了另一个人。

求如果两个人足够聪明，则谁会获胜。

解题思路

把一个数替换成它的一个因数也可以看作这个数除以一些他的质因数。所以可以将每一个数分解质因数，然后把每一个数的每一个质因子看成一块石头，这个问题就变成Nim博弈了。

code

#include <bits/stdc++.h>
using namespace std;
int a[100005];
int d[100005];
int main() {
    for (int i = 2; i <= 100005; i++) {
        d[i] = 1;
        for (int j = 2; j * j <= i; j++) {
            if (i % j == 0) {
                d[i] += d[i / j];
                break;
            }
        }
    }
    int n;
    scanf("%d", &n);
    int ret = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
        ret ^= d[a[i]];
    }
    if (ret) {
        puts("Anna");
    } else {
        puts("Bruno");
    }
    return 0;
}

G - Add and Multiply Queries

题目大意

给定两个长度为 \(N\) 的数组 \(A\) 和 \(B\) ，有三种操作：

  • 1 i x 将 \(A\) 数组的第 \(i\) 位设置为 \(x\) 。

  • 2 i x 将 \(B\) 数组的第 \(i\) 位设置为 \(x\) 。

  • 3 l r 解决一下问题并输出答案：

    • 最初 \(v = 0\) ，对于 \(i = l,l + 1,...,r\) ，将 \(v\) 替换为 \(v + A_i\) 或 \(vB_i\) ，求 \(v\) 最大可能值是多少。

给定一个操作序列，按顺序执行操作。

解题思路

这道题可以用线段树，前两个操作都可以用线段树很方便的解决。

对于第三个操作，可以先用二分找到区间 \([l,r]\) 中第一个 \(B_i \geqslant 2\) 的位置，然后将这个位置以前的数加到 \(v\) 里，然后乘上 \(B_i\) ，然后用同样的方法处理 \([i + 1,r]\) 。如果区间中没有一个位置使得 \(B_i \geqslant 2\) ，则把剩下的数加到 \(v\) 中去，最后输出。

code

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int n;
int a[100005];
int b[100005];
struct node {
    LL a;
    int b;
    int l, r;
    node(LL aa, int bb, int c, int d)
    : a(aa)
    , b(bb)
    , l(c)
    , r(d) {}
    node()
    : a(0)
    , b(0)
    , l(0)
    , r(0) {}
};
class xds {
public:
    vector<node> tree;
    int cnt = 0;
    int build(int l, int r) {
        int ind = ++cnt;
        if (l == r) {
            tree[ind] = node(a[l], b[l], 0, 0);
            return ind;
        }
        int mid = (l + r) / 2;
        int ll = build(l, mid);
        int rr = build(mid + 1, r);
        tree[ind] = node(tree[ll].a + tree[rr].a,
                         max(tree[ll].b, tree[rr].b),
                         ll,
                         rr);
        return ind;
    }
    void modify(
        int ind, int l, int r, int x, int a, int b) {
        if (l == r) {
            tree[ind].a = a;
            tree[ind].b = b;
            return;
        }
        int mid = (l + r) / 2;
        if (x <= mid) modify(tree[ind].l, l, mid, x, a, b);
        else modify(tree[ind].r, mid + 1, r, x, a, b);
        int ll = tree[ind].l, rr = tree[ind].r;
        tree[ind] = node(tree[ll].a + tree[rr].a,
                         max(tree[ll].b, tree[rr].b),
                         ll,
                         rr);
    }
    node query(int ind, int l, int r, int x, int y) {
        if (x <= l && r <= y) {
            return tree[ind];
        }
        int mid = (l + r) / 2;
        node ans1, ans2;
        if (x <= mid)
            ans1 = query(tree[ind].l, l, mid, x, y);
        if (mid < y)
            ans2 = query(tree[ind].r, mid + 1, r, x, y);
        return node(
            ans1.a + ans2.a, max(ans1.b, ans2.b), 0, 0);
    }
    int find(int ind, int l, int r, int x, int y) {
        if (l > y || r < x) {
            return 0;
        }
        if (x <= l && r <= y && tree[ind].b < 2) {
            return 0;
        }
        if (l == r) {
            return l;
        }
        int mid = (l + r) / 2;
        int ret = find(tree[ind].l, l, mid, x, y);
        if (ret == 0) {
            ret = find(tree[ind].r, mid + 1, r, x, y);
        }
        return ret;
    }
} t;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", b + i);
    }
    t.tree.resize(2 * n + 5);
    int root = t.build(1, n);
    int q, x, y, op;
    scanf("%d", &q);
    while (q--) {
        scanf("%d%d%d", &op, &x, &y);
        if (op == 1) {
            a[x] = y;
            t.modify(root, 1, n, x, a[x], b[x]);
        } else if (op == 2) {
            b[x] = y;
            t.modify(root, 1, n, x, a[x], b[x]);
        } else {
            LL ans = a[x];
            x++;
            while (x <= y) {
                int pos = t.find(root, 1, n, x, y);
                if (pos == 0) {
                    ans += t.query(root, 1, n, x, y).a;
                    break;
                } else {
                    node v =
                        t.query(root, 1, n, x, pos - 1);
                    ans += v.a;
                    ans = max(ans + a[pos], ans * b[pos]);
                    x = pos + 1;
                }
            }
            printf("%lld\n", ans);
        }
    }
    return 0;
}

标签：AtCoder,ABC,火车,int,题解,tree,using,id,200005
From： https://www.cnblogs.com/sxloiblog/p/18379271

相关文章

  • SP666 VOCV - Con-Junctions 题解
    注意到这个问题具有最优子结构性，考虑树上dp。记$dp[i][0/1]$表示i号节点不放灯或放灯的最小值，$s[i][0/1]$为对应的方案数。那么我们可以进行如下转移:$dp[u][0]=\sum_{u->v}dp[v][1]$$dp[u][1]=\sum_{u->v}\min(dp[v][0],dp[v][1])$在更新对应的dp数组时，我们用......
  • P9482 [NOI2023] 字符串 题解
    题目描述\(T\)组数据，给定长为\(n\)的字符串\(s\)，\(q\)次询问，给定\(i,r\)，求有多少个\(l\)满足：\(1\lel\ler\)。\(s[i:i+l-1]\)字典序小于\(R(s[i+l:i+2l-1])\)。数据范围\(1\leT\le5,1\len,q\le10^5,1\lei+2r-1\len\)。时间限制\(\texttt{1s}\)，......
  • Triple Attack 题解
    直接暴力显然不可行。我们容易发现，变量\(T\)的增量以\(3\)为循环，一次循环会造成\(5\)的贡献，所以我们容易想到对每个\(a_i\)直接对\(5\)计算倍数和取余，然后对于余数分类讨论去增加，然后对于倍数部分统一增加即可。有些细节。Code#include<bits/stdc++.h>//#include......
  • Minimum Steiner Tree 题解
    原题，详见P10723。几乎相同，我们只需要以一个需要选择的点为根，遍历子树看看有没有出现需要选择的点，然后直接去删除即可，可以看我的博客。但是我们也可以换一种做法，用类似拓扑排序的算法。先找到所有只连一条边且没有被选择的点，然后放进队列，接着依次取出队头遍历与它相连的点，同时记......
  • k8s中coredns访问连接拒绝问题解决
    问题现象1、节点访问coredns连接拒绝2、内部pod无法正常进行解析问题解决思路检查CoreDNSPod状态是否正常[root@k8s-master01~]#kubectlgetpods-nkube-system-lk8s-app=kube-dnsNAMEREADYSTATUSRESTARTSAGEcoredns-7b8d6fc5......
  • AtCoder Beginner Contest 368（ABC368）
    [ABC368F]DividingGame题意：有\(n\)堆石子，第\(i\)堆有\(a_i\)颗石子，每次可以拿走任意一堆石子数量任何数量的棋子，但是要保证拿走之后该堆的石子数量为原来的约数（不能不拿）。问是先手必胜还是后手必胜。\(n,a_i\le10^5\)。思路：发现与Nim游戏类似，且全局信息公开，状态......
  • CSP-J 2023 初赛试题解析（第三部分：完善程序（1-2））
    第一题补全后完整代码：#include<iostream>#include<vector>usingnamespacestd;intfind_missing(vector<int>&nums){intleft=0,right=nums.size()-1;while(left<right){intmid=left+(right-left)/2;if(nums[mi......
  • 洛谷SCP 2024 第一轮（初赛 J 组）模拟题解析（第三部分：完善程序（1-2））
    完善程序一（补全）#include<bits/stdc++.h>usingnamespacestd;constintMAXN=100000;intn;intvis[MAXN],a[MAXN];vector<int>ans;intcheck(intk){intx=n,top=0;for(inti=0;i<=k;i++)vis[i]=0;while(x......
  • ABC368
    A.Cut模拟代码实现#include<bits/stdc++.h>#definerep(i,n)for(inti=0;i<(n);++i)usingnamespacestd;intmain(){intn,k;cin>>n>>k;vector<int>a(n);rep(i,n)cin>>a[i];r......
  • Hitachi Vantara Programming Contest 2024（AtCoder Beginner Contest 368）- C
    题意概述有\(N\)个数，分别为\(H_1,H_2,H_3……H_N\)。你将使用初始化为\(0\)的变量\(T\)重复以下操作，直到所有数的值都变为\(0\)或更少。将\(T\)增加\(1\)。然后，减少最前方\(H_i\)值大于等于\(1\)的值。如果\(T\)是\(3\)的倍数，\(H_i\)的值会减少\(3\)；......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99