【第10题】题解及代码分享：ABC329-F - Colored Ball

小码匠

发布于 2023-11-21 15:45:34

2570

发布于 2023-11-21 15:45:34

文章被收录于专栏：小码匠和老码农小码匠和老码农

大家好，我是小码匠，今天分享上周末AtCoder线上赛-ABC329的F题。

前置知识

路漫漫其修远兮，吾将上下而求索

离自己的既定目标：

目标：300道
已完成：10道
待完成：290道

题目描述

官方原题：

https://atcoder.jp/contests/abc329/tasks/abc329_f
洛谷：https://www.luogu.com.cn/problem/AT_abc329_f

输入数据1

6 5
1 1 1 2 2 3
1 2
6 4
5 1
3 6
4 6

输出数据1

输入数据 2

输出数据 2

1
2
0

题解

看见题目询问种类数，优先想到set，set其中一个特性就是不包含重复值，很方便我们统计
set里面有一个函数，叫insert，可以合并两个集合，但请注意，它原来的集合里面的数是不变的
- 通俗点讲，
set_x
里面的数现在要合并到
set_y
里面，合并操作完成后，
set_y
里面包含了
set_x
的数，但
set_x
里面的数仍然存在，所以还要清除
这个时候，我们发现，假如我们直接按题目要求把

set_a

合并到

set_b

里面，当

set_a

里面的数太多时，容易超时，所以我们一定是将数少的一方合并到数多的一方

合并完成后我们发现，这种合并方式会导致set里的数是混乱的，比如本来是

set_1

里的数合并到

set_2

里面，但现在数都在

set_1

里，所以我们还要在实行一步交换

交换操作可以用swap函数很方便的完成，swap函数复杂度很低，不用担心超时

赛场代码

6个测试点TLE

#include <bits/stdc++.h>

using namespace std;

//bitset<200001> g[200001];

void best_coder() {
    int n, q;
    cin >> n >> q;
    vector<set<int>> g(n);
    vector<int> l(n, 1);
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        g[i].insert(a);
    }

    for (int i = 0; i < q; ++i) {
        int x, y;
        cin >> x >> y;
        --x;
        --y;
        if (l[x]) {
            g[y].insert(g[x].begin(), g[x].end());
            g[x].erase(g[x].begin(), g[x].end());
            l[x] = 0;
            l[y] = g[y].size();
        }
        cout << l[y] << endl;
    }
}

void happy_coder() {

}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    return 0;
}

AC代码

#include <bits/stdc++.h>

using namespace std;

void best_coder() {
    int n, q;
    cin >> n >> q;
    vector<set<int>> g(n);
    vector<int> l(n, 1);
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        g[i].insert(a);
    }

    for (int i = 0; i < q; ++i) {
        int x, y;
        cin >> x >> y;
        --x;
        --y;
        if (l[x] < l[y]) {
            g[y].insert(g[x].begin(), g[x].end());
            g[x].clear();
            l[x] = 0;
            l[y] = g[y].size();
        } else {
            g[x].insert(g[y].begin(), g[y].end());
            g[y].clear();
            l[x] = 0;
            l[y] = g[x].size();
            swap(g[x], g[y]);
        }
        cout << l[y] << '\n';
    }
}

void happy_coder() {

}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    return 0;
}

END

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2023-11-21，如有侵权请联系 cloudcommunity@tencent.com 删除

set