1063 Set Similarity (25)

Given two sets of integers, the similarity of the sets is defined to be Nc​/Nt​×100%, where Nc​ is the number of distinct common numbers shared by the two sets, and Nt​ is the total number of distinct numbers in the two sets. Your job is to calculate the similarity of any given pair of sets.

Input Specification:

Each input file contains one test case. Each case first gives a positive integer N (≤50) which is the total number of sets. Then N lines follow, each gives a set with a positive M (≤10^4) and followed by M integers in the range [0,10^9]. After the input of sets, a positive integer K (≤2000) is given, followed by K lines of queries. Each query gives a pair of set numbers (the sets are numbered from 1 to N). All the numbers in a line are separated by a space.

Output Specification:

For each query, print in one line the similarity of the sets, in the percentage form accurate up to 1 decimal place.

Sample Input:

3
3 99 87 101
4 87 101 5 87
7 99 101 18 5 135 18 99
2
1 2
1 3

Sample Output:

50.0%
33.3%

题目大意：给定两个整数集合，它们的相似度定义为：Nc/Nt*100%。其中Nc是两个集合都有的不相等整数的个数，Nt是两个集合一共有的不相等整数的个数。你的任务就是计算任意一对给定集合的相似度。nc是两个集合的公共元素个数，nt是两个集合的所有包含的元素个数（其中元素个数表示各个元素之间互不相同）

分析：题目要求为求两个数组交集中的元素数量Nc，两个数组并集中的元素数量Nt，再求这两个数的商。注意同一个数组中的重复元素只计入一次。除了模拟，还可用set，或者哈希。

#include<algorithm>
#include <iostream>
#include  <cstdlib>
#include  <cstring>
#include   <string>
#include   <vector>
#include   <cstdio>
#include    <queue>
#include    <stack>
#include    <ctime>
#include    <cmath>
#include      <map>
#include      <set>
#define ll long long
#define INF 0x3f3f3f3f
#define db1(x) cout<<#x<<"="<<(x)<<endl
#define db2(x,y) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<endl
#define db3(x,y,z) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<endl
#define db4(x,y,z,r) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#r<<"="<<(r)<<endl
using namespace std;bool cmp(int a,int b)
{return a<b;
}int main(void)
{#ifdef testfreopen("in.txt","r",stdin);//freopen("in.txt","w",stdout);clock_t start=clock();#endif //testint n;scanf("%d",&n);int num[n+5][10010]={0},cnt[n+5]={0},temp[n+5][10010]={0};for(int i=1;i<=n;++i){scanf("%d",&cnt[i]);for(int j=0;j<cnt[i];++j)scanf("%d",&temp[i][j]);}for(int i=1;i<=n;++i)sort(temp[i],temp[i]+cnt[i]);for(int i=1;i<=n;++i){int t=0;num[i][0]=temp[i][0];for(int j=1;j<cnt[i];++j)if(temp[i][j]!=temp[i][j-1])t++,num[i][t]=temp[i][j];cnt[i]=t+1;}int k;scanf("%d",&k);for(int ii=0;ii<k;++ii){int a,b,nc=0,nt=0;scanf("%d%d",&a,&b);int l1=0,l2=0;//db2(cnt[a],cnt[b]);while(l1<cnt[a]||l2<cnt[b]){nt++;if(l1<cnt[a]&&l2<cnt[b]){if(num[a][l1]>num[b][l2])l2++;else if(num[a][l1]<num[b][l2])l1++;else nc++,l1++,l2++;}else if(l1<cnt[a])l1++;else l2++;}//db4(nc,nt,l1,l2);printf("%.1f%\n",nc*100.0/nt);}#ifdef testclockid_t end=clock();double endtime=(double)(end-start)/CLOCKS_PER_SEC;printf("\n\n\n\n\n");cout<<"Total time:"<<endtime<<"s"<<endl;        //s为单位cout<<"Total time:"<<endtime*1000<<"ms"<<endl;    //ms为单位#endif //testreturn 0;
}