AcWing 1549. 集合相似度
原题链接
中等
作者:
守拙.
,
2023-02-06 10:37:58
,
所有人可见
,
阅读 186
#include<bits/stdc++.h>
using namespace std;
set <int> s[55];
set <int>::iterator it;
//使用set来做,对于每一个输入的元素,将其插入到所属的set集合中,因为set保证了元素不重复性
//对于find函数,如果在集合s里查找x,就是s.find(x),如果找到就返回该数的位置,找不到就返回s.end()。
int main()
{
int n;
cin >> n;//n个集合
for (int i = 1; i <= n; i++)
{
int m, x;
cin >> m;
while (m--)
{
cin >> x;
s[i].insert(x);
}
}
int k, a, b;
cin >> k;//询问次数
while (k--)
{
cin >> a >> b;//询问a集合和b集合的相似度
int la = s[a].size(), lb = s[b].size(), cnt = 0;//cnt是两个集合中相同整数的数量
for (it = s[a].begin(); it != s[a].end(); it++)
{
if (s[b].find(*it) != s[b].end())
{
cnt++;
}
}
//cnt是两个集合中相同整数的数量 //la+lb-cnt是两个集合中不同整数的数量
printf("%.1lf%\n", cnt * 1.0 / (la + lb - cnt) * 100);
}
return 0;
}