开始有一题一直超时，然后不断想着改进的办法。
然后想到一种，既然每次都要寻找一个f1值其包含的值，那么可以先一次找完所有这个f1有的数。
set对于数字的查找速度远远大于map！！！map是比较慢的
#include <iostream> #include <string.h> #include <algorithm> #include <stdio.h> #include <map> #include <set> using namespace std; struct ttt { int a[1050]; int s; }; ttt qq[55]; double walk[55][55]; set<int>vis1[55]; int summ[55]; bool walked[55][55]; void init(int n){ for(int i=1;i<=qq[n].s;i++){ if(vis1[n].count(qq[n].a[i])==0){ vis1[n].insert(qq[n].a[i]); summ[n]++; } } //cout << summ[n] << endl; } double shou(int f1,int f2){ set<int>vis2; set<int>vis3; int i,j,k; double sum1,sum2; sum1=summ[f1]; sum2=0; // cout << "777" << endl; for(i=1;i<=qq[f2].s;i++){ // cout << vis1.count(qq[f2].a[i]) <<endl; // cout << vis2.count(qq[f2].a[i]) <<endl; //cout << endl; if(vis1[f1].count(qq[f2].a[i])==0&&vis3.count(qq[f2].a[i])==0){ vis3.insert(qq[f2].a[i]); sum1++; }else if(vis1[f1].count(qq[f2].a[i])==1&&vis2.count(qq[f2].a[i])==0){ vis2.insert(qq[f2].a[i]); sum2++; } } // cout << sum1 << " "<< sum2 << endl; return sum2/sum1; } int main(){ //freopen("in.txt","r",stdin); int i,j,k,l,f2,f1,f3,t1,t2,t3; int n,m; memset(summ,0,sizeof(summ)); cin >>n; for(i=1;i<=n;i++){ scanf("%d",&qq[i].s); for(j=1;j<=qq[i].s;j++) scanf("%d",&qq[i].a[j]); } cin >> m; double sum1; memset(walk,0,sizeof(walk)); for(i=1;i<=n;i++){ init(i); } /*for(i=1;i<n;i++) for(j=i+1;j<=n;j++){ sum1=shou(i,j); walk[i][j]=sum1; }*/ memset(walked,0,sizeof(walked)); for(i=1;i<=m;i++){ scanf("%d%d",&f1,&f2); // sum1=shou(f1,f2); if(f2<f1)swap(f1,f2); if(walked[f1][f2]==0){ walk[f1][f2]=shou(f1,f2); walked[f1][f2]=1; } printf("%.2f",walk[f1][f2]*100); cout << "%" <<endl; } return 0; }
