首页 > 其他分享 >[ABC350] 赛后总结

[ABC350] 赛后总结

时间：2024-04-20 22:35:59浏览次数：22  
标签：总结 return int tr id ABC350 include 赛后 size

[ABC350] 赛后总结

AK 之。

A

模拟

// Problem: A - Past ABCs
// Contest: AtCoder - AtCoder Beginner Contest 350
// Author: Moyou
// Copyright (c) 2024 Moyou All rights reserved.
// Date: 2024-04-20 20:00:23

#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int N = 2e5 + 10;

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    string s;
    cin >> s;
    int x = atoi(s.substr(3, 3).c_str());
    if(x >= 1 && x <= 349 && x != 316) cout << "Yes\n";
    else cout << "No\n";

    return 0;
}

B

模拟

C

贪心，每次和当前位置下标交换，维护映射。

// Problem: C - Sort
// Contest: AtCoder - AtCoder Beginner Contest 350
// Author: Moyou
// Copyright (c) 2024 Moyou All rights reserved.
// Date: 2024-04-20 20:03:21

#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
// #define int long long
using namespace std;
const int N = 2e5 + 10;

int n, a[N], b[N];
vector<pair<int, int> > ans;

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i], b[a[i]] = i;
    for(int i = 1; i < n; i ++) {
        if(a[i] != i) {
            ans.push_back({i, b[i]});
            int x = i, y = b[i], t = a[i];
            swap(a[i], a[b[i]]);
            b[a[x]] = x, b[a[y]] = y;
        }
    }
    cout << ans.size() << '\n';
    for(auto [x, y] : ans) cout << x  << ' ' << y << '\n';

    return 0;
}

D

连通块内完全图。

// Problem: D - New Friends
// Contest: AtCoder - AtCoder Beginner Contest 350
// Author: Moyou
// Copyright (c) 2024 Moyou All rights reserved.
// Date: 2024-04-20 20:22:21

#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#define int long long
using namespace std;
const int N = 2e5 + 10;

int n, m, a[N], b[N];
int fa[N], rk[N], top;
int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]); }
void merge(int a, int b) {
    int x = find(a), y = find(b);
    if(x == y) return ;
    if(rk[x] > rk[y]) swap(x, y);
    fa[x] = y, rk[y] += rk[x];
}
int ans;
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
        fa[i] = i, rk[i] = 1;
    for(int i = 1, a, b; i <= m; i ++) {
        cin >> a >> b;
        merge(a, b);
    }
    for(int i = 1; i <= n; i ++)
        if(fa[i] == i) ans += 1ll * rk[i] * (rk[i] - 1) / 2;
    cout << ans - m << '\n';
    

    return 0;
}

E

直接记忆化搜索即可，状态不多。

// Problem: E - Toward 0
// Contest: AtCoder - AtCoder Beginner Contest 350
// Author: Moyou
// Copyright (c) 2024 Moyou All rights reserved.
// Date: 2024-04-20 20:27:56

#include <algorithm>
#include <map>
#include <iostream>
#include <queue>
#define int long long
using namespace std;
const int N = 1e7 + 10;

map<int, double> f;
int n, a, x, y;
double DP(int n) {
    if(n == 0) return 0;
    if(f.count(n)) return f[n];
    double sum = 0;
    for(int i = 2; i <= 6; i ++)
        sum += DP(n / i);
    return f[n] = min(DP(n / a) + x, 1.0 * (sum + 6 * y) / 5);
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> a >> x >> y;
    printf("%.9lf\n", DP(n));

    return 0;
}

F

【模板】文艺平衡树

// Problem: F - Transpose
// Contest: AtCoder - AtCoder Beginner Contest 350
// Author: Moyou
// Copyright (c) 2024 Moyou All rights reserved.
// Date: 2024-04-20 20:35:01

#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#include <ctime>
#include <random>
// #define int long long
using namespace std;
const int N = 5e5 + 10;

int stk[N], top;
char ope(char ch) {
    if(islower(ch)) return toupper(ch);
    return tolower(ch);
}
struct qwq {
    int l, r;
    char key;
    int val, size;
    bool tag;
} tr[N];
int root, idx;
mt19937 rando(time(0));
#define l(k) tr[k].l
#define r(k) tr[k].r
int New(char val) {return tr[++ idx] = {0, 0, val, rando(), 1}, idx; }
void up(int k) {tr[k].size = tr[l(k)].size + tr[r(k)].size + 1; }
void down(int k)
{
    if(!tr[k].tag) return ;
    if(tr[k].key != '#') tr[k].key = ope(tr[k].key);
    swap(l(k), r(k));
    if(l(k)) tr[l(k)].tag ^= 1;
    if(r(k)) tr[r(k)].tag ^= 1;
    tr[k].tag = 0;
}
void split(int u, int x, int &a, int &b)
{
    if(!u) {a = b = 0; return ;}
    down(u);
    if(tr[l(u)].size + 1 <= x) split(r(u), x - tr[l(u)].size - 1, r(u), b), a = u;
    else split(l(u), x, a, l(u)), b = u;
    up(u);
}
int merge(int a, int b)
{
    if(!a || !b) return a + b;
    if(tr[a].val > tr[b].val) {
        down(a), r(a) = merge(r(a), b), up(a);
        return a;
    }
    else {
        down(b), l(b) = merge(a, l(b)), up(b);
        return b;
    }
}
void rev(int l, int r) {
    int a, m, b;
    split(root, r, a, b);
    split(a, l - 1, a, m);
    tr[m].tag ^= 1;
    root = merge(a, merge(m, b));
}
void print(int u) {
    if(!u) return ;
    bool f = tr[u].tag;
    down(u);
    print(l(u));
    if(tr[u].key != '#') {
        cout << tr[u].key;
    } 
    print(r(u)); 
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    string s;
    cin >> s;
    int n = s.size();
    s = " " + s;
    for(int i = 1; i <= n; i ++) {
        if(isalnum(s[i])) {
            root = merge(root, New(s[i]));
        }
        else root = merge(root, New('#'));
    }
    for(int i = 1; i <= n; i ++) {
        if(s[i] == '(') stk[++ top] = i;
        else if(s[i] == ')') {
            rev(stk[top], i);
            top --;
        }
    }
    print(root);
    return 0;
}

也可以利用括号匹配的性质递归做，但是文艺无脑好调快。

G

按度数根号分治，对于两个点度数都很大的情况需要支持 __builtin_clz 函数，但是我不知道，所以这一部分暴力过掉了。

// Problem: G - Mediator
// Contest: AtCoder - AtCoder Beginner Contest 350
// Author: Moyou
// Copyright (c) 2024 Moyou All rights reserved.
// Date: 2024-04-20 20:56:32

#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#include <bitset>
// #define int long long
using namespace std;
const int N = 1e5 + 10, B = 320, mod = 998244353;

int n, q, fa[N];
bool ok[N], is[B][B];
bitset<N> d[B];
vector<int> g[N];
int h[N], idx;
int id(int x) {
    if(h[x]) return h[x];
    return h[x] = ++ idx;
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> q;
    for(int i = 1, op, a, b, lst = 0; i <= q; i ++) {
        cin >> op >> a >> b;
        op = 1 + ((1ll * op * (1 + lst)) % mod) % 2;
        a = 1 + ((1ll * a * (1 + lst)) % mod) % n;
        b = 1 + ((1ll * b * (1 + lst)) % mod) % n;
        bool x = g[a].size() > B, y = g[b].size() > B;
        if(op == 1) {
            g[a].push_back(b), g[b].push_back(a);
            if(!x && g[a].size() > B) {
                for(auto v : g[a]) {
                    d[id(a)][v] = 1;
                    if(g[v].size() > B) is[id(v)][id(a)] = is[id(a)][id(v)] = 1;
                }
            }
            if(!y && g[b].size() > B) {
                for(auto v : g[b]) {
                    d[id(b)][v] = 1;
                    if(g[v].size() > B) is[id(v)][id(b)] = is[id(b)][id(v)] = 1;
                }
            }
            if(g[a].size() > B) d[id(a)][b] = 1;
            if(g[b].size() > B) d[id(b)][a] = 1;
            if(g[a].size() > B && g[b].size() > B) is[id(a)][id(b)] = is[id(b)][id(a)] = 1;
        }
        else {
            if(x && y) {
                if(is[id(a)][id(b)]) {
                    cout << (lst = 0) << '\n';
                    continue;
                }
                auto t = d[id(a)] & d[id(b)];
                if(t.none()) cout << (lst = 0) << '\n';
                else {
                    for(int i = 1; i <= n; i ++) {
                        if(t[i]) {
                            lst = i;
                            break;
                        }
                    }
                    cout << (lst) << '\n';
                }
            }
            else if(!x && !y) {
                for(auto v : g[a]) ok[v] = 1;
                lst = 0;
                for(auto v : g[b]) if(ok[v]) {
                    lst = v;
                    break;
                }
                cout << lst << '\n';
                for(auto v : g[a]) ok[v] = 0;
            }
            else {
                if(x) swap(a, b), swap(x, y);
                lst = 0;
                for(auto v : g[a])
                    if(d[id(b)][v]) {
                        lst = v;
                        break;
                    }
                cout << lst << '\n';
            }
        }
    }
    
    return 0;
}

启发式合并也可以做，每次合并的时候重构小连通块的形态，查询分讨容易做。

时间复杂度：\(O(n\log n)\)。

// Problem: G - Mediator
// Contest: AtCoder - AtCoder Beginner Contest 350
// Author: Moyou
// Copyright (c) 2024 Moyou All rights reserved.
// Date: 2024-04-20 20:56:32

#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int N = 1e5 + 10, mod = 998244353;

int n, q, fa[N], pa[N], sz[N];
vector<int> g[N];
bool st[N];
int find(int x) {return pa[x] == x ? x : pa[x] = find(pa[x]);}
void merge(int a, int b) {
    int x = find(a), y = find(b);
    if(x == y) return ;
    pa[x] = y, sz[y] += sz[x];
}
void dfs(int u, int f) {
    fa[u] = f;
    for(auto v : g[u]) {
        if(v == f) continue;
        dfs(v, u);
    }
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> q;
    for(int i = 1; i <= n; i ++) pa[i] = i, sz[i] = 1;
    for(int i = 1, op, a, b, lst = 0; i <= q; i ++) {
        cin >> op >> a >> b;
        op = 1 + ((1ll * op * (1 + lst)) % mod) % 2;
        a = 1 + ((1ll * a * (1 + lst)) % mod) % n;
        b = 1 + ((1ll * b * (1 + lst)) % mod) % n;
        if(op == 1) {
            if(sz[find(a)] > sz[find(b)]) swap(a, b);
            merge(a, b);
            dfs(a, b);
            g[a].push_back(b), g[b].push_back(a);
        }
        else {
            if(fa[fa[a]] == b) cout << (lst = fa[a]) << '\n';
            else if(fa[fa[b]] == a) cout << (lst = fa[b]) << '\n';
            else if(fa[a] == fa[b]) cout << (lst = fa[a]) << '\n';
            else cout << (lst = 0) << '\n';
        }
    }
    return 0;
}

总结

C 切太慢了，以为是快排，对于这种映射要细心。

G 大胆可过。

标签：总结,return,int,tr,id,ABC350,include,赛后,size
From： https://www.cnblogs.com/MoyouSayuki/p/18148301

相关文章

  • Random 项目总结 -07 截取当前程序图片
    [DllImport("gdi32.dll",CharSet=CharSet.Auto,SetLastError=true,ExactSpelling=true)]publicstaticexternintBitBlt(HandleRefhDC,intx,inty,intnWidth,intnHeight,HandleRefhSrcDC,intxSrc,intySrc,intdwRop);p......
  • Random 项目总结 -08 生成WORD 报告
    usingSystem.Windows.Forms;usingSystem.Xml;usingMsword=Microsoft.Office.Interop.Word;privatevoiddy_Click(objectsender,EventArgse){Formf1=dy.FindForm();intgx=f1.Location.X;intgy=f1.Location.Y;......
  • Random 项目总结 -06 定时器、 随机数，截图，生成WORD报告 （result完整）
    usingSystem;usingSystem.Collections.Generic;usingSystem.ComponentModel;usingSystem.Data;usingSystem.Drawing;usingSystem.Drawing.Imaging;usingSystem.Linq;usingSystem.Text;usingSystem.Windows.Forms;usingSystem.Xml;usingMsword=Microsoft.Office.......
  • ABC350题解（E-G）
    E直接搜一下\(N\)的可能到达的值的个数，发现不多（大约\(10^4\)个），直接暴力dp（记忆化搜索）。转移式\(f_i=\max(X\log_{A}N,\dfrac{\sum\limits_{j=1}^6f_{i/j}}{6}+Y)\)。化简得到\(f_i=\max(X\log_{A}N,\dfrac{\left(\sum\limits_{j=2}^6f_{i/j}\right)+6Y}{5})\)。F文艺......
  • Random 项目总结 -04设置项目项目写入XML,，调用exe
     Processpro=newProcess();stringpropath=System.AppDomain.CurrentDomain.BaseDirectory;stringt_data="";stringt_sa="";stringt_pwd="";privatevoidbutton1_Click(objectsender,Eve......
  • 天梯赛训练总结
    知识点模块1.当我们需要检验一个子串在字符串中出现的次数的时候，如果是不计大小写的，那么我们可以按要求把它全部转化为小写，比如我们要求gptGptGpT等总共的出现次数，先将其化为小写for(auto&c:s)c=tolower(c)2.寻找出现次数有两种方法，可以根据复杂度验证后选择第一种方法是......
  • 关于发布题目集1~3的总结性Blog
    前言：这几次关于答题判题程序是通过从键盘中输入提取出对应的信息（比如说题目，试卷，答卷等等）然后再进行逐一判断。从中考查的知识点是正则表达式的运用，加上了split函数的运用，类的数组运用等等。主要的还是这三点。由于一直的迭代，导致最终它的题目要求越来越多，导致难度直线上升。也从8......
  • Random 项目总结 -03测试链接按钮 测试数据链接
    注意：如果填写地址是指定端口IP地址与端口之间需要用逗号隔开。 privatevoidbutton2_Click(objectsender,EventArgse){stringstrdata=textBox1.Text;stringstrsa=textBox2.Text;stringstrpwd=textBox3.Text;......
  • Random 项目总结 -登录按钮 读取XML文件判断用户、密码是否正确
      一、登录按钮privatevoidbutton1_Click(objectsender,EventArgse){stringxmlpath=System.AppDomain.CurrentDomain.BaseDirectory+"setting.xml";XmlDocumentdocx=newXmlDocument();docx.Load(xmlpath);......
  • Random 项目总结 -设置按钮 设置数据库地址， 用户密码写入XML
    privatevoidbutton1_Click(objectsender,EventArgse){stringxmlpath=System.AppDomain.CurrentDomain.BaseDirectory+"setting.xml";XmlDocumentxmldoc=newXmlDocument();xmldoc.Load(xmlpath);......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99