首页 > 其他分享 >AtCoder Beginner Contest 350 A - G 题解

AtCoder Beginner Contest 350 A - G 题解

时间：2024-04-23 19:11:26浏览次数：11  
标签：AtCoder ch return int 题解 fa 350 find dp

AtCoder Beginner Contest 350

A - Past ABCs

Solution

把最后三个字符转成数字判断即可

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s; cin >> s;
    s = s.substr(3,3);
    int x = 0;
    x = (s[0] -'0') * 100 + (s[1] - '0') * 10 + (s[2] - '0');
    if (x >= 350)
        return cout << "No" << endl, 0;
    if (x == 316)
        return cout << "No" << endl, 0;
    if (x <= 0)
        return cout << "No" << endl, 0;
    cout << "Yes" << endl;
    return 0;
}

B - Dentist Aoki

Solution

按照题意模拟

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<int> p (n + 1, 1);
    for (int i = 1; i <= m; i++) {
        int x; cin >> x;
        p[x] ^= 1;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans += p[i];
    cout << ans << endl;
    return 0;
}

C - Sort

Solution

记录 \(A[i]\) 已经每个数对应的位置 \(p[x]\) ，显然 \(pos[A[i]]=i\)

我们每次操作就是把第 \(i\) 小的数换到 \(i\) 位置

也就是位置 \(i\) 和位置 \(p[i]\)

交换之后更新 \(A\) 数组和 \(p\) 数组

Code

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
vector<pii> ans;
int main() {
    int n; cin >> n;
    vector<int> p(n + 1), a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        p[a[i]] = i;
    }
    for (int i = 1; i <= n; i++) {
        if (a[i] == i) continue;
        int pos = p[i];
        swap(a[pos], a[i]);
        ans.push_back({pos, i});
        p[a[pos]] = pos;
        p[a[i]] = i;
    }
    cout << ans.size() << endl;
    for (auto &x : ans) {
        if (x.first > x.second) 
            swap(x.first, x.second);
        cout << x.first << " " << x.second << endl;
    }
    return 0;
}

D - New Friends

Solution

显然，通过任意此操作后，任何一个原来在同一连通块的点直接都会有一条边

所以，对于一个连通块，需要添加的边数就是 \(n\times (n-1)/2 -\) 已经存在的边数，其中 \(n\) 为连通块内点的个数

判断连通块可以用并查集来实现

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int main() {
    int N, M; cin >> N >> M;
    vector<vector<int> > g(N + 1);
    vector<pii> edges;
    for (int i = 1; i <= M; i++) {
        int A, B; cin >> A >> B;
        edges.push_back({A, B});
    }

    vector<int> fa(N + 1);
    iota(fa.begin(), fa.end(), 0);
    function<int(int)> find = [&](int x) {
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    };

    for (auto &[A, B] : edges) {
        int x = find(A), y = find(B);
        if (x != y) fa[x] = y;
    }

    vector<int> cnt_x(N + 1, 0), cnt_y(N + 1, 0);
    for (int i = 1; i <= N; i++) 
        cnt_x[find(i)]++;
    for (auto &[A, B] : edges)
        cnt_y[find(A)]++;

    ll ans = 0;
    for (int i = 1; i <= N; i++) if (i == fa[i]) {
        ans += 1ll * cnt_x[i] * (cnt_x[i] - 1) / 2 - cnt_y[i];
    }
    cout << ans << endl;
    return 0;
}

E - Toward 0

Solution

一个比较显然的概率 DP

定义 \(dp[i]\) 表示把 \(i\) 变成 \(0\) 的最小花费

第一种方法：

\[dp[i]=dp[\lfloor \frac{i}{A}\rfloor]+X \]

第二种方法：

\[dp[i]=\frac{1}{6}(dp[i] + dp[\lfloor \frac{i}{2}\rfloor]+\cdots+ dp[\lfloor \frac{i}{6}\rfloor]) +Y \]

移项得：

\[dp[i]=\frac{6}{5}\times (\frac{1}{6}\times(dp[\lfloor \frac{i}{2}\rfloor]+\cdots+ dp[\lfloor \frac{i}{6}\rfloor])+Y) \]

两者中选小的转移

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
ll N, A, X, Y; 

map<ll, ld> dp;
const ld p = 1 / 6.0;
ld f(ll T) {
    if (T == 0) return 0;
    if (dp.count(T)) return dp[T];
    ld ans1 = f(T / A) + X;
    ld ans2 = 1.2 * ( (f(T / 2) + f(T / 3) + f(T / 4) + f(T / 5) + f(T / 6)) * p + Y);
    return dp[T] = min(ans1, ans2);
}

int main() {
    cin >> N >> A >> X >> Y;
    printf ("%.10lf\n", f(N));
    return 0;
}

F - Transpose

Solution

我们可以把大小写和翻转作为两种独立的操作来考虑

对于大小写，利用树状数组记录一个数字被改变大小写了多少次，如果是偶数则不动，如果是奇数次则转变大小写

对于翻转操作，可以用 Splay + 标记维护

Code

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int fa, ch[2], tag, siz;
};
vector<Node> t;
int rt;

bool ident (int x, int f) { // 判断 x 是 f 的左儿子还是右儿子
    return t[f].ch[1] == x;
}

void connect (int x, int f, int op) {
    t[f].ch[op] = x;
    t[x].fa = f;
}

void push_up (int x) {
    t[x].siz = t[t[x].ch[0]].siz + t[t[x].ch[1]].siz + 1;
}

void push_down (int x) {
    if (t[x].tag) {
        swap (t[x].ch[0], t[x].ch[1]);
        t[t[x].ch[0]].tag ^= 1;
        t[t[x].ch[1]].tag ^= 1;
        t[x].tag = 0;
    }
}

void build (int l, int r, int f) {
    if (l > r) return ;
    int mid = (l + r) >> 1;
    if (mid < f) t[f].ch[0] = mid;
    else t[f].ch[1] = mid;
    t[mid].siz = 1; t[mid].fa = f;
    if (l == r) return ;
    build(l, mid - 1, mid); build(mid + 1, r, mid);
    push_up(mid);
}

void rotate (int x) {
    int f = t[x].fa, g = t[f].fa, k = ident(x, f);
    connect (x, g, ident(f, g));
    connect (t[x].ch[k ^ 1], f, k);
    connect (f, x, k ^ 1);
    push_up(f); push_up(x);
}

void splay (int x, int top) {
    if (!top) rt = x;
    while (t[x].fa != top) {
        int f = t[x].fa, g = t[f].fa;
        if (g != top)
            ident(x, f) ^ ident(f, g) ? rotate(x) : rotate(f);
        rotate(x);
    }
}

void rever (int L, int R) {
    splay(L, 0); splay(R, L);
    t[t[R].ch[0]].tag ^= 1;
}

int find (int x, int k) { // 找到以 x 为根的树中第 k 个节点
    push_down(x);
    int sum = t[t[x].ch[0]].siz + 1;
    if (sum == k) return x;
    if (sum > k) return find(t[x].ch[0], k);
    else return find(t[x].ch[1], k - sum);
}

void inorder (int x, vector<int> & ord) {
    push_down(x);
    if (t[x].ch[0]) inorder(t[x].ch[0], ord);
    if (x >= 2 && x <= t.size() - 2)
        ord.push_back(x - 1);
    if (t[x].ch[1]) inorder(t[x].ch[1], ord);
}

vector<int> c;
void add_x (int x, int v) {
    for (int i = x; i < c.size(); i += i & -i)
        c[i] += v;
}
int query (int x) {
    int res = 0;
    for (int i = x; i; i -= i & -i)
        res += c[i];
    return res;
}

int main() {
    freopen ("F.in", "r", stdin);
    string s; cin >> s; s = " " + s;
    int n = s.size() - 1;
    t.resize(n + 3); c.resize(n + 1);
    rt = (n + 3) / 2; 
    build(1, rt - 1, rt); build(rt + 1, n + 2, rt);

    stack<int> st;
    for (int i = 1; i <= n; i++) {
        if (s[i] == '(') 
            st.push(i);
        else if (s[i] == ')'){
            int l = st.top(), r = i; st.pop();

            add_x(l, 1); add_x(r + 1, -1);

            int L = find (rt, l), R = find(rt, r + 2);
            rever(L, R);
        }
    }
    vector<int> ord;
    inorder(rt, ord);
    for (auto x : ord) {
        if (s[x] == '(' || s[x] == ')') continue;
        int v = query(x);
        if (v & 1) {
            if ('A' <= s[x] && s[x] <= 'Z') 
                s[x] = s[x] - 'A' + 'a';
            else 
                s[x] = s[x] - 'a' + 'A';
        }
        cout << s[x];
    }
    return 0;
}

G - Mediator

Solution

由于强制在线，没法乱搞

我们记录下每个节点的父亲节点 \(fa[x]\)，显然，通过 \(fa[x]\) 我们可以得出询问的答案

考虑如果维护 \(fa[x]\)

如果把 \(u\) 和 \(v\) 连接起来

image.png

不妨设 \(u\) 是 \(v\) 的父亲

由于一棵树的任意一个点当根节点仍然保持者树的性质，所以我们让 \(v\) 作为右边那棵树的根节点，然后把根节点接到 \(u\) 上面，完成合并

在转换根节点的时候，\(v\) 所在的树的 \(fa\) 也发生了改变，具体发生改变的点是 \(v\) 到原来根节点路径上的所有点，改变方式是调换了位置，子节点和父节点发生了调换

这样的调换最多出现 \(v\) 的子树次，暴力修改会超时

想到启发式合并，每次 \(v\) 作为较的子树，\(u\) 作为较大的树，所以总时间复杂度控制在 \(O(n\log n)\)

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll TT = 998244353;

vector<int> fa, siz;

int find (int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

vector<int> real_fa;

int main() {
    freopen ("G.in", "r", stdin);
    int n, m; cin >> n >> m;
    fa.resize(n + 1); siz.resize(n + 1); real_fa.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
        siz[i] = 1;
        real_fa[i] = 0;
    };


    int lst = 0;
    while (m--) {
        ll a, b, c; cin >> a >> b >> c;
        ll A = 1 + (((a * (1ll + lst)) % TT) % 2);
        ll B = 1 + (((b * (1ll + lst)) % TT) % n);
        ll C = 1 + (((c * (1ll + lst)) % TT) % n);
        
        int op = A, u = B, v = C;
        // int op, u, v; cin >> op >> u >> v;
        if (op == 1) {
            if (siz[find(u)] < siz[find(v)]) swap(u, v);
            siz[find(u)] += siz[find(v)]; fa[find(v)] = find(u);

            int nxt = real_fa[v]; real_fa[v] = u;
            for (int s = v, f = nxt; f;) {
                int nxt = real_fa[f];
                real_fa[f] = s;
                s = f; f = nxt;
            }
        }
        else if (op == 2) {
            if (find(u) != find(v)) {
                cout << (lst = 0) << '\n';
            }
            else {
                auto check = [&](int u, int v) {
                    if (u == real_fa[real_fa[v]]) return real_fa[v];
                    if (real_fa[u] == real_fa[v]) return real_fa[u];
                    return 0;
                };
                lst = check(u, v) | check(v, u);
                cout << lst << '\n';
            }
        }
    }
    return 0;
}

标签：AtCoder,ch,return,int,题解,fa,350,find,dp
From： https://www.cnblogs.com/martian148/p/18153587

相关文章

  • ABC350C 题解
    怎么赛时连这道都不会了/ll注意到输入是个排列，这意味着我们可以直接确定每个元素应在的位置。考虑维护每个数当前所在的位置\(\{p\}\)。对于任意\(i\in[1,n]\)，我们访问\(p_i\)，如果该位置不为第\(i\)位便对排列中第\(i\)位的数\(j\)和\(i\)进行“交换”操作。“......
  • P1763 埃及分数 题解
    题目传送门【-1】前言这题的剪枝真的太妙了，很难想象巨佬是怎么独立想出来这所有的剪枝的。本题解没有包含所有的剪枝，只选了我认为最好理解的几条剪枝。想学习所有的剪枝的右转巨佬的题解。【1】本题大框架：迭代加深搜索（IDDFS）看到\(1<a<b<1000\)，可以猜测分数的个数不会......
  • initialize方法重定向无限循环问题解决方案
    由于在initialize方法中进行重定向而造成的重定向循环。当session('?user_id')检查失败时，你的代码会尝试重定向到登录页面。如果登录页面或者处理登录的控制器也继承自同一个基类（或者有类似的initialize检查），这将导致每次尝试访问登录页面时都会再次执行重定向，从而陷入无限循......
  • helpdesk桌面运维常见问题解决
    helpdesk是一套帮助IT团队管理IT工单生命周期、自动化日常工作、优化工作流程的软件或软件集合，它可以帮助IT团队提高生产力、降低成本、改善服务水平和客户体验。 在现代企业中，helpdesk桌面运维是一项至关重要的工作，helpdesk团队负责处理员工或客户在日常工作中遇到的各种技术......
  • 题解 CF1743F【Intersection and Union】
    postedon2022-10-2119:23:54|under题解|sourceproblem给定\(n\)个集合\(S_i\)，以\(l_i,r_i\)的形式给出，集合的元素就是\(\{x|x\in[l_i,r_i]\cap\mathbb{N}\}\)。有三种集合间的二元运算，分别是交（\(\cap\)）、并（\(\cup\)）、对称差（\(\oplus\)）。其中对称差（\(A\oplusB......
  • 【微电平台】-高并发实战经验-奇葩问题解决及流程优化之旅
    微电平台微电平台是集电销、企业微信等于一体的综合智能SCRMSAAS化系统，涵盖多渠道管理、全客户生命周期管理、私域营销运营等主要功能，承接了京东各业务线服务，专注于为业务提供职场外包式的一站式客户管理及一体化私域运营服务。 导读本文介绍电销系统【客户名单离线打标......
  • CF1863G Swaps 题解
    题目链接点击打开链接题目解法这么牛的题！！！先套路地建图，连边\(i\toa_i\)考虑交换\(a_i\)和\(a_{a_i}\)的含义，我们把边\(i\toa_i,\;a_i\toa_{a_i}\)变成了\(i\toa_{a_i}\)和\(a_i\)的自环每次交换的话分析过于复杂，考虑打\(tag\)，我们把所有操作过的\(i\)，在\(i......
  • Numb 题解
    前言五一网课的例题，但是网上没有题解，所以来写一篇，就当攒RP了。题目可以在这里提交。原题是Baekjoon-19083，但是交不了？题目简述给你一个偶数\(n\)，求一个二进制数\(x=\overline{a_1a_2\dotsa_n}\)，满足：\(x\equiv0\pmod{n}\)；\(\foralli\in[1,n]\)，\(\overline{......
  • CF1137F Matches Are Not a Child's Play 题解
    题目链接点击打开链接题目解法参考abruce的非\(lct\)的做法\(compare\)操作是搞笑的，可以转化成求\(u,v\)的\(when\)操作一个结论是编号最大的点一定是最晚删的，不妨令编号最大的点为根，则删除顺序一定是从下往上删的先考虑原树上单个点\(u\)的\(when\)怎么求令......
  • wps使用FileDialog(msoFileDialogFolderPicker)问题解决
    在vba里面使用了WithApplication.FileDialog(msoFileDialogFolderPicker)，在excel里面多次测试均正常，但在wps里面运行时，发现只有打开文档后第一次运行宏是正确的，之后运行就再取不到选取的单元格，不管怎么选取，.SelectedItems.Count都是0。百度搜索为什么。 找到两个帖子1、 ......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99