注意点:
1.关于set合并,简单点就用s.insert(st[b].begin(),st[b].end());(注释部分)
PAT中使用上述的方法AC了但在acwing中无法AC,set中insert的时间复杂度是logn,遍历一次即是nlogn,所以acwing的数据更强一点被卡了 , 50wlog50w+100wlog50w(不知道对不对hhh)
C++ 代码
#include<bits/stdc++.h>
#define pb push_back
#define pp poop_back
#define se second
#define fi first
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N=55,mod=1e9+7;
set<int> st[N];
int len[N];
int main()
{
int n;scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int m;scanf("%d",&m);
for(int j=1;j<=m;j++)
{
int x;
scanf("%d",&x);
st[i].insert(x);
}
len[i]=st[i].size();
}
int T; scanf("%d",&T);
while(T--)
{
int a,b;
scanf("%d%d",&a,&b);
int sum=len[a]+len[b];
int x=0;
for(auto it:st[b])
{
if(st[a].count(it)) x++;
}
// set<int> s=st[a];
// s.insert(st[b].begin(),st[b].end());
double ans=(double)x/(sum-x)*100;
printf("%.2lf%\n",ans);
}
return 0;
}