L2-005 集合相似度-PAT团体程序设计天梯赛GPLT

短命女 2023-07-07 11:24 11阅读 0赞

> 题目来源：团体程序设计天梯赛-练习集  
> 题目地址：[L2-005 集合相似度][L2-005]

![problem][]

### 题目大意 ###

给定  n n n 个集合，然后有  k k k 次询问，每次询问都要求出  N c / N t × 100 % N\_c / N\_t \\times100\\% Nc/Nt×100%

N c N\_c Nc 表示两个集合中都有的数的个数（重复不计），相当于**求交集去重**。  
 N t N\_t Nt 表示两个集合一共有多少个数（重复不计），相当于**求并集去重**。

### 题目分析 ###

根据题意，我们在**存储集合就时候就可以将重复元素去掉**，可以用上C++ STL提供的  s e t set set 容器，它不会保存重复元素。  
![1][]  
设要求的两个集合分别为  A A A 和  B B B，它们的大小分别为  S i z e A Size\_A SizeA 和  S i z e B Size\_B SizeB

我们先遍历集合  A A A ，每访问一个元素就判断它是否在集合  B B B中出现，如果出现，则计数器  c n t cnt cnt 加一，最后**得出的  c n t cnt cnt 就是  N c N\_c Nc**。

因为有  c n t cnt cnt 个数在集合  A A A 出现一遍，又在集合  B B B 中出现了一遍，所以求  N t N\_t Nt 的时候我们需要将它减去，最后我们得到求  N t N\_t Nt 的式子如下：  
 N t = S i z e A + S i z e B − c n t N\_t=Size\_A+Size\_B-cnt Nt=SizeA\+SizeB−cnt

### 代码如下 ###

#include <bits/stdc++.h>
    
    using namespace std;
    int n, m, t, k, a, b;
    const int maxn = 1e4 + 10;
    /** * 利用stl中set来进行集合的存储 */
    set<int> vis[maxn];
    int main()
    { 
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) { 
            scanf("%d", &m);
            while (m--) { 
                scanf("%d", &t);
                vis[i].insert(t);
            }
        }
        scanf("%d", &k);
        while (k--) { 
            scanf("%d %d", &a, &b);
            // set.size() 返回的是集合中不同元素的个数
            int cnt1 = vis[a].size(), cnt2 = vis[b].size(), cnt3 = 0;
            for (auto e : vis[a]) { 
                if (vis[b].count(e))
                    cnt3++;
            }
            printf("%.2f%\n", (double)cnt3 / (cnt1 + cnt2 - cnt3) * 100);
        }
        return 0;
    }

--------------------

如果本文对你有所帮助，记得要点赞哦~

[L2-005]: https://pintia.cn/problem-sets/994805046380707840/problems/994805070149828608
[problem]: https://img-blog.csdnimg.cn/20200223084645820.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI5MjIyOQ==,size_16,color_FFFFFF,t_70
[1]: https://img-blog.csdnimg.cn/20200223100437603.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI5MjIyOQ==,size_16,color_FFFFFF,t_70