最後更新日期 2024 / 01 / 01

C++ 常見 STL 教學

piar

簡介

pair 是一種可以儲存兩個元素的資料結構

用途

通常用來儲存二維座標或者是陣列的 index 與 value
而且常數較小
如果用 array / vector 替代有些題目真的會被卡 TLE

語法

// 宣告一個第一個欄位為 1 第二個欄位為 5 的 pair
// 在一些 c++ 版本較舊的環境下要使用 make_pair(1, 5)
pair<int, int> pos = {1, 5};

// 取得第一個欄位的值
cout << pos.first << endl;

// 取得第二個欄位的值
cout << pos.second << endl;

// 將 pos 的第一個欄位的 1 改成 2
pos.first = 2;

// 將 pos 的第二個欄位的 5 改成 4
pos.second = 4;

比較

在比較兩個 pair 時會先比第一個元素
如果第一個元素相同才會比第二個元素

vector

簡介

跟傳統陣列差不多
不過長度是可變的
會因為加入更多元素讓 vector 變得更長

用途

不用多說了吧
就是可以像陣列一樣儲存 n 個元素

語法

// 直接宣告 vector 的方式
vector<int> v1;

// 宣告長度為 n 的 vector
vector<int> v2(n);

// 宣告長度為 n 且每個元素都是 5 的 vector
vector<int> v3(n, 5);

// 宣告一個有元素 {1, 2, 3, 4} 的 vector
vector<int> v4 = {1, 2, 3, 4}

// 宣告一個跟其他 vector 一樣的 vector (複製)
vector<int> v5(v4);

// 加入元素在尾端
v1.push_back(7);

// 從尾端移除元素
v1.pop_back();

// 存取 vector 中的某一項
cout << v4[2] << endl;

// 取得大小
cout << v2.size() << endl;

比較

從第一個元素開始比較
如果相同就繼續往後比
直到第一個不同為止

queue

簡介

像是一個排隊的隊伍
可以從一端進入
從另一端離開
也就是先進去的會先離開

用途

大部分情況用來實作一些較複雜的演算法
比如 BFS、拓撲排序等等

語法

// 宣告一個 queue
queue<int> q;

// 將元素 5 推入 queue 後端
q.push(5);

// 取得 queue 前端的元素
cout << q.front() << endl;

// 取得 queue 後端的元素
cout << q.back() << endl;

// 將隊伍前端的元素彈出(移除)
q.pop();

// 檢查 queue 是否為空
if (q.empty()) {
    cout << "empty" << endl;
}

// 取得 queue 的大小
cout << q.size() << endl;

stack

簡介

類似於一疊盤子
最後放上去的盤子會最先被取走
而你不能從中間拿走盤子
也就是說後進去的會先出去

用途

stack 常用來會處理一些匹配類問題
或者是模擬遞迴
更進階一點還有單調堆疊之類的玩法

語法

// 宣告一個 stack
stack<int> stk;

// 將元素 3 推入 stack
stk.push(3);

// 從 stack 頂端取出元素
cout << stk.top() << endl;

// 將 stack 頂端的元素彈出(移除)
stk.pop();

// 檢查 stack 是否為空
if (stk.empty()) {
    cout << "empty" << endl;
}

// 取得 stack 的大小
cout << stk.size() << endl;

set

簡介

就是集合的意思
用來儲存不重複的元素
並會按照元素的大小自動排序

用途

主要用於快速插入和查找元素

語法

// 宣告一個 set
set<int> st;

// 插入元素
st.insert(5);
st.insert(3);
st.insert(7);

// 檢查 set 是否包含某元素
if (st.find(3) != st.end()) {
    cout << "set contains 3" << endl;
} else {
    cout << "set does not contain 3" << endl;
}

// 刪除元素
st.erase(5);

// 遍歷 set 中的元素
for (int e : st) {
    cout << e << " ";
}

// 取得 set 的大小
cout << st.size() << endl;

// 取得 set 的第一項
// 因為回傳的是 iterator 所以要加 *
cout << *st.begin() << endl;

// 取得 set 的最後一項
// 由於 back 是開區間所以要 -1
cout << *--st.end() << endl;

map

簡介

語法根陣列有點像
不過可以接受整數以外的型態來當作索引值

用途

有些時候需要使用負數、非常大的數字、字串等等來當索引值
map 就會是一個很方便的工具

語法

// 宣告一個以 string 為索引,int 為值的 map
map<string, int> mp;

// 把字串對應到數字
mp["one"] = 1;
mp["two"] = 2;
mp["three"] = 3;

// 輸出 one 的值
cout << mp["one"] << endl;

// 在 map 中刪除 one
mp.erase("one");

// 遍歷 map
for (auto [key, value] : mp) {
    cout << key << ", " << value << endl;
}

// 取得 map 的大小
cout << mp.size() << endl;

priority queue

簡介

又稱為 heap
可以支援快速地插入及查詢最大最小值

用途

很常使用在一些複雜的演算法內
比如最短路徑、最小生成樹等等

語法

// 宣告一個 priority queue
priority_queue<int> pq;

// 宣告一個 priority queue 並且頂部為最小值
priority_queue<int, vector<int>, greater<int>> pq;

// 插入元素
pq.push(3);
pq.push(1);
pq.push(5);

// 取得頂端的元素(最大值)
cout << pq.top() << endl;

// 移除頂端的元素
pq.pop();

// 檢查 priority queue 是否為空
if (pq.empty()) {
    cout << "empty" << endl;
}

// 取得 priority queue 的大小
cout << pq.size() << endl;

推薦文章

題解 CSES Restaurant Customers

給你 n 位客人的進入和離開餐廳的時間 輸出最多同時有幾位客人同時在餐廳- n le 2 times 10^5把每個人加入時間和離開的時間分別看成兩個時間點 並把所有時間點加入陣列後一起排序 然後用一個變數來維護目前餐廳人數 每次遇到加入就增加 反之遇到離開就減少 維護中遇到的最大值就是答案了 時間複雜度:Oncpp using namespace std; signed main { int n; cin n; vectorpii v; for int i = 0; i n; i++ { int s, t; cin s t; v.pushback{s, true}; v.pushback{t, false}; } sortv.begin, v.end; int cur = 0; int ans = 0; for auto e : v { if e.ss == true cur++; else cur--; ans = maxcur, ans; } cout ans endl;}

CSES

題解 CSES Sum of Divisors

定義 sigmax 為 x 的所有因數之和 給予一個 n 求 sum^n{k=1}sigmak 之值以 12 為例 先看一下這張圖列出了 1 sim 12 的所有因數可以發現每兩個數字就會出現一次 2 每三次數字就會出現一次 3 觀察後可知 對於一個數字 x 它的出現次數會是 lfloor frac{n}{x} rfloor 因為每 x 個數字就會出現一個 x 的倍數 用這個做法枚舉每個數字計算就可以得到一個 On 的算法 但這樣還不夠快到足以處理這題 10^{12} 的資料量如果我們把剛剛那張圖的呈現方式改一下 上面那一橫排代表因數 1 sim 12 下面那一行排代表該因數出現的次數可以發現這張圖內有幾串連續的因數出現次數相同 因為事實上在計算這個的過程中只會出現最多 2 sqrt n 個相異數字 證明上面那張圖每個紅色圈起來代表一塊 如果我們可以塊為單位來計算就可以把時間複雜度降到 Osqrt{n} 了想像一下 如果 n 除以 x 可以剛好整除的話 令 k = lfloor frac{n}{x} rfloor 則 lfloor frac{n}{k} rfloor 必定等於 k 那如果不是剛好整除的呢? lfloor frac{12}{5} rfloor = 2 ,quadlfloor frac{12}{2} rfloor = 6 再試試看 6 lfloor frac{12}{6} rfloor = 2 ,quadlfloor frac{12}{2} rfloor = 6 觀察後發現 這裡的 6 就是最大的 x 滿足 frac{n}{x} 為 2 於是這樣我們就可以找到最後一個連續出現次數相同的因數 最後只要把每次一塊的第一個數和最後一個數用梯形公式求總和乘上共同的出現次數就可以得到答案了不過這邊要注意的是 因為答案很大所以題目要我們對 10^9 + 7 取模 但梯形公式中又會用到除法 所以我們不能直接除 需要先求出模反元素.modulo-inverse再乘進去才行cppusing namespace std;const int mod = 1e9 + 7;const int inv = 500000004; signed main { int n; cin n; int cur = 1; int ans = 0; while cur = n { int cnt = n cur; int last = n cnt; int sum = last + cur % mod last - cur + 1 % mod % mod inv % mod; ans += sum % mod cnt % mod % mod; cur = last + 1; } cout ans % mod endl;}

CSES

TOI 新手同好會心得文

有點怕遲到很早出門 結果正式開始前半小時就到師大了 不過教室已經開了 就到裡面坐著寫寫題等工作人員準備一下之後 很快就開放參與者報到了 領了名牌還有幾個師大的紀念品 因為下午團體賽要分組所以也抽了組別的籤比賽時常 2.5 小時總共有 8 題 開賽後先打開了第一題 ~~但看到一堆複雜的算式所以就先跳過了~~ 第二題感覺就是排序裸題 ~~但沒看很仔細導致看不懂題目所以也跳過了~~ 第三題是字串模擬題 我決定從這題開始下手 結果因為最近用 Mac 而且家裡 Windowns 鍵盤跟比賽的差很多的關係 打字打的超痛苦 方向鍵位置差很多而且要按 ctrl 一直按到 alt 寫到心態很崩 這種水題傳上去甚至還吃了一個 WA ~~我甚至在想為什麼我要花時間來這裡受苦受難~~ 重新看題目後發現原來完全理解錯意思了 修改一下之後總算 AC 了一題 翻開第四題 看到測資範圍到了 10^5 總算看到一題算法題了 大概花幾分鐘思考就把雙指針寫完 不過還是吃了幾次 WA 加上讀題跟 debug 大概總共花了半小時才 AC 這題第五題 很明顯的水題目 簡單陣列操作而已 大概只花了幾分鐘就寫完這題 AC 第六題 裸的 STL prorityqueue 題 寫起來也還算順手 1 發 AC接下來是第七題 ~~但看起來有點難所以先看第八題~~ 第八題是括號運算式 + 二分搜或枚舉 不過看起來實做有點麻煩 所以先回去看前面的題目好了重新讀懂第二題之後花了一點時間就 AC 了回到第一題 仔細看題目之後發現 原來似乎只是要模擬計算過程而已 不過浮點數感覺很棘手 總之還是先寫在說 結果傳上去馬上吃了一個 WA 花了一點時間 debug 之後獲得 20 分子題分數 不會有小數點精度問題的子題 qwq最剩下半小時我決定來寫最後一題目 把括號運算式弄好了 枚舉也做好了 不過一直吃 WA 比賽就這樣結束了總分:620 打的比上次還慘先上一張超讚的午餐圖片簡單來說就是比薩+飲料 然後系主任還有一個一個同學發巧克力 QQ 球 系主任人超好 然後吃完午餐就是頒獎跟摸彩時間 結果意外的拿了個人賽第二名 獲得了一副藍牙耳機 摸彩還摸到前幾大獎 可惜前三名不能拿摸彩獎品所以重抽了接著是神奇的團康小遊戲(? 他們會發給每個人一張表格 上面有很多格子 每個格子寫著不同內容 例如「我來自雲林」、「我近視不到 200 度」、「我知道 DFS」之類的 要找符合內容的人簽名 最後先連成一條、兩條、三條線的可以獲得獎品 總之我沒成功拿到獎品就是了 QAQ這次的團體賽玩的是 Same Game 簡單來說就是在盤面上找到兩個以上同色球連再一起消除得分 消除後空格會有上面的球掉下來 獲得越多分數的排名越高 不過跟一般的差別就在我們要使用程式操作這個遊戲一剛開始的想法是 有沒有可能這就是某種很酷的 dp 題目 畢竟目前狀態消除不同位置都會讓不同的球往下掉 也就會改變未來的狀態進而影響結果 不過後來想了一下沒什麼頭緒 但看到了第一步可以花 20 秒計算 於是我就想說 不如來試試看 Minimax Algorithm 吧 以前做遊戲的電腦 AI 時用過 想說感覺應該可以用在這邊 其實簡單來說就是暴力枚舉 k 步後的所有狀態在選擇最佳的走而已 花了快一個小時寫完後 結果才跑兩層記憶體就炸了 qwq 嗯 預測一兩步跟沒預測一樣 所以只好果斷放棄這個做法想起剛剛在講解規則時 有提到一些策略 於是我們就先把那些能做的都做出來 主要就是兩個「先固定消一個顏色,消完再消下一個」跟「先把連通塊小的顏色消掉」 於是我們就拿了第三名 ???帶走了一個安妮亞滑鼠墊 : D整體來說還蠻好玩的 午餐很讚而且也帶了不少戰利品 還認識了一些人 ~~準確來說是只認識了一個人 TAT~~

Journal