目录

• A - Favorite Sound
• B - K-th Common Divisor
• C - Unification
• D - Decayed Bridges

A - Favorite Sound

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;
typedef long long LL;

int main(){
    int a, b, c;
    cin >> a >> b >> c;
    cout << min(c, b / a) << endl;
    return 0;
}

B - K-th Common Divisor

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;
typedef long long LL;
int res[N];

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    int num = 0;
    for (int i = 1; i <= min(a, b); i++) {
        if ((a % i == 0) && (b % i == 0)) {
            res[num++] = i;
        }
    }
    cout << res[num - c] << endl;
    return 0;
}

C - Unification

给出一个长度为n的字符串，由0和1组成，每次可以将相邻的不同的数字删掉（删掉后左右两边变成相邻），问最多可以删掉多少

直接输出出现次数较少的字符的两倍即可

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;
typedef long long LL;
stack<int> st;
int main() {
    string s;
    cin >> s;
    int num1=0,num0=0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '0') num0++;
        else
            num1++;
    }

    cout << 2*min(num1,num0) << endl;
    return 0;
}

D - Decayed Bridges

给出n个点，m条边，问依次删去每个边后，有多少个点对之间不能互达

并查集倒着维护即可，每次删边相当于将两个集合合并起来

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;
typedef long long LL;
int n, m, f[N];
LL d[N];
int findf(int x) { return f[x] == x ? x : f[x] = findf(f[x]); }
struct node {
    int x, y;
} q[N];
LL ress[N];
LL res = 0;
void Union(int x, int y) {
    int fx = findf(x), fy = findf(y);
    if (fx != fy) {
        res -= d[fx] * d[fy];
        f[fx] = fy;
        d[fy] += d[fx];
    }
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) f[i] = i, d[i] = 1;
    for (int i = 0; i < m; i++) {
        cin >> q[i].x >> q[i].y;
    }
    for (int i = 1; i < n; i++) {
        res += (LL)i;
    }
    for (int i = m - 1; i >= 0; i--) {
        ress[i] = res;
        int x = q[i].x, y = q[i].y;
        Union(x, y);
    }
    for (int i = 0; i < m; i++) cout << ress[i] << endl;
    return 0;
}