1063. Set Similarity.md

【PAT A-1063】Set Similarity

题意概述

给定两个整数集，集合的相似度定义为$N_c/N_t\times 100%$，其中，$N_c$是两个集合共享的不同数字的数量，而$N_t$是两个集合中不同数字数量的总数。你需要计算任何给定及集合对的相似度。

输入输出格式

输入第一行给出一个正整数 N，表示集合的总数。接下来 N 行，每行先给出一个正整数 M，表示该集合的数字总数，之后给出 M 个正整数。接下来一行给出一个正整数 K，表示查询的总数。接下来 K 行，每行给出一对集合的编号（集合从 1 到 N 编号）。一行中的所有数字都用空格分隔。

对于每个查询，以百分比形式准确地显示集的相似度，精确到小数点后一位。

数据规模

$$N\le50,M\le{10}^4,K\le2000$$

算法设计

利用vector<unordered_set<gg>> v存储所有的集合，也就是说，用unordered_set<gg>存储每个集合。针对每个查询，可以利用 count_if 泛型算法求出两个集合共享的数字数量 m，假设两个集合的数字个数分别为$n_1$、$n_2$，那么这两个集合的相似度为$m/\left(n_1+n_2-m\right)\times100%$。

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    gg ni, mi, ki, ai, bi;
    cin >> ni;
    vector<unordered_set<gg>> v(ni);
    for (auto& us : v) {
        cin >> ki;
        while (ki--) {
            cin >> ai;
            us.insert(ai);
        }
    }
    cin >> mi;
    while (mi--) {
        cin >> ai >> bi;
        gg num = count_if(v[ai - 1].begin(), v[ai - 1].end(),
                          [&v, bi](gg a) { return v[bi - 1].count(a); });
        cout << fixed << setprecision(1)
             << (num * 100.0 / (v[ai - 1].size() + v[bi - 1].size() - num))
             << "%\n";
    }
    return 0;
}