AcWing 1549. 集合相似度
原题链接
中等
作者:
_如鲸向海
,
2022-07-06 16:52:05
,
所有人可见
,
阅读 183
C++ 代码(自己模拟哈希表实现)
#include <iostream>
#include <cstring>
#include <iomanip>
using namespace std;
const int N = 53;
const int M = 10007;
int num[N][M];
int H[M];
bool cnt[M];
bool cnt1[M];
int n,m;
int find(int x){
int k = x%M;
while(H[k]!=x&&H[k]!=0x3f3f3f3f){
k++;
if(k == M) k = 0;
}
return k;
}
int main(){
cin>>n;
for(int i = 1;i<=n;i++){
cin>>num[i][0];
for(int j = 1;j<=num[i][0];j++)
cin>>num[i][j];
}
int k;
cin>>k;
for(int i = 0;i<k;i++){
int a,b;
cin>>a>>b;
memset(H,0x3f,sizeof H);
memset(cnt,0,sizeof cnt);
memset(cnt1,0,sizeof cnt1);
int nc = 0,nt = 0;
for(int j = 1;j<=num[a][0];j++)
{
if(H[find(num[a][j])]==0x3f3f3f3f){
nt++;
H[find(num[a][j])] = num[a][j];
}
}
for(int j = 1;j<=num[b][0];j++){
if(H[find(num[b][j])]==0x3f3f3f3f){
if(!cnt1[find(num[b][j])]){
nt++;
cnt1[find(num[b][j])] = true;
}
}
else{
if(!cnt[find(num[b][j])]){
nc++;
cnt[find(num[b][j])] = true;
}
}
}
double res = ((nc)*1.0/nt)*100;
cout<<fixed<<setprecision(1)<<res<<"%"<<endl;
}
}