CCF CSP 第33次（2024.03）（2_相似度計算_C++）
- 題目背景：
- 題目描述：
- 輸入格式：
- 輸出格式：
- 樣例1輸入：
- 樣例1輸出：
- 樣例1解釋：
- 樣例2輸入：
- 樣例2輸出：
- 樣例2解釋：
- 樣例3輸入：
- 樣例3輸出：
- 子任務：
- 解題思路：
- 思路一（字符串中字母大小寫轉換+哈希集合）：
- 代碼實現
- 代碼實現（思路一（字符串中字母大小寫轉換+哈希集合））：
時間限制： 1.0 秒
空間限制： 512 MiB
題目背景：
兩個集合的 Jaccard 相似度定義為：
Sim(A,B)= ∣A∪B∣/∣A∩B∣
?即交集的大小除以并集的大小。當集合 𝐴 和 𝐵完全相同時，𝑆𝑖𝑚(𝐴,𝐵)=1取得最大值；當二者交集為空時，𝑆𝑖𝑚(𝐴,𝐵)=0取得最小值。
題目描述：
除了進行簡單的詞頻統計，小 P 還希望使用 Jaccard 相似度來評估兩篇文章的相似性。 具體來說，每篇文章均由若干個英文單詞組成，且英文單詞僅包含“大小寫英文字母”。 對于給定的兩篇文章，小 P 首先需要提取出兩者的單詞集合 𝐴和 𝐵，即去掉各自重復的單詞。 然后計算出：
∣𝐴∩𝐵∣，即有多少個不同的單詞同時出現在兩篇文章中；
∣𝐴∪𝐵∣，即兩篇文章一共包含了多少個不同的單詞。
最后再將兩者相除即可算出相似度。 需要注意，在整個計算過程中應當忽略英文字母大小寫的區別，比如 the、The 和 THE 三者都應被視作同一個單詞。
試編寫程序幫助小 P 完成前兩步，計算出 ∣𝐴∩𝐵∣ 和 ∣𝐴∪𝐵∣；小 P 將親自完成最后一步的除法運算。
輸入格式：
從標準輸入讀入數據。
輸入共三行。
輸入的第一行包含兩個正整數 𝑛 和 𝑚，分別表示兩篇文章的單詞個數。
第二行包含空格分隔的 𝑛 個單詞，表示第一篇文章；
第三行包含空格分隔的 𝑚 個單詞，表示第二篇文章。
輸出格式：
輸出到標準輸出。
輸出共兩行。
第一行輸出一個整數 ∣𝐴∩𝐵∣，即有多少個不同的單詞同時出現在兩篇文章中；
第二行輸出一個整數 ∣𝐴∪𝐵∣，即兩篇文章一共包含了多少個不同的單詞。
樣例1輸入：
3 2
The tHe thE
the THE
樣例1輸出：
1
1
樣例1解釋：
𝐴=𝐵=𝐴∩𝐵=𝐴∪𝐵= {the}
樣例2輸入：
9 7
Par les soirs bleus dete jirai dans les sentiers
PICOTE PAR LES BLES FOULER LHERBE MENUE
樣例2輸出：
2
13
樣例2解釋：
𝐴=A= {bleus, dans, dete, jirai, les, par, sentiers, soirs} ∣𝐴∣=8
𝐵=B= {bles, fouler, les, lherbe, menue, par, picote} ∣𝐵∣=7
𝐴∩𝐵=A∩B= {les, par} ∣𝐴∩𝐵∣=2
樣例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樣例3輸出：
4
24
子任務：
80% 的測試數據滿足：𝑛,𝑚≤100且所有字母均為小寫；
全部的測試數據滿足：𝑛,𝑚≤104 且每個單詞最多包含 10 個字母。
解題思路：
思路一（字符串中字母大小寫轉換+哈希集合）：
1、解題步驟拆分：
① 忽略英文字母大小寫，我們可以將所有的字母轉換為小寫。
② 忽略一個集合中重復的單詞，我們可以想到哈希集合來進行降重。
③ 求并集，可以想到將兩個集合中的并入一個集合。
④ 求交集，可以想到通過查找集合A中的元素是否存在集合B中來求出。
代碼實現
代碼實現（思路一（字符串中字母大小寫轉換+哈希集合））：
#include<iostream>
#include<unordered_set> // 引入unordered_set容器，使用哈希表來存儲不重復元素
#include<algorithm> // 引入算法庫，包含transform、tolower、toupper等函數using namespace std;int main(int argc, char const *argv[]) {int n, m;cin >> n >> m; // 輸入兩個整數 n 和 m，分別表示集合A和集合B的元素個數unordered_set<string> setA, setB; // 定義兩個unordered_set，分別存儲集合A和集合B的元素string word; // 用于存儲每次輸入的單詞// 讀取n個單詞并插入集合setAfor (int i = 0; i < n; i++) {cin >> word;// 使用transform函數將單詞轉為小寫 //tolower轉小寫 。toupper轉為大寫transform(word.begin(), word.end(), word.begin(), ::tolower); // tolower將字母轉為小寫setA.insert(word); // 將小寫形式的單詞插入setA}// 讀取m個單詞并插入集合setBfor (int i = 0; i < m; i++) {cin >> word;// 使用transform函數將單詞轉為小寫transform(word.begin(), word.end(), word.begin(), ::tolower); // tolower將字母轉為小寫setB.insert(word); // 將小寫形式的單詞插入setB}unordered_set<string> intersection, unionSet; // 定義兩個unordered_set，分別存儲交集和并集// 計算集合B與集合A的交集 (也可以使用一個變量來計數)for (auto &str : setB) { // 遍歷集合B中的每個元素if (setA.count(str)) { // 如果setA中包含該元素 //如果使用setA.find()則需與setA.end()進行比較判斷有無intersection.insert(str); // 將該元素插入交集}}// 計算集合A與集合B的并集（也可以使用原來的set集合，將setB并入setA）unionSet = setA; // 將setA的所有元素先復制到unionSet中for (auto &str : setB) { // 遍歷集合B中的每個元素unionSet.insert(str); // 將集合B中的元素插入unionSet（如果元素已經存在，insert不會重復插入）}// 輸出交集的大小cout << intersection.size() << endl;// 輸出并集的大小cout << unionSet.size() << endl;return 0; // 返回0，表示程序成功結束
}
//ch = std::toupper(ch); // 將字符轉換為大寫
歡迎大家和我溝通交流(????)
)
