PAT甲级：1063 Set Similarity｜Python

目录

题目描述

Input Specification:

Output Specification:

Sample Input:

Sample Output:

题目大意 

解题思路 

Python3代码 

题目描述

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 (≤104) and followed by M integers in the range [0,109]. 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%

题目大意 

输入一堆集合 每次询问两个集合的相似程度 相似程度的算法是 ：

都有的数字 / 所有不同的数字

解题思路 

在每次输入一个集合时，我们都对它进行去重，并放入s数组中

每次读入需要计算相似度的集合A、B时

用他们两个的交集 / 全集 即为相似度

全集 = 交集 + A对于B的差异集合（A有B没有）+ B对于A的差异集合（B有A没有）

Python3代码 

import sys
N = int(input())
 
s = [0]
 
for _ in range(N) :
    tmp = list(map(int,sys.stdin.readline().split()))
    num = tmp[0] ; tmp_set = set(tmp[1:])
    s.append(tmp_set)
 
K = int(input())
for _ in range(K) :
    a,b = map(int,sys.stdin.readline().split())
    tmp_same = s[a].intersection(s[b]) # 交集
    tmp_diff_1 = s[a].difference(s[b]) # 差集
    tmp_diff_2 = s[b].difference(s[a])
    ans = len(tmp_same) / (len(tmp_diff_1)+(len(tmp_diff_2)+(len(tmp_same))))
    ans *= 100
    print('%.1f'%ans,'%',sep='')