CSP202403B - 相似度计算

2026/9/4· Soln

题目描述

两个集合的 Jaccard 相似度定义为：

Sim(A,B)=\frac{|A\cap B|}{|A\cup B|}

其中：

$|A\cap B|$ 表示集合 $A$ 和集合 $B$ 的交集大小；
$|A\cup B|$ 表示集合 $A$ 和集合 $B$ 的并集大小。

当两个集合完全相同时：

Sim(A,B)=1

当两个集合没有公共元素时：

Sim(A,B)=0

小 P 希望使用 Jaccard 相似度来评估两篇文章的相似程度。

每篇文章由若干个英文单词组成，英文单词仅包含大小写英文字母。

对于给定的两篇文章，小 P 首先需要提取出两者的单词集合：

去除重复出现的单词；
忽略英文字母大小写区别。

例如：

the
The
THE

三个单词均视为同一个单词。

现在请你帮助小 P 完成前两步，计算：

两篇文章单词集合的交集大小 $|A\cap B|$ ；
两篇文章单词集合的并集大小 $|A\cup B|$ 。

输入格式

输入共三行。

第一行包含两个正整数：

n m

分别表示两篇文章包含的单词数量。

第二行包含 $n$ 个由空格分隔的单词，表示第一篇文章。

第三行包含 $m$ 个由空格分隔的单词，表示第二篇文章。

输出格式

输出两行。

第一行输出：

|A\cap B|

表示两篇文章中同时出现的不同单词数量。

第二行输出：

|A\cup B|

表示两篇文章总共包含的不同单词数量。

样例 1

输入

3 2
The tHe thE
the THE

输出

1
1

解释

忽略大小写后：

A={the}
B={the}

因此：

|A\cap B|=1

|A\cup B|=1

样例 2

输入

9 7
Par les soirs bleus dete jirai dans les sentiers
PICOTE PAR LES BLES FOULER LHERBE MENUE

输出

2
13

解释

第一篇文章：

A={bleus,dans,dete,jirai,les,par,sentiers,soirs}

第二篇文章：

B={bles,fouler,les,lherbe,menue,par,picote}

交集：

A∩B={les,par}

所以：

|A∩B|=2

并集大小：

|A∪B|=13

样例 3

输入

15 15
Thou that art now the worlds fresh ornament And only herald to the gaudy spring
Shall I compare thee to a summers day Thou art more lovely and more temperate

输出

4
24

数据范围

部分测试数据：

$n,m\le100$

并且所有字母均为小写。

全部测试数据：

$n,m\le5\times10^5$

每个单词长度不超过 10

提示

由于输入规模较大，请使用效率较高的读入方式。

题解

本题是简单的容斥原理与集合运算，基本上根据题意，处理好

单词的读入
统一大小写
集合统计和运算

以上几点就可以解决本题。代码如下：

#include <iostream>
#include <unordered_set>
#include <string>
#include <cctype>

using namespace std;

string normalize(string s) {
    for (char &c : s) {
        c = tolower(c);
    }
    return s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    unordered_set<string> A, B;

    // read A
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        A.insert(normalize(s));
    }

    // read B
    for (int i = 0; i < m; i++) {
        string s;
        cin >> s;
        B.insert(normalize(s));
    }

    // compute intersection
    int intersection = 0;

    for (const string &s : A) {
        if (B.count(s)) {
            intersection++;
        }
    }

    int unionSize = A.size() + B.size() - intersection;

    cout << intersection << endl;
    cout << unionSize << endl;

    return 0;
}

注意点

需要注意题目子任务：

80%：n,m <= 100，而且所有字母都是小写；
100%：n,m <= 5×10^5，单词长度不超过 10，而且要处理大小写。

这里就可以看出，假如第二题要拿到满分的话，必须要考虑清楚复杂度。我们这里就使用了哈希集合 unordered_set ，因为它的平均插入/查询都是 $O(1)$ 。

特性	`set`	`unordered_set`
底层	红黑树	哈希表
元素顺序	有序	无序
插入	`O(log n)`	平均 `O(1)`
查找	`O(log n)`	平均 `O(1)`
删除	`O(log n)`	平均 `O(1)`
能否 `lower_bound`	可以	不可以
适合场景	需要顺序 / 区间查找	只关心是否存在

set 内部是红黑树，维持有序；unordered_set 内部是哈希桶，所以快一点。

cicada@blog:~

$ cat ../prev→ZT1 关于矩阵 $ cat ../next→CSP202406B - 矩阵重塑（其二）

本作品采用 CC BY-NC-SA 4.0 许可协议

转载或引用请注明出处