pta题目集：L2-005 集合相似度 (25分)——set集合以及容斥原理

题目索引

题目

传送门

输入样例

3
3 99 87 101
4 87 101 5 87
7 99 101 18 5 135 18 99
2
1 2
1 3

输出样例

50.00%
33.33%

题目大意：输入n个集合，再输入k个询问，每个询问输入两个集合的编号，计算出这两个集合的集合相似度，而集合相似度就是用两个集合都有的不相等整数个数（即两个集合的交集的不重复元素个数）除以两个集合一共有的不相等整数个数（即两个集合并集的不重复元素个数）再乘100%

解法

对于交集元素个数的算法就是利用set中的find函数或者count函数

• find函数：是在集合里挨个查找某个数，例如，如果在集合s里查找x，就是s.find(x)，如果找到就返回该数的位置，找不到就返回s.end()
• count函数：查找s中x出现的次数，但x只能出现0次或1次，因为set具有自动去重功能，所以也可用来查找x元素是否在s中出现过

而并集元素个数的算法就要用到容斥原理：两个集合元素个数之和减去交集元素个数

完整代码

#include <iostream>
#include <set>
#include <cstdio>
using namespace std;
const int N = 1e4 + 10;
int main()
{
    int n;
    scanf("%d",&n);
    set<int>s[N];
    for(int i = 1 ; i <= n ; i++)
    {
        int m;
        scanf("%d",&m);
        for(int j = 0 ; j < m ; j++)
        {
            int num;
            scanf("%d",&num);
            s[i].insert(num);
        }
    }
    int k;
    scanf("%d",&k);
    while(k--)
    {
        int a,b;
        scanf("%d %d",&a,&b);
        int num1 = s[a].size();
        int num2 = s[b].size();
        int nc = 0;
        for(set<int>::iterator it = s[a].begin() ; it != s[a].end(); it++)
        {
            if(s[b].count(*it))
            {
                nc++;
            }
            //if(s[b].find(*it) != s.end())
            //{
            //	nc++;
            //}
        }
        int nt = num1 + num2 - nc;
        printf("%.2f%\n",nc * 1.0 / nt * 100);
    }
    return 0;
}