1063 Set Similarity （25 分)

2019-03-31

1063 Set Similarity （25 分)

Given two sets of integers, the similarity of the sets is defined to be N**c/N**t×100%, where N**c is the number of distinct common numbers shared by the two sets, and N**t 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:

1 2	50.0% 33.3%

作者: CHEN, Yue

单位: 浙江大学

时间限制: 500 ms

内存限制: 64 MB

代码长度限制: 16 KB

题目大意

给出一堆集合，要求给定两个集合间的相似度。相似度定义为两个集合共有元素数/两个集合总元素数。

分析

这里给出元素时会有重复元素，但是重复元素是没有用的。所以使用set存储集合，方便去重。计算相似度时，假设给出两集合号为s1,s2。nc初始化为0,nt初始化为s2.size。遍历s1,在s2中寻找其元素。找到nc++,找不到则nt++。

代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <map>
#include <set>
#include <cstring>
#include <cmath>
#include<sstream>

using namespace std;

int main() {
    int n,k,l,t;
    cin>>n;
    set<int> sets[55];
    for(int i=1;i<=n;i++){
        cin>>l;
        for(int j=0;j<l;j++){
            cin>>t;
            sets[i].insert(t);
        }
    }
    cin>>k;
    int s1,s2;
    for(int i=0;i<k;i++){
        cin>>s1>>s2;
        int nc=0,nt=sets[s2].size();
        for(auto it=sets[s1].begin();it!=sets[s1].end();it++){
            if(sets[s2].find(*it)!=sets[s2].end())
                nc++;
            else
                nt++;
        }
        double sim=(double)nc/nt*100.0;
        printf("%.1f%%\n",sim);
    }
    return 0;
}

其他

这题用map，会超时，估计是因为map的插入操作比较费时。