【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;
}

目录
相关文章
|
25天前
|
存储 NoSQL 关系型数据库
Redis 集合(Set)
10月更文挑战第17天
36 5
|
26天前
|
算法 Java 数据处理
从HashSet到TreeSet,Java集合框架中的Set接口及其实现类以其“不重复性”要求,彻底改变了处理唯一性数据的方式。
从HashSet到TreeSet,Java集合框架中的Set接口及其实现类以其“不重复性”要求,彻底改变了处理唯一性数据的方式。HashSet基于哈希表实现,提供高效的元素操作;TreeSet则通过红黑树实现元素的自然排序,适合需要有序访问的场景。本文通过示例代码详细介绍了两者的特性和应用场景。
36 6
|
26天前
|
存储 Java 数据处理
Java Set接口凭借其独特的“不重复”特性,在集合框架中占据重要地位
【10月更文挑战第16天】Java Set接口凭借其独特的“不重复”特性,在集合框架中占据重要地位。本文通过快速去重和高效查找两个案例,展示了Set如何简化数据处理流程,提升代码效率。使用HashSet可轻松实现数据去重,而contains方法则提供了快速查找的功能,彰显了Set在处理大量数据时的优势。
32 2
|
11天前
|
存储 Java
判断一个元素是否在 Java 中的 Set 集合中
【10月更文挑战第30天】使用`contains()`方法可以方便快捷地判断一个元素是否在Java中的`Set`集合中,但对于自定义对象,需要注意重写`equals()`方法以确保正确的判断结果,同时根据具体的性能需求选择合适的`Set`实现类。
|
11天前
|
JavaScript 前端开发 开发者
set类型可以实现数组去重等
【10月更文挑战第30天】 `Set`类型在JavaScript中提供了一种方便、高效的集合数据结构,在数组去重、集合运算、数据存在性检查等方面都有广泛的应用,能够帮助开发者更简洁、高效地处理数据。
|
11天前
|
存储 Java 开发者
在 Java 中,如何遍历一个 Set 集合?
【10月更文挑战第30天】开发者可以根据具体的需求和代码风格选择合适的遍历方式。增强for循环简洁直观,适用于大多数简单的遍历场景;迭代器则更加灵活,可在遍历过程中进行更多复杂的操作;而Lambda表达式和`forEach`方法则提供了一种更简洁的函数式编程风格的遍历方式。
|
11天前
|
Java 开发者
|
26天前
|
存储 Java 数据处理
Set 是 Java 集合框架中的一个接口,不包含重复元素且不保证元素顺序。
【10月更文挑战第16天】Java Set:无序之美,不重复之魅!Set 是 Java 集合框架中的一个接口,不包含重复元素且不保证元素顺序。通过 hashCode() 和 equals() 方法实现唯一性,适用于需要唯一性约束的数据处理。示例代码展示了如何使用 HashSet 添加和遍历元素,体现了 Set 的高效性和简洁性。
26 4
|
28天前
|
存储 Java 数据处理
Set 是 Java 集合框架中的一个接口,不包含重复元素且不保证元素顺序。
Java Set:无序之美,不重复之魅!Set 是 Java 集合框架中的一个接口,不包含重复元素且不保证元素顺序。它通过 hashCode() 和 equals() 方法确保元素唯一性,适用于需要唯一性约束的数据处理。示例代码展示了如何使用 HashSet 实现这一特性。
25 5
|
26天前
|
Java 开发者
在Java集合世界中,Set以其独特的特性脱颖而出,专门应对重复元素
在Java集合世界中,Set以其独特的特性脱颖而出,专门应对重复元素。通过哈希表和红黑树两种模式,Set能够高效地识别并拒绝重复元素的入侵,确保集合的纯净。无论是HashSet还是TreeSet,都能在不同的场景下发挥出色的表现,成为开发者手中的利器。
26 2

热门文章

最新文章