1063 Set Similarity（详细注释+35代码+set的妙用）-Toy模板网

这篇具有很好参考价值的文章主要介绍了1063 Set Similarity（详细注释+35代码+set的妙用）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

分数 25

全屏浏览题目

作者 CHEN, Yue

单位浙江大学

Given two sets of integers, the similarity of the sets is defined to be Nc/Nt×100%, where Nc is the number of distinct common numbers shared by the two sets, and Nt is the total number of distinct numbers in the two sets. Your job is to calculate the similarity of any given pair of sets.

Input Specification:

Each input file contains one test case. Each case first gives a positive integer N (≤50) which is the total number of sets. Then N lines follow, each gives a set with a positive M (≤104) and followed by M integers in the range [0,109]. After the input of sets, a positive integer K (≤2000) is given, followed by K lines of queries. Each query gives a pair of set numbers (the sets are numbered from 1 to N). All the numbers in a line are separated by a space.

Output Specification:

For each query, print in one line the similarity of the sets, in the percentage form accurate up to 1 decimal place.

Sample Input:

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

Sample Output:

50.0%
33.3%

代码长度限制

16 KB

时间限制

500 ms

内存限制

64 MB

注意：set里存储的元素不包括重复的元素

#include<bits/stdc++.h>
using namespace std;
const int N=55;
set<int>s[N];//存储某个集合的所有元素
set<int>temp;//存储要查询的两个集合合并后的元素
int main(){
   int n;
   cin>>n;
   int cur=1;
   while(n--){//输入集合个数
       int m;
       scanf("%d",&m);
       while(m--){//输入每个集合里的元素
           int t;
           scanf("%d",&t);
           s[cur].insert(t);//将元素压入第cur个集合
       }
       cur++;
   }
   int k;
   cin>>k;
   while(k--){
       int a,b;
       scanf("%d %d",&a,&b);
       for(auto t:s[a])temp.insert(t); //将要查询的两个集合里的元素全部加入到临时的集合temp里
       for(auto t:s[b])temp.insert(t);
       int total=temp.size();//计算临时集合的大小（合并后的元素集合的大小）
       int common=s[a].size()+s[b].size()-total;//计算相同的元素数量（简单的数学问题）
       double res=common*100.0/total;//结果的百分比
       printf("%.1f%\n",res);//保留一位小数
       temp.clear();//每次清空临时集合
}
   return 0;
}
文章来源地址https://www.toymoban.com/news/detail-454401.html