【CCCC】L2-005 集合相似度 (25分),维护set数组去重,比较统计

简介: 【CCCC】L2-005 集合相似度 (25分),维护set数组去重,比较统计

problem

L2-005 集合相似度 (25分)
给定两个整数集合,它们的相似度定义为:N
​c
​​ /N
​t
​​ ×100%。其中N
​c
​​ 是两个集合都有的不相等整数的个数,N
​t
​​ 是两个集合一共有的不相等整数的个数。你的任务就是计算任意一对给定集合的相似度。

输入格式:
输入第一行给出一个正整数N(≤50),是集合的个数。随后N行,每行对应一个集合。每个集合首先给出一个正整数M(≤10
​4
​​ ),是集合中元素的个数;然后跟M个[0,10
​9
​​ ]区间内的整数。

之后一行给出一个正整数K(≤2000),随后K行,每行对应一对需要计算相似度的集合的编号(集合从1到N编号)。数字间以空格分隔。

输出格式:
对每一对需要计算的集合,在一行中输出它们的相似度,为保留小数点后2位的百分比数字。

输入样例:
3
3 99 87 101
4 87 101 5 87
7 99 101 18 5 135 18 99
2
1 2
1 3
输出样例:
50.00%
33.33%

solution

  • 题意:给定n个集合,k个询问,两个集合的相似程度
  • 相似度:nc表示两个集合都有的元素,nt表示两个集合全部的元素(其实元素个数建立在元素互不相同的基础上)
  • 开set数组给n个集合去重。对于询问,遍历集合a时,查询集合b以统计nc和nt。
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;  cin>>n;
    vector<set<int> >v(n);
    for(int i = 0; i < n; i++){
        int t;  cin>>t;
        for(int j = 0; j < t; j++){
            int x;  cin>>x;
            v[i].insert(x);
        }
    }
    int k;  cin>>k;
    for(int i = 0; i < k; i++){
        int a, b;  cin>>a>>b;
        int nc = 0, nt = v[b-1].size();
        for(set<int>::iterator it = v[a-1].begin(); it != v[a-1].end(); it++){
            if(v[b-1].find(*it) == v[b-1].end())nt++;
            else nc++;
        }
        printf("%.2f\%\n",(double)nc/nt*100);
    }
    return 0;
}

目录
相关文章
|
9天前
|
存储 NoSQL 关系型数据库
Redis 集合(Set)
10月更文挑战第17天
23 5
|
10天前
|
算法 Java 数据处理
从HashSet到TreeSet,Java集合框架中的Set接口及其实现类以其“不重复性”要求,彻底改变了处理唯一性数据的方式。
从HashSet到TreeSet,Java集合框架中的Set接口及其实现类以其“不重复性”要求,彻底改变了处理唯一性数据的方式。HashSet基于哈希表实现,提供高效的元素操作;TreeSet则通过红黑树实现元素的自然排序,适合需要有序访问的场景。本文通过示例代码详细介绍了两者的特性和应用场景。
30 6
|
10天前
|
存储 Java 数据处理
Java Set接口凭借其独特的“不重复”特性,在集合框架中占据重要地位
【10月更文挑战第16天】Java Set接口凭借其独特的“不重复”特性,在集合框架中占据重要地位。本文通过快速去重和高效查找两个案例,展示了Set如何简化数据处理流程,提升代码效率。使用HashSet可轻松实现数据去重,而contains方法则提供了快速查找的功能,彰显了Set在处理大量数据时的优势。
21 2
|
12天前
|
存储 算法 Java
Java Set因其“无重复”特性在集合框架中独树一帜
【10月更文挑战第14天】Java Set因其“无重复”特性在集合框架中独树一帜。本文深入解析Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定的数据结构(哈希表、红黑树)确保元素唯一性,并提供最佳实践建议,包括选择合适的Set实现类和正确实现自定义对象的`hashCode()`与`equals()`方法。
23 3
|
10天前
|
存储 Java 数据处理
Set 是 Java 集合框架中的一个接口,不包含重复元素且不保证元素顺序。
【10月更文挑战第16天】Java Set:无序之美,不重复之魅!Set 是 Java 集合框架中的一个接口,不包含重复元素且不保证元素顺序。通过 hashCode() 和 equals() 方法实现唯一性,适用于需要唯一性约束的数据处理。示例代码展示了如何使用 HashSet 添加和遍历元素,体现了 Set 的高效性和简洁性。
19 4
|
12天前
|
存储 Java 数据处理
Set 是 Java 集合框架中的一个接口,不包含重复元素且不保证元素顺序。
Java Set:无序之美,不重复之魅!Set 是 Java 集合框架中的一个接口,不包含重复元素且不保证元素顺序。它通过 hashCode() 和 equals() 方法确保元素唯一性,适用于需要唯一性约束的数据处理。示例代码展示了如何使用 HashSet 实现这一特性。
16 5
|
10天前
|
Java 开发者
在Java集合世界中,Set以其独特的特性脱颖而出,专门应对重复元素
在Java集合世界中,Set以其独特的特性脱颖而出,专门应对重复元素。通过哈希表和红黑树两种模式,Set能够高效地识别并拒绝重复元素的入侵,确保集合的纯净。无论是HashSet还是TreeSet,都能在不同的场景下发挥出色的表现,成为开发者手中的利器。
22 2
|
12天前
|
Java
Java Set 是一个不包含重复元素的集合接口,确保每个元素在集合中都是唯一的
【10月更文挑战第14天】Java Set 是一个不包含重复元素的集合接口,确保每个元素在集合中都是唯一的。本文介绍了 Set 的独特特性和两个常用实现类:基于哈希表的 HashSet 和基于红黑树的 TreeSet。通过示例代码展示了它们如何高效地处理唯一性约束的数据。
31 3
|
12天前
|
存储 算法 Java
Java的Set集合以其严格的“不重复性”著称,使开发者既好奇又困惑
Java的Set集合以其严格的“不重复性”著称,使开发者既好奇又困惑。本文将探讨Set为何如此“挑剔”。Set接口不包含重复元素,适用于需要唯一性约束的场景。其内部通过哈希表或红黑树等数据结构和哈希算法、equals()方法来确保元素的唯一性。示例代码展示了Set如何自动过滤重复元素,体现了其高效性和便利性。
28 2
|
12天前
|
算法 Java 数据处理
从HashSet到TreeSet,Java集合框架中的Set接口及其实现类以其独特的“不重复性”要求,彻底改变了处理唯一性约束数据的方式。
【10月更文挑战第14天】从HashSet到TreeSet,Java集合框架中的Set接口及其实现类以其独特的“不重复性”要求,彻底改变了处理唯一性约束数据的方式。本文深入探讨Set的核心理念,并通过示例代码展示了HashSet和TreeSet的特点和应用场景。
14 2