接下來的章節,採用 C++ 作為主要的程式語言,原因是相對於其他主流的高階語言(e.g. Python, JavaScript…),C++ 作為編譯語言有相對快的執行速度,且在某些細節操作上更加自由。不過在部分時間或空間限制較寬鬆的題目中採用 Python 解題可以提升解題速度,這部分就交給讀者自行探索。
在 C++ 中,主要有兩種教派(?),std::cin
, std::cout
派與 scanf
, printf
派
在一般情況,兩種輸出入函式可以混用,他們會同步使用同一塊緩衝區。
但這樣對於 cin/cout
的負擔很大[1],所以純用 cin/cout
的話建議在使用前加入這行:
預設中在執行 cin
之前 cout
會直接 flush (將緩衝區內容輸出到螢幕),也建議關掉這功能:
有大量的 I/O 將會拖慢時間
而 C++ 有個換行操作是 std::endl
,將會強制進行 flush,建議也用 '\n'
取代
在撰寫程式時要估算資料大小,以選擇適合的資料型別,就算是身經百戰的選手也可能因沒有小心估算範圍而得到 WA 或 RE,以下給出 C++ 中常用型別以及大約範圍:
int x
:
long long x
:
float x
: 共 6 位精確度
純整數若超過 會不精確
double x
: 共 15 位精確度
純整數若超過 會不精確
double
與 float
的精確度取決整數位數+小數位數,若同時存過大且對小數精確度要高的數時,可能會出現誤差。
對浮點數實作及精確值有興趣的話可翻閱 IEEE 754 規範
第 15 週會討論到如何解決因精度不夠而產生的問題
CODEFORCES 913A Modular Exponentiation
演算法的設計,得建立在資料結構之上,並評估時間與空間上的效率
題目給定輸入規模通常很大,2 倍、3 倍、甚至 10 倍的常數倍優化其實不是競賽時考慮的要點。
我們所設計的演算法必須根據輸入規模 而定。
意思是說在 足夠大的時候,存在正數 使得 大於
或是說 趨近無窮的成長速度不比 來得慢
假設寫的程式碼長這樣:
對應的時間估計函數就是
在 很大的時候,主要影響整個函數值的大小是平方項,這時可以說 [2]
假設輸入規模為 ,常見的複雜度有:
為不受輸入規模影響的常數
通常無特別強調,複雜度都暗指時間複雜度。但空間複雜度的估計也很重要
記憶體空間的用量在各個比賽中規範都不相同
但有些基本的考慮因素,例如 遞迴深度,使用的變數多寡,程式碼長度[3]
普遍上題目都會以秒為單位去做時間限制 (e.g. 3 秒、10 秒)
但通常我們會直接考慮輸入資料的規模與計算出來的複雜度
有個傳統(?)的範圍: 左右
這只是大約的估計範圍
假設輸入規模為 ,演算法的複雜度為
那麼需要滿足
具體一點,上面如果 ,那你就得重新設計演算法了。
資料結構 (data structure) 是種對資料的有系統的整理,
資料結構是為了令在其之上運作的演算法能更好的進行操作,或為了提昇演算法的效率,甚至是方便解釋演算法的運作(抽象化)。
每種資料結構通常是針對:插入,刪除,修改,查詢[4] 的效率及操作上的追求。
所以每個容器通常都有相似的函式能用,函式名稱或許也一樣。
STL 全名 Standard Template Library
由容器 (Containers)、迭代器 (Iterators)、演算法 (Algorithms)、函式 (Functions) 組成。
下面會陸續介紹幾個常用的 STL 裡的容器及函式
在使用前請先行測試過,以及了解其複雜度
絕大部分 STL 的東西只要涉及區間的操作,區間表示一律為左閉右開[5]
其中 std::queue
, std::stack
, std::list
先給出簡易實作,再介紹在 STL 裡的用法。
推薦的參考網站: cplusplus.com、C++ reference
假設容器 C
,已經裝了一些元素,若想遍歷 C
中的所有元素,那要如何做到呢?
有些容器是沒有 index 可以隨機存取的 (例如: std::list
),
為處理此問題,STL 為每個容器提供一個成員型別:迭代器 (Iterator)
可用"指標"的概念理解迭代器
實際上,指標算是一種迭代器
假設迭代器 it
,存取 it
所指向的內容,就用 *it
迭代器有 3 類:
++
)、遞減 (--
)++
)STL 容器有 begin()
與 end()
成員函式,它倆都會回傳個迭代器。
由於左閉右開
end()
的迭代器位置落在容器最尾端迭代器的後面
vector 跟一般在使用的陣列很像,最大的特色就是他的儲存空間是動態增減的
std::vector
vector<T> v
: v
為空的 vector,且各元素型別為 T
vector<T> v(size_type a)
: v
長度為 a
vector<T> v(size_type a, const T& b)
: v
會被 a
個 b
填滿
v.size()
: v
目前的長度
v.push_back(T a)
: 在 v
的結尾加一個 a
v.pop_back()
: 刪除 v
的最末項[6]
v.empty()
: 是否 v
為空
v[i]
: v
的第 i
項
v.clear()
: 清空 v
v.resize(size_type a)
: 將 v
的長度調至 a
v.assign(InputIterator l, InputIterator r)
: 將指標 l
到 r
的內容覆蓋至 v
v.assign(size_type n, const value_type& val)
: 覆蓋 n
個 val
至 v
字串 (string),顧名思義是很多個字它們串在一起
例如: "stringisastring",就是一堆字 's', 't', 'r', 'i', 'n', 'g', 'i', …, 'g' 串在一起。
字串可像序列一樣表示, 例如長度為 的字串 為:
字串的問題與序列問題的區別在於字串通常探討的是字元前後連續的特性。
std::string
string 的用法很像 vector<char>
但多了一些優化,以及功能、且 vector<char>
有的 string
都有
若 t
是 string
或 C style string 則:
s = t
: 會將 t
複製給 s
s += t
: 在 s
的尾端接上 t
cin >> s
: 輸入字串至 s
cout << s
: 輸出 s
getline(cin, s, char c)
: 輸入字串至 s
,直到讀到 c
。c
預設為 '\n'
s == t
: 是否 s
跟 t
相同
s.c_str()
: 回傳 s
的 C style string
挺複雜的題目
將 4 道指令拆解成兩種指令的合成,也就是 return_above
以及 move_to
return_above(a)
: 將特定 block a
上方的 blocks 全數返回到原來的位置。move_to(a, b)
: 將 block a
及其上所有 blocks 移動到 block b
所在的位置最上方。宣告 vector<int> pile[maxn];
以 pile[p]
紀錄位置 p
上的所有 blocks (從 0 開始由下而上)
學習重點:
CODEFORCES 1287A Angry Students
CODEFORCES 1301A Three Strings
CODEFORCES 1144A Diverse Strings
CODEFORCES 1243B1 Character Swap (Easy Version)
*CODEFORCES 1304B Longest Palindrome
*CODEFORCES 1243B2 Character Swap (Hard Version)
將一堆元素由"給定規則"排成一順序,稱為排序 (sort)。
例如:
5, 6, 9, 8, 2
這五個元素由小到大排為 2, 5, 6, 8, 9
a, bc, aa, ay
這四個元素由字典順序排為 a, aa, ay, bc
std::sort
STL 的 sort
裡有複雜的優化,預設將容器元素由小排至大
假設有如下資料結構:
若想依 num
對 v
做排序,需寫比較函數
比較函數是在定義"小於"運算:
或將小於運算子 (
operator<
) 重載也能達到一樣的效果
將 cmp
做為參數:
當然也可以直接把匿名函數寫進去:
順帶一提,
若把小於行為內部定義為"大於":
則排序為從大至小。
乍看之下有夠難欸
仔細觀察發現,
個切出來的 subarray 中最大的 個元素,收集起來恰好就是原 array 中前 大的元素
所以將它們加起來就能得到所有 beauty 的總和
因為要求輸出間隔的 index 位置,所以我們需要原本的 index 位置
將 idx
再排序一遍,就能穩穩輸出來了
學習重點:
std::sort
複雜度 ,大部份競賽中並不會比 壞很多for
迴圈中大於 以上的累加Kick start Round A 2019 A Training
Kick start Round F 2018 A Common Anagrams
CODEFORCES 1294B Collecting Packages
CODEFORCES 1107C Brutality
要搭公車之前,都是先排隊進入公車站,等到公車到來時,再從公車站出去搭上公車;
由此,公車站可以作為一種資料結構,人可類比為欲儲存之資料
[7]
此種資料結構稱作隊列 (Queue);擁有先進先出 (First In, First Out) 的特性。
例如在郵局要辦事,會先從機器拿號碼紙等叫號,這時候就是用隊列去儲存編號。
下面給出隊列的簡易實作程式碼:
操作多次 enqueue
與 dequeue
,會使得 front_idx
最終會碰到陣列邊界,這樣會導致能儲存的資料量變小。
觀察發現,當 front_idx
增加,相當於丟掉以前的資料,這時候就有舊的空間空出來了,該如何使用這塊舊空間呢?
直接的,讓 back_idx
碰到邊界後回去初始位置就可以了: 這種資料結構稱作環狀隊列
還有種變種隊列,叫做雙端隊列(Double ended queue),他可以從前面或後面 enqueue
或 dequeue
。
std::queue
queue<T> q
: q
為空的隊列,且各元素型別為 T
q.front()
: 第一個進入 q
的元素
q.back()
: 最後一個進入 q
的元素
q.push(T a)
: 將 a
加入 q
中 (enqueue)
q.pop()
: 將第一個進入 q
的元素移除 (dequeue)
q.empty(), q.size()
: q
當然也有這兩個函式
UVa OJ 10935 Throwing cards away I
UVa OJ 12100 Printer Queue
Zero Judge c700 壞掉的隊列(queue) (建議讀完 stack 再來練習本題)
考慮將鬆餅每次只放一片疊到盤子上,則最後放上去的鬆餅將會是最上層的鬆餅,如果要吃會依序從最上層開始拿;
由此,盤子可以作為一種資料結構,鬆餅可類比為欲儲存之資料
鬆餅(資料)的放、拿法,是種稱作堆疊 (stack) 的資料結構;有後進先出 (Last In, First Out) 特性,
下面給出堆疊的簡易實作程式碼:
相較於隊列的簡易實作版,堆疊不用擔心已用過的空間會永遠用不到
std::stack
stack<T> st
: st
為空的堆疊,且各元素型別為 T
st.top()
: 存取最後一個進入 st
的元素
st.push(T a)
: 將 a
加入 st
中
st.pop()
: 將最後一個進入 st
的元素移除
UVa OJ 514 Rails
UVa OJ 673 Parentheses Balance
UVa OJ 271 Simply Syntax
UVa OJ 11234 Expressions
玩撲克牌遊戲時,常會有將牌拿起與將牌插到某個位置的動作
支援這兩個行為的資料結構稱為"連結串列 (Linked list)"[9]
連結串列比較複雜點,需要造出兩種結構:
list[0]
不當一般資料 (.data
) 使用,它用來指向連接串列的頭在最後將 list[0]
(head pointer) 與串列尾部連接起來,是為了下面兩個函式寫法上的方便(?
當擁有這樣的結構,拔除節點和插入節點只需 :
比起 queue 和 stack,從頭刻 linked list 真的挺累的
因應題目需求,有時候還是得自己刻
std::list
list<T> ls
: ls
空的連接串列,且各元素型別為 T
insert
, erase
將回傳操作過後的迭代器位置 (最好自行實驗)
ls.insert(iterator it, T a)
: 在 it
位置前插入 a
ls.insert(iterator it, size_type n, T a)
: 在 it
位置前插入 n
個 a
ls.erase(iterator it)
: 把 it
位置上的元素移除
ls.erase(iterator l, iterator r)
: 把 位置上的元素移除
此時 it
將指向第 個位置
是還未
ls.insert(it, 3, 100)
前的位置
是因為插入了 個100
UVa OJ 11988 Broken Keyboard (a.k.a. Beiju Text)
CODEFORCES 1154E Two Teams
UVa OJ 245 Uncompress
Sprout OJ 21 陸行鳥大賽車
Sprout OJ 20 中國人排隊問題
inserter
介紹 std::set
之前,得先介紹一些集合操作
inserter 顧名思義,就是把一些東西插入到某個地方
set_union
union 就是將兩個集合取聯集
set_intersection
取交集
set_difference
取差集
集合(Set) 是非常基礎的數學結構,對於資料結構也一樣基礎
特別注意:集合中的元素不會重複
std::set
std::set
是使用紅黑樹實作的,插入、刪除、查詢都為 ,其中元素也不會重複。
且元素們在 set
容器中保持排序的(可比大小)
也就是說迭代器位置會優先從元素值小的排到大的
set<T> S
: 空的集合
S.insert(T a)
: 插入元素 a
S.erase(iterator x)
: ,移除 位置上的元素
S.erase(iterator l, iterator r)
: 把 位置上的元素移除
S.erase(T a)
: 移除元素 a
S.find(T a)
: 回傳指向元素 a
的迭代器;若 a
不存在,則回傳 S.end()
S.count(T a)
: 元素 a
是否存在
在 C++11 後,erase 會回傳最後被移除元素下個元素的迭代器
持續使用函數 ,除以 1 次 前最多只會加 9 次 ,
於是對於數字 最多只會使用 次
在這過程中若遇到已經見過的數字,表示不會再出現不曾見過的數字了
CODEFORCES 1238B Kill `Em All
CODEFORCES 1253B Silly Mistake
鍵(key)值(value)對(pair) 是非常實用的資料結構
例如想表達每個人 的身高 可以寫:
又或是表達有理數 的分子分母:
std::map
std::map
的插入、刪除或查詢為
map
的每個元素結構為 std::pair<T1, T2>
構成的 KVP
且元素們在 map
容器中保持排序的
map<T1, T2> M
: 空的 KVP 集合,鍵型態 T1
,值型態 T2
M[k] = a
: 修改鍵 k
對應的值為 a
M[k]
: 存取鍵 k
對應的值
M.insert(pair<T1, T2> P)
: 插入一個鍵值對 P
每次將 skill 為 student 以上相差 以內的 skill 都記錄下來就行
例如有 skill 、 及 的 student 存在
那麼首先記錄 :
接著
然後
所以對於 skill :
接著找出 以下相差為 的 skill 數中的最大值:
且慢!
注意到一個限制:
若把 cnt
陣列的空間開得這麼大,明顯的會 Runtime error[11]
所以把陣列改成 map<int, int>
,就能避免空間上的龐大需求
觀察題目中的例子
應該可以很自然地推得數列
原因是當起頭確定時,可得知下兩個數字是啥
確定是 ,那一定知道後面是
確定是 ,那一定知道後面是
並且若知道下兩個數字,又能再推得一個數字
的話能推得 ,因為有
依此類推,能夠把所有數字都算出來
且起頭的數字是統計所有 triple 中只出現 1 次的數字,如
第二個數字則是統計所有 triple 中只出現 2 次的數字,如
UVa OJ 11991 Easy Problem from Rujia Liu?
*CODEFORCES 1257C Dominated Subarray
**CODEFORCES 1230D Marcin and Training Camp
優先隊列 (priority queue) 是隊列 (queue) 的一個變種
std::priority_queue
每次進出的時間複雜度都為
對於數值型態的元素,數值越大優先度越大
priority_queue<T> pq
: pq
為空的優先隊列,且各元素型別為 T
pq.top()
: pq
中優先度最大的元素
pq.push(T a)
: 將 a
加入 pq
中 (enqueue)
pq.pop()
: 將pq
中優先度最大的一個元素移除 (dequeue)
對於未定義排序關係的元素(型態),要先定義小於運算子,例如:
priority_queue
也能定義比較函數,可以自行實驗
簡單的,將所有 binary string (preferences) 都產出,並把 string 對應的抱怨 (complaint) 算出
接著找出最小抱怨且不屬於 forbidden types 的 binary string 就好。
用 span
保存將產出的 binary string:
以 seed
作為基礎,再將 string 加上 "0"
或 "1"
並每次將當前的抱怨值算出後保存:
其中 one[i]
與 zero[i]
為 Shakti 的朋友們對於第 個 option 的加總 (選項只有 和 )
但光是產出所有 binary string 就足夠讓複雜度導致 TLE。
在上述過程中,若把某些 string 去除掉,就能使效率增加不少
合理的,答案只要最小抱怨值的 binary string,那在過程中移除抱怨值較大的 string 就行了:
因為共有 個 forbidden type,所以至少要保存 個 binary string
最後把 string 為 forbidden type (ban
) 的濾掉,留下抱怨值最小的就好:
ICPC 3135 Argus
UVa OJ 11997 K Smallest Sums
有時會想試試不靠儲存空間,使用大量的判定輸出,此時程式碼長度的估算也得考量 ↩︎
若 v 為空,會發生無法預期的結果 ↩︎
wikipedia/ Representation of a FIFO (first in, first out) queue ↩︎
wikipedia/ Simple representation of a stack runtime with push and pop operations ↩︎
這裡介紹的是更為泛用的 doubly linked list 而非單純的 singly linked list ↩︎
不過實驗證明,提交上 Codeforces 會拿到 Compilation error ↩︎