AtCoder Beginner Contest 350 (小白来了)

youhualiuh / 2024-04-21 / 原文

这一场整体感觉还行.

A - Past ABCs

思路:

题意需要计算已经结束的比赛其中1 ~ 349属于已经结束的比赛, 其中316没有计算进去模拟即可

Code:

#include<bits/stdc++.h>
    
using namespace std;
    
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    string s; cin >> s;
    int ans = 0;
    for (int i = 3; i < 6; i++) {
        ans = ans * 10 + s[i] - '0';
    }
    if (ans >= 1 && ans <= 349 && ans != 316) {
        cout << "Yes\n";
    }
    else {
        cout << "No\n";
    }
    return 0;
}

B - Dentist Aoki

思路:

有n 个牙齿,首先如果这个这个牙齿已经存在就移除反之给他种植,所以小小模拟即可

Code:

#include<bits/stdc++.h>
    
using namespace std;
    
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, q; cin >> n >> q;
    vector <bool> vis(n + 1);  
    int ans = n;
    while (q--) {
        int x; cin >> x;
        if (!vis[x]) {
            ans --; vis[x] = 1;
        } 
        else {
            ans ++; vis[x] = 0;
        }
    }
    cout << ans << '\n';
    return 0;
}

C - Sort

思路:

它是想求出最小操作使得1 2 4 3 变成一个升序的 1 2 3 4 且每一个数字只出现一次, 可以使用桶排序来完成.

Code:

#include<bits/stdc++.h>
    
using namespace std;
    
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    vector <int> a(n + 1), rev(n + 1);
    vector <pair <int, int>> p;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        rev[a[i]] = i;
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] != i) {
            cnt ++;
            p.push_back({rev[a[i]], rev[i]});   
            int pos = rev[i];
            swap(a[i], a[pos]);
            rev[a[pos]] = pos;
            rev[a[i]] = i;
        }
    }
    cout << cnt << '\n';
    for (const pair <int, int> i : p) {
        cout << i.first << ' ' << i.second << '\n';
    }
    return 0;
}

D - New Friends　

思路:

一看到朋友的朋友就并查集敲了，题意我们是朋友那你的朋友都是我的朋友不过X需要在X的朋友Y的关系上继续建立X与Z关系求出最多可以建立多少X-Z关系

那么我们可以开始实践了以第三样例举例

你可以发现去掉重复的 1的朋友可以是 2 ~ 10

2的朋友可以是 3 ~ 10

3 的朋友可以是 4 ~ 10

.... 以此类推你可以发现一个等差公式（1 + 9） * 9 / 2 最后减去 8 我已有的关系就是最后的结果这个结论不难发现

Code:

#include<bits/stdc++.h>
    
using namespace std;
    
const int N = 2e5 + 5;

int n, f[N], m, sz[N];

using i64 = long long;

i64 ans = 0;

void init() {
    for (int i = 1; i <= n; i++) f[i] = i, sz[i] = 1;
}

int find(int x) {
    return f[x] == x ? x : f[x] = find(f[x]);
}

void merge(int x, int y) { 
    x = find(x); y = find(y);
    if (x == y) return ;
    if (sz[x] < sz[y]) {
        swap(sz[x], sz[y]);
    }
    f[y] = x; sz[x] += sz[y];  
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    init();
    for (int i = 1; i <= m; i++) {
        int x, y; cin >> x >> y; 
        merge(x, y); 
    }
    for (int i = 1; i <= n; i++) {
        if (f[i] == i) {  
            ans += 1LL * (sz[i]) * (sz[i] - 1) / 2;
        }
    }  
    cout << ans - 1LL * m << '\n';
    return 0;
}

E - Toward 0

思路:

好久没有一眼E题感觉简单

给你这两个操作使得最小盈利第一个是支付 X 日元使得 N / A 向下取整, 另外就是支付 y 日元扔色子 1 ~ 6 使得 N / b 一眼递归首先 N / 1 不太理想我们就是用1.2 的概率去获得这些棋子

所以如Code

Code:

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

i64 a, x, y;

map <i64, double> dp;

double dfs(i64 n) {
    if (!n) return 0;
    if (dp[n]) return dp[n];
    return dp[n] = min(dfs(n / a) + x, (dfs(n / 6) + dfs(n / 5) + dfs(n / 4) + dfs(n / 3) + dfs(n / 2) + 6 * y) / 5); 
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    i64 n; cin >> n >> a >> x >> y;
    dfs(n); 
    cout << fixed << setprecision(30) << dp[n] << '\n'; 
    return 0;
}

F - Transpose

思路：

这题题意很好理解就是在() 这个区间你只要倒过来且大小写互换就行题意了解开干

Code:

#include<bits/stdc++.h>
    
using namespace std;
    
const int N = 5e5 + 5;

string s; 
stack <int> st;
int a[N];

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> s; 
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') {
            st.push(i);
        }
        else if (s[i] == ')') {
            a[st.top()] = i;
            a[i] = st.top(); st.pop();
        }
    }
    int ok = 0;
    for (int i = 0; i < s.size(); i = (ok ? i - 1 : i + 1)) {
        if (s[i] == '(' || s[i] == ')') {
            i = a[i];
            ok ^= 1;
        }
        else {
            if (ok) cout << char(s[i] ^ 32);
            else cout << char(s[i]);
        }
    }
    return 0;
}