给定两个整数集合，它们的相似度定义为：N$_c$/N$_t$×100%。其中N$_c$是两个集合都有的不相等整数的个数，N*t是两个集合一共有的不相等整数的个数。你的任务就是计算任意一对给定集合的相似度。
输入格式：
输入第一行给出一个正整数N（≤50），是集合的个数。随后N行，每行对应一个集合。每个集合首先给出一个正整数M（≤10^4^），是集合中元素的个数；然后跟M个[0,10^9^]区间内的整数。
之后一行给出一个正整数K（≤2000），随后K行，每行对应一对需要计算相似度的集合的编号（集合从1到N编号）。数字间以空格分隔。
输出格式:
对每一套方案，如果可行就输出YES，否则输出NO。
输入样例:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| 10 11
8 7
6 8
4 5
8 4
8 1
1 2
1 4
9 8
9 1
1 10
2 4
5
4 10 3 8 4
6 6 1 7 5 4 9
3 1 8 4
2 2 8
7 9 8 7 6 5 4 2
|
输出样例:
思路
用set数组存储集合。对一对集合，先遍历其中一个集合，用find函数求出两个集合都有的不相等整数的个数，再求出两个集合一共有的不相等整数的个数。
或者用set_intersection()求交集
代码1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| #include<iostream>
#include<set>
using namespace std;
const int N=1e2+5;
int main(){
set<int> s[N];
int n,m,k,x;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&m);
for(int j=0;j<m;j++){
scanf("%d",&x);
s[i].insert(x);
}
}
scanf("%d",&k);
while(k--){
int a,b,c=0;
scanf("%d %d",&a,&b);
for(auto it:s[a]){
if(s[b].find(it)!=s[b].end()) c++;
}
double t=s[a].size()+s[b].size()-c;
printf("%.2lf%%\n",c/t*100);
}
return 0;
}
|
代码2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| #include<iostream>
#include<set>
#include<vector>
#include <algorithm>
using namespace std;
const int N=1e2+5;
int main(){
set<int> s[N];
int n,m,k,x;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&m);
for(int j=0;j<m;j++){
scanf("%d",&x);
s[i].insert(x);
}
}
scanf("%d",&k);
while(k--){
int a,b,c=0;
scanf("%d %d",&a,&b);
vector<int> res;
set_intersection(s[a].begin(),s[a].end(),s[b].begin(),s[b].end(),back_inserter(res));//求交集
c=res.size();
double t=s[a].size()+s[b].size()-c;
printf("%.2lf%%\n",c/t*100);
}
return 0;
}
|
