AtCoder Beginner Contest 120 题解

题目链接：https://atcoder.jp/contests/abc120

 

A Favorite Sound

分析：答案为。

代码：

#include <iostream>

using namespace std;

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

 

B K-th Common Divisor

分析：A、B范围很小，枚举即可。注意要判断A、B的大小，从大到小枚举。

代码：

#include <cstdio>
#include <iostream>

using namespace std;

int main()
{
    int a, b, k;
    scanf("%d %d %d", &a, &b, &k);
    int imax = max(a, b);
    int cnt = 0;
    for(int i = imax; i >= 1; --i)
    {
        if(a % i == 0 && b % i == 0)
            cnt++;
        if(cnt == k)
        {
            printf("%d\n", i);
            break;
        }
    }
    return 0;
}

 

C Unification

分析：因为S串里只有‘0’和‘1’，所以无论如何只要还有‘0’和‘1’同时存在，就一定可以继续该操作。答案就是‘0’和‘1’的数量取最小值的两倍（一次操作两个cube）。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int main()
{
    char s[100005];
    scanf("%s", s);
    int slen = strlen(s);
    int zero = 0, one = 0;
    for(int i = 0; i < slen; ++i)
    {
        if(s[i] == '0')
            zero++;
        else if(s[i] == '1')
            one++;
    }
    printf("%d\n", min(zero, one)*2);
    return 0;
}

 

D Decayed Bridges

分析：建边后删边判断连通比较麻烦。我们可以考虑倒着建边。当所有边都删完后，。然后倒序加入每一条边，inconvenience减去加入一条边后连通的点对。判断是否在同一个连通集里可以用并查集维护。这里需要开一个数组s记录每一个集合内的点个数，初始所有点为1.之后更新的时候只要更新并查集里的根节点个数即可。每加一条边。

代码：

#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;

struct bridge
{
    int a;
    int b;
}dict[100005];

int parent[100005], trank[100005];
ll sum;
ll ans[100005] = {0};
ll s[100005];

void init()
{
    for(int i = 0; i < 100005; ++i)
    {
        parent[i] = -1;
        trank[i] = 0;
    }
}

int find_root(int x)
{
    int x_root = x;
    while(parent[x_root] != -1)
        x_root = parent[x_root];
    return x_root;
}

int union_set(int x, int y)
{
    int x_root = find_root(x);
    int y_root = find_root(y);
    if(x_root == y_root)
        return 0;
    else
    {
        if(trank[x_root] > trank[y_root])
        {
            parent[y_root] = x_root;
            sum -= s[x_root]*s[y_root];
            s[x_root] += s[y_root];
        }
        else if(trank[y_root] > trank[x_root])
        {
            parent[x_root] = y_root;
            sum -= s[x_root]*s[y_root];
            s[y_root] += s[x_root];
        }
        else
        {
            parent[y_root] = x_root;
            trank[x_root]++;
            sum -= s[x_root]*s[y_root];
            s[x_root] += s[y_root];
        }
    }
    return 1;
}

int main()
{
    init();
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i = 0; i < m; ++i)
        scanf("%d %d", &dict[i].a, &dict[i].b);
    for(int i = 0; i <= n; ++i)
        s[i] = 1;
    sum = 1ll*n*(n-1)/2;
    for(int i = m - 1; i >= 0; --i)
    {
        ans[i] = sum;
        int x = dict[i].a;
        int y = dict[i].b;
        union_set(x, y);
    }
    for(int i = 0; i < m; ++i)
        cout<<ans[i]<<endl;
    return 0;
}