關于set，map以及變種
|關聯容器| set&multiset | map&multimap |無序關聯容器| Unordered set&multiset | Unordered map&multimap |
建議先了解之后再配合練習
這次練習CCF真題比較多，也比較基礎，預計耗時不用這么久。

今天的重點是 C++ STL 中兩個非常強大的關聯式容器：map和 set。它們在處理需要高效統計、去重和查找的場景時極為有用，尤其在CCF認證考試的題目中頻繁出現。

練習計劃概覽

• 總時長: 約 4 小時

• 核心目標:

  1. 掌握 std::map 的基本用法，用于建立鍵-值（key-value）映射，實現快速詞頻統計和數據聚合。

  2. 掌握 std::set 的基本用法，利用其自動去重和排序的特性，進行數據去重和有序集合操作。

  3. 理解 map 和 set 底層基于紅黑樹實現所帶來的 O(log n) 時間復雜度特性。

  4. 通過練習CCF真題，熟悉這類考點的設問方式和解題套路。

---

第一部分：map 的應用——統計與映射 (約 2 小時)

map 提供的是鍵（Key）到值（Value）的映射關系。它非常適合需要根據某個標識（如單詞、ID）來存儲和查詢對應信息（如出現次數、屬性）的場景。

題目編號	題目名稱	核心知識點	練習目標
CCF202403-1	詞頻統計	map, set	這是最經典的詞頻統計題。使用 map<int, int> 統計單詞總頻次，并可結合 set 對每篇文章的單詞去重，以統計單詞出現的文章數 1。是 map 和 set 結合使用的絕佳練習。（來自您提供的文件）
CCF202305-1	重復局面	map, vector<string>	統計每個 8x8 棋盤局面出現的次數 2。本題是練習將 vector<string> 等復雜數據結構作為 map 的鍵，來進行頻次統計的絕佳題目。（來自您提供的文件）
CCF202006-2	稀疏向量	map<int, int>	這道題是 map 應用的絕佳范例。由于向量維度很高但非零值很少（稀疏） 3，使用數組會浪費巨大空間。而用 map 只存儲非零值的下標和值，可以高效地解決空間和計算問題 4。 （CCF真題）
CCF202312-2	因子化簡	map	在對整數進行質因數分解時，使用 map<long long, int> 來存儲每個質因數及其出現的次數（指數）5，是 map 在數論問題中進行頻次統計的典型應用。（來自您提供的文件）

//33-1 (第33次第一題)
//構建兩個map來映射，也可以吧兩個合成一個map<int,vector<int>>來操作，但我覺得沒必要#include <iostream>
#include <map>
#include <vector>using namespace std;int main(){int m,n;cin >> n >> m;map<int,int> freq;map<int,int> arti;for(int i=1;i<=m;i++){freq.insert(make_pair(i,0));arti.insert(make_pair(i,0));}while(n--){int a;cin >> a;vector<bool> vis(m,false);for(int i=0;i<a;i++){int tmp;cin >> tmp;freq[tmp]++;if(!vis[tmp]){arti[tmp]++;vis[tmp] = true;}}}for(int i=1;i<=m;i++){cout << arti[i] << " " << freq[i] <<"\n";}return 0;
}``````cpp
//30-1 直接無腦把各種情況往映射里面插入就行。#include <iostream>
#include <vector>
#include <map>  
#include <string>using namespace std;int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;map<vector<string>,int> freq;for(int i=0;i<n;i++){vector<string> situ(8);for(int j=0;j<8;j++){cin >> situ[j];}if(freq.find(situ)==freq.end()){freq[situ]=1;}else{freq[situ]++;}cout << freq[situ] <<"\n";}return 0;
}

//19-2 寫兩個map，數據傳入后直接乘#include <iostream>
#include <vector>
#include <map>  
#include <string>using namespace std;int main(){int n,a,b;cin >> n >> a >> b;map<int,int> vc1;map<int,int> vc2;for(int i=0;i<a;i++){int tmp;cin >> tmp;cin >> vc1[tmp];}for(int i=0;i<b;i++){int tmp;cin >> tmp;cin >> vc2[tmp];}long long sum=0;// 遍歷第一個向量中的所有索引for(auto& p : vc1){int index = p.first;if(vc2.find(index) != vc2.end()){sum += (long long)p.second * vc2[index];}}cout << sum << "\n";return 0;
}

//素數我直接打表的，注意一個可能本身是大數的情況，所以加了一步flag#include <iostream>
#include <vector>
#include <map>  
#include <string>
#include <sstream>
#include <math.h>std::vector<int> pri={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,701,709,719,727,733,739,743,751,757,761,769,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997};
using namespace std;int main(){int n;cin >> n;while(n--){long long a;int k;map<int,int> freq;cin >> a >> k;while(a>1){bool flag = false;for(int i=0;i<pri.size()&&a>=pri[i];i++){if(a%pri[i]==0){if(freq.find(pri[i])==freq.end()){freq[pri[i]]=1;}elsefreq[pri[i]]++;a/=pri[i];flag = true;break;}}if(!flag){if(freq.find(a)==freq.end())freq[a]=1;elsefreq[a]++;break;}}long long b = 1;for(auto& p : freq){if(p.second>=k){b *= pow(p.first,p.second) ;}}cout << b << "\n";}return 0;
}

練習建議:

• CCF202403-1 (詞頻統計) 是必做題，它完美地體現了CCF對 map 基本能力的考察。請務必掌握 map[key]++ 這種簡潔的計數方式。

• 做 CCF202305-1 (重復局面) 時，關鍵在于理解C++中 map 的鍵只要是可比較的，就可以是任意復雜類型。這為你解決更多樣的問題打開了思路。

• 做 CCF202006-2 (稀疏向量) 時，需要遍歷其中一個 map，然后用 find 或 count 方法在另一個 map 中查找是否存在相同的 key（維度下標），從而計算內積。

---

第二部分：set 的應用——去重與查找 (約 1.5 小時)

set 容器存儲的元素都是唯一的，并且會自動排序。它非常適合需要去除重復元素，或者需要快速判斷某個元素是否在集合中的場景。

題目編號	題目名稱	核心知識點	練習目標
P1059	[NOIP2006 普及組] 明明的隨機數	set	最經典的去重入門題。將所有數字插入 set 容器，它會自動完成去重和排序，是理解 set 核心特性的不二之選。
CCF202403-2	相似度計算	set, string	題目核心是“去掉各自重復的單詞”并計算交集與并集 6。這是 set 數據結構的教科書式應用，用于高效地進行字符串去重和集合運算。（來自您提供的文件）
P3370	【模板】字符串哈希	set<string>	統計一堆字符串中有多少個不同的字符串。可以直接使用 std::set<string> 來自動去重并計數，是 set 用于字符串去重的模板題。
P1540	[NOIP2010 提高組] 機器翻譯	set/map, queue	模擬內存緩存。需要一個數據結構能快速判斷某單詞是否存在于內存中，set 的 find 或 count 方法非常適合這個場景。

P1059 -這個題目我在排序和二分那里用set做了一遍

//33-2 兩個點：大小寫轉換記得用引用；這里用無序容器更好，因為基于哈希的無序容器查找耗時O(1)#include <iostream>
#include <set>
#include <string>using namespace std;int main(){int a,b;cin >> a >> b;set<string> s1;set<string> s2;for(int i=0;i<a;i++){string tmp;cin >> tmp;for(char &c : tmp){c = tolower(c);}s1.insert(tmp);}for(int i=0;i<b;i++){string tmp;cin >> tmp;for(char &c : tmp){c = tolower(c);}s2.insert(tmp);}set<string> s3;for(auto& p : s1){if(s2.find(p)!=s2.end()){s3.insert(p);}}cout << s3.size() << endl << s1.size()+s2.size()-s3.size() << endl;return 0;
}

//P3370 - 題目想要你自己搞哈希，既然有現成容器直接用就行#include <iostream>
#include <set>
#include <string>using namespace std;int main(){int n;cin >> n;set<string> s;while(n--){string tmp;cin >> tmp;s.insert(tmp);}cout << s.size() << endl;return 0;
}

//P1540 - 我這里了個queue來進行內存里面數據的處理（先進先出），因為刪除set里面東西的時候只能找key，愿意的話可以用u_map然后把key順序一下，每次刪最前面就行。（我覺不如queue實在）#include <iostream>
#include <unordered_set>
#include <string>
#include <deque>using namespace std;int main(){int m,n;int rst=0;cin >> m >> n;unordered_set<int> s;deque<int> q;while(n--){int i;cin >> i;if(s.find(i)==s.end()){s.insert(i);q.push_back(i);rst++;if(q.size()>m){s.erase(q.front());q.pop_front();}}}cout << rst << endl;return 0;
}

練習建議:

• P1059 和 CCF202403-2 是必做題，它們分別代表了對數字和字符串的去重，覆蓋了 set 最核心的應用。

• 在做 CCF202403-2 (相似度計算) 時，在將兩個單詞集合（set）構建好之后，可以通過遍歷較小的集合，并使用 find 方法在較大的集合中查找，來高效地計算交集的大小。

• P1540 是一個很好的綜合題，它會讓你思考 set 只負責去重和查找，但不記錄順序，因此需要結合 queue等其他數據結構來記錄元素的進入次序。

---

目標達成自查 (約 0.5 小時)

完成以上練習后，進行復盤和總結：

1. 關于 map vs 數組:

   • 在什么情況下必須使用 map 而不能用數組？（當鍵的類型不是整數，或者鍵是整數但范圍非常大且分布稀疏時）

   • map 的 m[key]++ 操作包含了哪些步驟？（查找 key，如果不存在則插入默認值0，然后自增）

2. 關于 set vs vector+sort+unique:

   • 使用 set 去重和使用 vector 排序去重各有什么優缺點？（set 插入時自動維護，代碼簡單；vector 操作對于靜態數據一次性處理速度可能更快）

   • 如何用 set 快速判斷一個元素是否存在？（使用 s.count(element) 或 s.find(element) != s.end()，時間復雜度為 O(log n)）

3. 復雜度意識:

   • map 和 set 中一次插入、刪除、查找操作的平均時間復雜度是多少？（O(log n)）

   • 對于 10^5 級別的數據量，使用 map 或 set 的總時間復雜度大約是多少？（O(n log n)），這在絕大多數算法競賽中是可以接受的。