Contestant. Rank 3721. Rating +41.

A. Many A+B Problems

题意

给定 \(a, b\)，输出 \(a + b\)。

思路

如题

时间复杂度：\(O(1)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

signed main() {
    ios::sync_with_stdio(0);
    int t;
    cin >> t;
    while(t --){
        int a, b;
        cin >> a >> b;
        cout << a + b << '\n';
    }
    return 0;
}

怎么会是呢

B. Qualification Contest

题意

给定 \(n\) 个由小写字母组成的字符串，输出字典序升序排序的前 \(k\) 个字符串。

思路

考虑到 \(sort\) 对字符串的排序就是按照字典序的，所以调函数输出即可。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 110;

string a[N];

signed main() {
    ios::sync_with_stdio(0);
    int k, n;
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + k);
    for (int i = 0; i < k; i++) {
        cout << a[i] << '\n';
    }
    return 0;
}

草，卡了半天发现调函数就好了（

C. Don't be cycle

题意

给定一个无向有环图，输出最小删除边数，使整个图无环。

思路

考虑到树的结构即为无向无环，所以我们不妨跑一遍最小生成树，剩余的边就是我们想要删去的边了。

时间复杂度：\(O(e \log_2 e)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 200010, M = 400010;

int n, m;
int f[N];
int u[M], v[M], ans = 0;

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

void kruskal(){
    for(int i=0;i<m * 2;i++){
        int eu = find(u[i]), ev = find(v[i]);
        if(eu != ev){
            ans ++;
            f[ev] = eu;
        }
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin >> n >> m;
    for(int i=1;i<=n;i++) f[i] = i;
    for(int i=0;i<m;i++){
        int a, b;
        cin >> a >> b;
        u[i << 1] = a;
        v[i << 1] = b;
        u[i << 1 | 1] = b;
        v[i << 1 | 1] = a;
    }
    kruskal();
    cout << m - ans;
    return 0;
}

我蠢了，想了好一会儿