PAT 甲级 1063 Set Similarity

时间：2024-07-23 09:03:38

https://pintia.cn/problem-sets/994805342720868352/problems/994805409175420928

Given two sets of integers, the similarity of the sets is defined to be /, where N​c​​ is the number of distinct common numbers shared by the two sets, and N​t​​ 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 (≤) which is the total number of sets. Then N lines follow, each gives a set with a positive M (≤) and followed by M integers in the range [0]. After the input of sets, a positive integer K (≤) 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%

代码：

#include <bits/stdc++.h>

using namespace std;

int N, M;

int main() {

    scanf("%d", &N);

    set<int> s[N + 1];

    for(int i = 1; i <= N; i ++) {

        int x;

        scanf("%d", &x);

        for(int j = 0; j < x; j ++) {

            int y;

            scanf("%d", &y);

            s[i].insert(y);

        }

    }

    scanf("%d", &M);

    while(M --) {

        int a, b;

        scanf("%d%d", &a, &b);

        int num = 0;

        for(set<int>::iterator it = s[b].begin(); it != s[b].end(); it ++)

            if(s[a].find(*(it)) != s[a].end())

                num ++;

        printf("%.1f%%\n", (double)num / (s[a].size() + s[b].size() - num) * 100);

    }

    return 0;

}

　　前两天第一次交居然 0 !!!!! 今天才发现输出一位我输出两位。。。。 不用 set 会超时 

　　后天出去玩 今天已经不是很想写了 哭唧唧

相关文章