CCF-CSP认证考试 202403-2 相似度计算 100分题解

更多 CSP 认证考试题目题解可以前往：CSP-CCF 认证考试真题题解

原题链接： 202403-2 相似度计算

时间限制： 1.0 秒

空间限制： 512 MiB

题目背景

两个集合的 Jaccard 相似度定义为： S i m ( A , B ) = ∣ A ∩ B ∣ ∣ A ∪ B ∣ Sim(A, B) = \frac{|A \cap B|}{|A \cup B|} Sim(A,B)=∣A∪B∣∣A∩B∣​​即交集的大小除以并集的大小。当集合 A A A 和 B B B 完全相同时， S i m ( A , B ) = 1 Sim(A, B) = 1 Sim(A,B)=1 取得最大值；当二者交集为空时， S i m ( A , B ) = 0 Sim(A, B) = 0 Sim(A,B)=0 取得最小值。

题目描述

除了进行简单的词频统计，小 P 还希望使用 Jaccard 相似度来评估两篇文章的相似性。 具体来说，每篇文章均由若干个英文单词组成，且英文单词仅包含“大小写英文字母”。 对于给定的两篇文章，小 P 首先需要提取出两者的单词集合 A A A 和 B B B，即去掉各自重复的单词。 然后计算出：

• ∣ A ∩ B ∣ |A \cap B| ∣A∩B∣，即有多少个不同的单词同时出现在两篇文章中；
• ∣ A ∪ B ∣ |A \cup B| ∣A∪B∣，即两篇文章一共包含了多少个不同的单词。

  最后再将两者相除即可算出相似度。 需要注意，在整个计算过程中应当忽略英文字母大小写的区别，比如 the、The 和 THE 三者都应被视作同一个单词。

  试编写程序帮助小 P 完成前两步，计算出 ∣ A ∩ B ∣ |A \cap B| ∣A∩B∣ 和 ∣ A ∪ B ∣ |A \cup B| ∣A∪B∣；小 P 将亲自完成最后一步的除法运算。

  输入格式

  从标准输入读入数据。

  输入共三行。

  输入的第一行包含两个正整数 n n n 和 m m m，分别表示两篇文章的单词个数。

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

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

  输出格式

  输出到标准输出。

  输出共两行。

  第一行输出一个整数 ∣ A ∩ B ∣ |A \cap B| ∣A∩B∣，即有多少个不同的单词同时出现在两篇文章中；

  第二行输出一个整数 ∣ A ∪ B ∣ |A \cup B| ∣A∪B∣，即两篇文章一共包含了多少个不同的单词。

  样例1输入

  3 2The tHe thEthe THE

  样例1输出

  11

  样例1解释

  A = B = A ∩ B = A ∪ B = A = B = A \cap B = A \cup B = A=B=A∩B=A∪B= {the}

  样例2输入

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

  样例2输出

  213

  样例2解释

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

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

  A ∩ B = A \cap B = A∩B= {les, par} ∣ A ∩ B ∣ = 2 |A \cap B| = 2 ∣A∩B∣=2

  样例3输入

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

  样例3输出

  424

  子任务

  80 % 80\% 80% 的测试数据满足： n , m ≤ 100 n, m \leq 100 n,m≤100 且所有字母均为小写；

  全部的测试数据满足： n , m ≤ 1 0 4 n, m \leq 10^{4} n,m≤104 且每个单词最多包含 10 10 10 个字母。

  ---

  题解

  将两篇文章的单词中的大写转小写后，分别放入两个 std::set 中，然后使用 std::set_intersection 和 std::set_union 分别求出两个集合的交集和并集，最后输出交集和并集的大小即可。

  时间复杂度： O ( ( n + m ) log ⁡ ( n + m ) ) \mathcal{O}((n+m)\log(n+m)) O((n+m)log(n+m))。

  参考代码（15ms，5572KB）

  /*    Created by Pujx on 2024/5/8.*/#pragma GCC optimize(2, 3, "Ofast", "inline")#include using namespace std;#define endl '\n'//#define int long long//#define double long doubleusing i64 = long long;using ui64 = unsigned long long;using i128 = __int128;#define inf (int)0x3f3f3f3f3f3f3f3f#define INF 0x3f3f3f3f3f3f3f3f#define yn(x) cout     cin  n  m;    set        string s; cin  s;        for (auto& ch : s)            if (ch >= 'A' && ch #ifdef LOCAL    freopen("C:\Users\admin\CLionProjects\Practice\data.in", "r", stdin);    freopen("C:\Users\admin\CLionProjects\Practice\data.out", "w", stdout);#endif    ios::sync_with_stdio(false);    cin.tie(0);    cout.tie(0);    int Case = 1;    //cin  Case;    while (Case--) work();    return 0;}/*     _____   _   _       _  __    __    |  _  \ | | | |     | | \ \  / /    | |_| | | | | |     | |  \ \/ /    |  ___/ | | | |  _  | |   }  {    | |     | |_| | | |_| |  / /\ \    |_|     \_____/ \_____/ /_/  \_\*/