演算法攻略從零到一（cpp版）演算法攻略從零到一（cpp版）
1 前言
雖然C++是向物件語，但是演算法題的基本思維方式是
面向過程式
，也就是針對演算法題我們是不需要掌握面向物件部分（繼承、封裝、多型）。只需要掌握刷演算法的時候需要到的部分（
基本輸輸出、STL標準模板庫、string字串等
）。
使用C++刷題有幾大好處：
方便的輸入輸出；C++的
cout
、
cin
不再像C語言裡面的輸入輸出
scanf
、
printf
那樣需要自己寫明變數的型別，比如
scanf（“%d”， &n）；
printf（“%d”， n）；
，直接
cin >> n；
cout << n
；
更強大的字串處理；C++的
string
字串類提供了強大的字串處理功能，不再像C語言裡面的字元陣列，處理起來比較繁瑣；
STL
模板庫；
STL
的動態陣列
vector
、集合
set
、對映
map
、棧
stack
、佇列
queue
、位運算
bitset
，以及演算法庫
#include
的
sort
排序演算法函式模板等等，都極大提高了我們做題的效率；
整理自網路，非商業用途，侵權聯絡刪除。
2 演算法基礎之C++
2。1 輸入輸出
leetcode平臺是不需要我們自己寫資料輸入的
，只需要在下圖的紅色文字框中寫自己的解題程式碼就行。
然而在其他的OJ平臺上刷題，是需要自己
需要自己編寫輸入輸出。
然而在其他的OJ平臺上刷題，是需要自己
然後在網頁編輯框填寫自己的程式碼提交評測。
2。1。1 整數輸入問題
最簡單的輸入
//最簡單的輸入，輸入單行
Sample Input 1 2
Sample Output 3
#include
using
namespace
std
；
int
main
（）
{
int
a
，
b
；
cin
>>
a
>>
b
；
cout
<<
a
+
b
<<
endl
；
//對其他題目，換成要求的複雜處理與輸出
return
0
；
}
輸入多行數時，直到讀至輸入檔案末尾（
EOF
）為止
輸入多行數時，直到讀至輸入檔案末尾（EOF）為止
說明1：當讀到輸入結束時，cin >> a >> b返回 0，迴圈也結束。
說明2：在除錯程式時，鍵盤輸入的資料，用CTRL-Z（即按住CTRL鍵不放，再按下Z）組合作為輸入結束，此謂鍵盤輸入裝置的“檔案末尾”。
重點掌握
Sample Input
1 5
10 20
400 516
Sample Output
6
30
916
#include
using
namespace
std
；
int
main
（）
{
int
a
，
b
；
while
（
cin
>>
a
>>
b
）
//當題目輸入行數不確定時使用此方法
{
cout
<<
a
+
b
<<
endl
；
}
return
0
；
}
多組由兩個整數（a和b）構成的輸入，a和b之間用空格隔開，每組輸入單獨佔一行。
多組由兩個整數（a和b）構成的輸入，a和b之間用空格隔開，每組輸入單獨佔一行。
當輸入為 0 0 時，輸入結束。
Sample Input
1 5
10 20
0 0
Sample Output
6
30
#include
using
namespace
std
；
int
main
（）
{
int
a
，
b
；
while
（
cin
>>
a
>>
b
&&
（
a
||
b
））
{
cout
<<
a
+
b
<<
endl
；
}
return
0
；
}
第一行是資料的組數N，從第二行是N組由兩個整數（a和b）構成的輸入，a和b之間用空格隔開，每組輸入單獨佔一行
第一行是資料的組數N，
從第二行是N組由兩個整數（a和b）構成的輸入，a和b之間用空格隔開，每組輸入單獨佔一行
重點掌握
Sample Input
2
1 5
10 20
Sample Output
6
30
#include
using
namespace
std
；
int
main
（） {
int
a
，
b
，
n
；
cin
>>
n
；
for
（
int
i
=
0
；
i
<
n
；
i
++
）
{
cin
>>
a
>>
b
；
//cin以空格或者回車作為輸入輸出分隔符
cout
<<
a
+
b
<<
endl
；
}
return
0
；
}
利用檔案重定向提高除錯效率
#include
#include
using
namespace
std
；
int
main
（）
{
freopen
（
“input。txt”
，
“r”
，
stdin
）；
// 將輸入重定向到檔案 input。txt （注意檔案路徑）
int
a
，
b
；
cin
>>
a
>>
b
；
cout
<<
a
+
b
<<
endl
；
return
0
；
}
// 在執行程式前，將本該由鍵盤輸入的資料，寫到檔案 input。txt 中。而在執行程式時，資料將不再需要人去輸入
2。1。2
讀取和解析標點字元（如逗號）分隔資料
讀取以逗號間隔的數字到陣列中
處理輸入問題：讀取以逗號間隔的數字到陣列中
例：
輸入：1，12，123
陣列a：a［0］ = 1，a［1］ = 12， a［2］ = 123
#include
#include
#include
#include
using
namespace
std
；
int
main
（）
{
vector
<
int
>
a
；
string
s
；
cin
>>
s
；
//讀取輸入字串到s
stringstream
input
（
s
）；
//將字串s轉化為流
string
numstr
；
while
（
getline
（
input
，
numstr
，
‘，’
））
//按逗號分隔為字串（ getline每次讀一個 ）
{
a
。
push_back
（
stoi
（
numstr
））；
}
return
0
；
}
思路：使用
getline
和
stringstream
以 ‘，’ 為分隔符來切分資料 ，然後使用標準庫
string
的數值轉換函式例如字串轉整形
stoi
進行解析。注意： 當資料以空格分隔時，可以直接用
cin
來讀入！
2。2 String類
string
類，使得字串的定義、拼接、輸出、處理都更加簡單。不過
string
只能
cin
和
cout
處理，法
scanf
和
printf
處理：
string
s
=
“hello world”
；
// 賦值字串
string
s2
=
s
；
string
s3
=
s
+
s2
；
// 字串拼接直接+號就可以
string
s4
；
cin
>>
s4
；
// 讀字串
cout
<<
s
；
// 輸出字串
cin
讀字串的時候，是以空格為分隔符的，如果想要讀整的字串，就需要
getline
。
此外
string
的長度可以用
string s； s。length（）； s。size（）
獲取，這兩個獲取長度的函式功能是一樣的。與C語言的
char ［］
還要考慮尾部的
\0
字元，
string
裡面是多少字元就是多少，當然也包括
‘’
字元。
string
s
；
// 定義個空字串s
getline
（
cin
，
s
）；
// 讀取的字串，包括空格
cout
<<
s
。
length
（）；
// 輸出字串s的度
string
中還有個很常的函式叫做
substr
，作是擷取某個字串中的串，法有兩種形式：
string s2 = s。substr（4）； // 表示從下標4開始直到結束string s3 = s。substr（5， 3）； // 表示從下標5開始，3個字元
2。3 STL
2。3。1 STL之動態陣列vector（量）
之前C語
int arr［］
定義陣列，它的缺點是陣列的度不能隨所欲的改變。而
vector
它能夠在運階段設定陣列的度、在末尾增加新的資料、在中間插新的值、度任意被改變。它在頭件
vector
，也在名稱空間
std
，所以使的時候要引頭件
#include
和
using namespace std
；
vector
、
stack
、
queue
、
map
、
set
這些在C++中都叫做容器，這些容器的都可以
。size（）
獲取到，就像
string s
的度
s。length（）
獲取樣。只是對於
string
字串我們一般是用
。length（）
，而對於容器類我們一般用
。size（）
。
#include
vector
可以開始不定義，之後
resize
法分配，也可以開始就定義，之後還可以對它插刪除動態改變它的。且不管在
main
函式還是在全域性中定義，它都能夠直接將所有的值初始化為0（不顯式地寫出來，預設就是所有的元素為0）。
vector
除了可以訪問官網檢視
vector
的所有功能，我們下面列舉一些常見的方法。
#include
容器
vector
、
set
、
map
這些遍歷的時候都是使迭代器訪問的，
c。begin（）
是個指標，指向容器的第個元素，
c。end（）
指向容器的最後個元素的後個位置，所以迭代器指標
it
的
for
迴圈判斷條件是
it ！= c。end（）
。
2。3。2 STL之集合set的使用
set
是集合，個
set
的各元素是各不相同的，且
set
會按照元素進從到排序，以下是
set
的常法：
#include
2。3。3 STL之對映map的使用
map
是鍵值對，如個名對應個學號，就可以定義個字串
string
型別的名為“鍵”，學號
int
型別為“值”，如
map
； 當然鍵、值也可以是其它變數型別。
map
會動將所有的鍵值對按照鍵從到排序，
map
使時的頭件
#include
以下是
map
中常的法：
#include
2。3。4 STL之棧的使用
棧
stack
在頭件
#include
中，是資料結構的棧。以下是常法：
#include
2。3。5 STL之佇列queue的使用
佇列
queue
在頭件
#include
中，是資料結構的佇列。以下是常法：
#include
2。3。6 STL之
unordered_map
和
unordered_set
的使用
unordered_map
在頭件
#include
中，
unordered_set
在頭件
#include
中。
unordered_map
和
map
（或者
unordered_set
和
set
）的區別是，
map
會按照鍵值對的鍵
key
進排序（
set
會按照集合中的元素進排序，從到順序），
unordered_map
（或者
unordered_set
）省去了這個排序的過程，如果偶爾刷題時候
map
或者
set
超時了，可以考慮
unordered_map
（或者
unordered_set
）縮短程式碼運時間、提程式碼效率。於法和
map
、
set
是樣的。
2。3。7
位運算
bitset
bitset
來處理進位制位常便。頭件是
#include
，
bitset
可能在PAT、藍橋OJ中不常，但是在LeetCode OJ中經常到。且知道
bitset
能夠簡化些操作，可能些複雜的問題能夠直接
bitset
就很輕易地解決。以下是些常法：
#include
2。3。8 演算法庫之sort函式
sort
函式在頭件
#include
，主要是對個數組進排序（
int arr［］
陣列或者
vector
陣列都），
vector
是容器，要
v。begin（）
和
v。end（）
表示頭尾；
int arr［］
arr
表示陣列的地址，
arr+n
表示尾部。
#include
注意：
sort
函式的
cmp
必須按照規定來寫，即必須只是 > 或者 < ，如：
return a > b
； 或者
return a < b
； 不能是 <= 或者
>
= ，（實際上等於號加了也是毫意義，
sort
是不穩定的排序），否則可能會出現段錯誤。
2。3。9 演算法庫之sort定義cmp函式
sort
預設是從到排列的，也可以指定第三個引數
cmp
函式，然後定義個
cmp
函式指定排序規則。
cmp
最好的還是在結構體中，尤其是很多排序的題。如個學結構體
stu
有學號和成績兩個變數，要求如果成績不同就按照成績從到排列，如果成績相同就按照學號從到排列，那麼就可以寫個
cmp
陣列實現這個看上去有點複雜的排序過程：
#include
2。4 cctype標頭檔案裡的判斷函式
#include
本質上來源於C語標準函式庫中的頭件
#include
，其實並不屬於C++新特性的範疇，但是刷題時會經常碰到。
比如下面的程式碼就是判斷一個字元是否是字母
#include
不僅僅能判斷字，還能判斷數字、寫字、寫字等，總的來說如下：
isalpha
字（包括寫、寫）
islower
（寫字）
isupper
（寫字）
isalnum
（字寫寫+數字）
isblank
（space和
\t
）
isspace
（ space 、
\t
、
\r
、
\n
）
此外還有兩個常用函式，
tolower
和
toupper
，作是將某個字元轉為寫或者寫，這樣就不像原來那樣動判斷字元
c
是否是寫，如果是寫字元就
c = c + 32
； 的法將
c
轉為寫字元。
char c = ‘A’；char t = tolower（c）； // 將c字元轉化為寫字元賦值給t，如果c本身就是寫字元也不變cout << t； // 此處t為‘a’
2。5 演算法刷題常用到的c++11特性
2。5。1 auto宣告
auto
是C++11的新特性，可以讓編譯器根據初始值型別直接推斷變數的型別。如這樣：
auto x = 100； // x是int變數auto y = 1。5； // y是double變數
在STL中使迭代器的時候，
auto
可以代替串的迭代器型別宣告
// 本來set的迭代器遍歷要這樣寫：for（set
2。5。2 for in range 迴圈
除了像C語的
for
語句
for （i = 0； i < arr。size（）； i++）
這樣，C++11標準還為C++添加了種新的for迴圈式，叫做基於範圍（range-based）的
for
迴圈，這在遍歷陣列中的每個元素時使會較簡便。如想要輸出陣列
arr
中的每個值，可以使如下的式輸出：
int arr［4］ = {0， 1， 2， 3}；for （int i ： arr） cout << i << endl； // 輸出陣列中的每個元素的值，每個元素佔據
i
變數從陣列的第個元素開始，不斷執迴圈，
i
依次表示陣列中的每個元素。注意，使
int i
的式定義時，該語句只能來輸出陣列中元素的值，不能修改陣列中的元素，如果想要修改，必須使
int &i
這種定義引變數的式。如想給陣列中的每個元素都乘以2，可以使如下式：
int arr［4］ = {0， 1， 2， 3}；for （int &i ： arr） // i為引變數 i = i * 2； // 將陣列中的每個元素都乘以2，arr［4］的內容變為了{0， 2， 4， 6}
這種基於範圍的
for
迴圈適於各種型別的陣列，將上述兩段程式碼中的
int
改成其他變數型別如
double
、
char
都是可以的。另外，這種
for
迴圈式不僅可以適於陣列，還適於各種STL容器，如
vector
、
set
等。加上上節所講的C++11很好的
auto
宣告，將
int
、
double
等變數型別替換成
auto
，起來就更便。
// v是個int型別的vector容器for （auto i ： v） cout << i << “ ”；// 上的寫法等價於for （int i = 0； i < v。size（）； i++） cout << v［i］ << “ ”；
2。5。3
to_string
to_string
的頭件是
#include
，
to_string
最常的就是把個
int
型變數或者個數字轉化為
string
型別的變數，當然也可以轉
double
、
float
等型別的變數，這在很多字串處理的題中很有處，以下是示例程式碼
#include
2。5。4 stoi、stod
使
stoi
、
stod
可以將字串
string
轉化為對應的
int
型、
double
型變數，這在字串處理的很多問題中很有幫助。以下是示例程式碼和法輸的處理法：
#include
不僅有
stoi
和
stod
兩種，相應的還有：
stof
（string to flfloat）
stold
（string to long double）
stol
（string to long）
stoll
（string to long long）
stoul
（string to unsigned long）
stoull
（string to unsigned long long）
2。6 常見錯誤型別
平常刷題提交評測遇到錯誤時常見型別如下。
3 演算法基礎之常見模板
3。1 基礎演算法
快速排序
void quick_sort（int q［］， int l， int r）{ if （l >= r） return； int i = l - 1， j = r + 1， x = q［l + r >> 1］； while （i < j） { do i ++ ； while （q［i］ < x）； do j —— ； while （q［j］ > x）； if （i < j） swap（q［i］， q［j］）； } quick_sort（q， l， j）， quick_sort（q， j + 1， r）；}
歸併排序
void merge_sort（int q［］， int l， int r）{ if （l >= r） return； int mid = l + r >> 1； merge_sort（q， l， mid）； merge_sort（q， mid + 1， r）； int k = 0， i = l， j = mid + 1； while （i <= mid && j <= r） if （q［i］ <= q［j］） tmp［k ++ ］ = q［i ++ ］； else tmp［k ++ ］ = q［j ++ ］； while （i <= mid） tmp［k ++ ］ = q［i ++ ］； while （j <= r） tmp［k ++ ］ = q［j ++ ］； for （i = l， j = 0； i <= r； i ++， j ++ ） q［i］ = tmp［j］；}
整數二分
bool check（int x） {/* 。。。 */} // 檢查x是否滿足某種性質// 區間［l， r］被劃分成［l， mid］和［mid + 1， r］時使用：int bsearch_1（int l， int r）{ while （l < r） { int mid = l + r >> 1； if （check（mid）） r = mid； // check（）判斷mid是否滿足性質 else l = mid + 1； } return l；}// 區間［l， r］被劃分成［l， mid - 1］和［mid， r］時使用：int bsearch_2（int l， int r）{ while （l < r） { int mid = l + r + 1 >> 1； if （check（mid）） l = mid； else r = mid - 1； } return l；}
浮點數二分
bool check（double x） {/* 。。。 */} // 檢查x是否滿足某種性質double bsearch_3（double l， double r）{ const double eps = 1e-6； // eps 表示精度，取決於題目對精度的要求 while （r - l > eps） { double mid = （l + r） / 2； if （check（mid）） r = mid； else l = mid； } return l；}
高精度加法
// C = A + B， A >= 0， B >= 0vector
高精度減法
// C = A - B， 滿足A >= B， A >= 0， B >= 0vector
高精度乘低精度
// C = A * b， A >= 0， b >= 0vector
高精度除以低精度
// A / b = C 。。。 r， A >= 0， b > 0vector
一維字首和
S［i］ = a［1］ + a［2］ + 。。。 a［i］a［l］ + 。。。 + a［r］ = S［r］ - S［l - 1］
二維字首和
S［i， j］ = 第i行j列格子左上部分所有元素的和以（x1， y1）為左上角，（x2， y2）為右下角的子矩陣的和為：S［x2， y2］ - S［x1 - 1， y2］ - S［x2， y1 - 1］ + S［x1 - 1， y1 - 1］
一維差分
給以（x1， y1）為左上角，（x2， y2）為右下角的子矩陣中的所有元素加上c：S［x1， y1］ += c， S［x2 + 1， y1］ -= c， S［x1， y2 + 1］ -= c， S［x2 + 1， y2 + 1］ += c
位運算
求n的第k位數字： n >> k & 1返回n的最後一位1：lowbit（n） = n & -n
雙指標演算法
for （int i = 0， j = 0； i < n； i ++ ）{ while （j < i && check（i， j）） j ++ ； // 具體問題的邏輯}常見問題分類： （1） 對於一個序列，用兩個指標維護一段區間 （2） 對於兩個序列，維護某種次序，比如歸併排序中合併兩個有序序列的操作
離散化
vector
區間合併
// 將所有存在交集的區間合併void merge（vector
3。2 常見資料結構
單鏈表
// head儲存連結串列頭，e［］儲存節點的值，ne［］儲存節點的next指標，idx表示當前用到了哪個節點int head， e［N］， ne［N］， idx；// 初始化void init（）{ head = -1； idx = 0；}// 在連結串列頭插入一個數avoid insert（int a）{ e［idx］ = a， ne［idx］ = head， head = idx ++ ；}// 將頭結點刪除，需要保證頭結點存在void remove（）{ head = ne［head］；}
雙鏈表
// e［］表示節點的值，l［］表示節點的左指標，r［］表示節點的右指標，idx表示當前用到了哪個節點int e［N］， l［N］， r［N］， idx；// 初始化void init（）{ //0是左端點，1是右端點 r［0］ = 1， l［1］ = 0； idx = 2；}// 在節點a的右邊插入一個數xvoid insert（int a， int x）{ e［idx］ = x； l［idx］ = a， r［idx］ = r［a］； l［r［a］］ = idx， r［a］ = idx ++ ；}// 刪除節點avoid remove（int a）{ l［r［a］］ = l［a］； r［l［a］］ = r［a］；}
棧
// tt表示棧頂int stk［N］， tt = 0；// 向棧頂插入一個數stk［ ++ tt］ = x；// 從棧頂彈出一個數tt —— ；// 棧頂的值stk［tt］；// 判斷棧是否為空if （tt > 0）{}
佇列
普通佇列
// hh 表示隊頭，tt表示隊尾int q［N］， hh = 0， tt = -1；// 向隊尾插入一個數q［ ++ tt］ = x；// 從隊頭彈出一個數hh ++ ；// 隊頭的值q［hh］；// 判斷佇列是否為空if （hh <= tt）{}
迴圈佇列
// hh 表示隊頭，tt表示隊尾的後一個位置int q［N］， hh = 0， tt = 0；// 向隊尾插入一個數q［tt ++ ］ = x；if （tt == N） tt = 0；// 從隊頭彈出一個數hh ++ ；if （hh == N） hh = 0；// 隊頭的值q［hh］；// 判斷佇列是否為空if （hh ！= tt）{}
單調棧
常見模型：找出每個數左邊離它最近的比它大/小的數int tt = 0；for （int i = 1； i <= n； i ++ ）{ while （tt && check（stk［tt］， i）） tt —— ； stk［ ++ tt］ = i；}
單調佇列
常見模型：找出滑動視窗中的最大值/最小值int hh = 0， tt = -1；for （int i = 0； i < n； i ++ ）{ while （hh <= tt && check_out（q［hh］）） hh ++ ； // 判斷隊頭是否滑出視窗 while （hh <= tt && check（q［tt］， i）） tt —— ； q［ ++ tt］ = i；}
KMP
// s［］是長文字，p［］是模式串，n是s的長度，m是p的長度求模式串的Next陣列：for （int i = 2， j = 0； i <= m； i ++ ）{ while （j && p［i］ ！= p［j + 1］） j = ne［j］； if （p［i］ == p［j + 1］） j ++ ； ne［i］ = j；}// 匹配for （int i = 1， j = 0； i <= n； i ++ ）{ while （j && s［i］ ！= p［j + 1］） j = ne［j］； if （s［i］ == p［j + 1］） j ++ ； if （j == m） { j = ne［j］； // 匹配成功後的邏輯 }}
Trie樹
int son［N］［26］， cnt［N］， idx；// 0號點既是根節點，又是空節點// son［］［］儲存樹中每個節點的子節點// cnt［］儲存以每個節點結尾的單詞數量// 插入一個字串void insert（char *str）{ int p = 0； for （int i = 0； str［i］； i ++ ） { int u = str［i］ - ‘a’； if （！son［p］［u］） son［p］［u］ = ++ idx； p = son［p］［u］； } cnt［p］ ++ ；}// 查詢字串出現的次數int query（char *str）{ int p = 0； for （int i = 0； str［i］； i ++ ） { int u = str［i］ - ‘a’； if （！son［p］［u］） return 0； p = son［p］［u］； } return cnt［p］；}
並查集
（1）樸素並查集： int p［N］； //儲存每個點的祖宗節點 // 返回x的祖宗節點 int find（int x） { if （p［x］ ！= x） p［x］ = find（p［x］）； return p［x］； } // 初始化，假定節點編號是1~n for （int i = 1； i <= n； i ++ ） p［i］ = i； // 合併a和b所在的兩個集合： p［find（a）］ = find（b）；（2）維護size的並查集： int p［N］， size［N］； //p［］儲存每個點的祖宗節點， size［］只有祖宗節點的有意義，表示祖宗節點所在集合中的點的數量 // 返回x的祖宗節點 int find（int x） { if （p［x］ ！= x） p［x］ = find（p［x］）； return p［x］； } // 初始化，假定節點編號是1~n for （int i = 1； i <= n； i ++ ） { p［i］ = i； size［i］ = 1； } // 合併a和b所在的兩個集合： size［find（b）］ += size［find（a）］； p［find（a）］ = find（b）；（3）維護到祖宗節點距離的並查集： int p［N］， d［N］； //p［］儲存每個點的祖宗節點， d［x］儲存x到p［x］的距離 // 返回x的祖宗節點 int find（int x） { if （p［x］ ！= x） { int u = find（p［x］）； d［x］ += d［p［x］］； p［x］ = u； } return p［x］； } // 初始化，假定節點編號是1~n for （int i = 1； i <= n； i ++ ） { p［i］ = i； d［i］ = 0； } // 合併a和b所在的兩個集合： p［find（a）］ = find（b）； d［find（a）］ = distance； // 根據具體問題，初始化find（a）的偏移量
堆
// h［N］儲存堆中的值， h［1］是堆頂，x的左兒子是2x， 右兒子是2x + 1// ph［k］儲存第k個插入的點在堆中的位置// hp［k］儲存堆中下標是k的點是第幾個插入的int h［N］， ph［N］， hp［N］， size；// 交換兩個點，及其對映關係void heap_swap（int a， int b）{ swap（ph［hp［a］］，ph［hp［b］］）； swap（hp［a］， hp［b］）； swap（h［a］， h［b］）；}void down（int u）{ int t = u； if （u * 2 <= size && h［u * 2］ < h［t］） t = u * 2； if （u * 2 + 1 <= size && h［u * 2 + 1］ < h［t］） t = u * 2 + 1； if （u ！= t） { heap_swap（u， t）； down（t）； }}void up（int u）{ while （u / 2 && h［u］ < h［u / 2］） { heap_swap（u， u / 2）； u >>= 1； }}// O（n）建堆for （int i = n / 2； i； i —— ） down（i）；
一般雜湊
（1） 拉鍊法 int h［N］， e［N］， ne［N］， idx； // 向雜湊表中插入一個數 void insert（int x） { int k = （x % N + N） % N； e［idx］ = x； ne［idx］ = h［k］； h［k］ = idx ++ ； } // 在雜湊表中查詢某個數是否存在 bool find（int x） { int k = （x % N + N） % N； for （int i = h［k］； i ！= -1； i = ne［i］） if （e［i］ == x） return true； return false； }（2） 開放定址法 int h［N］； // 如果x在雜湊表中，返回x的下標；如果x不在雜湊表中，返回x應該插入的位置 int find（int x） { int t = （x % N + N） % N； while （h［t］ ！= null && h［t］ ！= x） { t ++ ； if （t == N） t = 0； } return t； }
字串雜湊
核心思想：將字串看成P進位制數，P的經驗值是131或13331，取這兩個值的衝突機率低小技巧：取模的數用2^64，這樣直接用unsigned long long儲存，溢位的結果就是取模的結果typedef unsigned long long ULL；ULL h［N］， p［N］； // h［k］儲存字串前k個字母的雜湊值， p［k］儲存 P^k mod 2^64// 初始化p［0］ = 1；for （int i = 1； i <= n； i ++ ）{ h［i］ = h［i - 1］ * P + str［i］； p［i］ = p［i - 1］ * P；}// 計算子串 str［l ~ r］ 的雜湊值ULL get（int l， int r）{ return h［r］ - h［l - 1］ * p［r - l + 1］；}
STL簡介
vector， 變長陣列，倍增的思想 size（） 返回元素個數 empty（） 返回是否為空 clear（） 清空 front（）/back（） push_back（）/pop_back（） begin（）/end（） ［］ 支援比較運算，按字典序pair
3。3 搜尋與圖論
樹與圖的儲存
樹是一種特殊的圖，與圖的儲存方式相同。
對於無向圖中的邊ab，儲存兩條有向邊
a->b， b->a
。
因此我們可以只考慮有向圖的儲存。
（1） 鄰接矩陣：
g［a］［b］
儲存邊
a->b
（2） 鄰接表：
// 對於每個點k，開一個單鏈表，儲存k所有可以走到的點。h［k］儲存這個單鏈表的頭結點int h［N］， e［N］， ne［N］， idx；// 新增一條邊a->bvoid add（int a， int b）{ e［idx］ = b， ne［idx］ = h［a］， h［a］ = idx ++ ；}// 初始化idx = 0；memset（h， -1， sizeof h）；
樹與圖的遍歷
時間複雜度
O（n+m）O（n+m）
，
n
表示點數，
m
表示邊數
（1） 深度優先遍歷
int dfs（int u）{ st［u］ = true； // st［u］ 表示點u已經被遍歷過 for （int i = h［u］； i ！= -1； i = ne［i］） { int j = e［i］； if （！st［j］） dfs（j）； }}
（2） 寬度優先遍歷
queue
拓撲排序
時間複雜度
O（n+m）O（n+m）
，
n
表示點數，
m
表示邊數
bool topsort（）{ int hh = 0， tt = -1； // d［i］ 儲存點i的入度 for （int i = 1； i <= n； i ++ ） if （！d［i］） q［ ++ tt］ = i； while （hh <= tt） { int t = q［hh ++ ］； for （int i = h［t］； i ！= -1； i = ne［i］） { int j = e［i］； if （—— d［j］ == 0） q［ ++ tt］ = j； } } // 如果所有點都入隊了，說明存在拓撲序列；否則不存在拓撲序列。 return tt == n - 1；}
樸素dijkstra演算法
時間複雜度
O（n^2+m）
，
n
表示點數，
m
表示邊數
int g［N］［N］； // 儲存每條邊int dist［N］； // 儲存1號點到每個點的最短距離bool st［N］； // 儲存每個點的最短路是否已經確定// 求1號點到n號點的最短路，如果不存在則返回-1int dijkstra（）{ memset（dist， 0x3f， sizeof dist）； dist［1］ = 0； for （int i = 0； i < n - 1； i ++ ） { int t = -1； // 在還未確定最短路的點中，尋找距離最小的點 for （int j = 1； j <= n； j ++ ） if （！st［j］ && （t == -1 || dist［t］ > dist［j］）） t = j； // 用t更新其他點的距離 for （int j = 1； j <= n； j ++ ） dist［j］ = min（dist［j］， dist［t］ + g［t］［j］）； st［t］ = true； } if （dist［n］ == 0x3f3f3f3f） return -1； return dist［n］；}
堆最佳化版dijkstra
時間複雜度
O（m\log n）
，
n
表示點數，
m
表示邊數
typedef pair
Bellman-Ford演算法
時間複雜度
O（mn）
，
n
表示點數，
m
表示邊數
int n， m； // n表示點數，m表示邊數int dist［N］； // dist［x］儲存1到x的最短路距離struct Edge // 邊，a表示出點，b表示入點，w表示邊的權重{ int a， b， w；}edges［M］；// 求1到n的最短路距離，如果無法從1走到n，則返回-1。int bellman_ford（）{ memset（dist， 0x3f， sizeof dist）； dist［1］ = 0； // 如果第n次迭代仍然會鬆弛三角不等式，就說明存在一條長度是n+1的最短路徑，由抽屜原理，路徑中至少存在兩個相同的點，說明圖中存在負權迴路。 for （int i = 0； i < n； i ++ ） { for （int j = 0； j < m； j ++ ） { int a = edges［j］。a， b = edges［j］。b， w = edges［j］。w； if （dist［b］ > dist［a］ + w） dist［b］ = dist［a］ + w； } } if （dist［n］ > 0x3f3f3f3f / 2） return -1； return dist［n］；}
spfa 演算法（佇列最佳化的Bellman-Ford演算法）
時間複雜度 平均情況下
O（m）O（m）
，最壞情況下
O（nm）
，
n
表示點數，
m
表示邊數
int n； // 總點數int h［N］， w［N］， e［N］， ne［N］， idx； // 鄰接表儲存所有邊int dist［N］； // 儲存每個點到1號點的最短距離bool st［N］； // 儲存每個點是否在佇列中// 求1號點到n號點的最短路距離，如果從1號點無法走到n號點則返回-1int spfa（）{ memset（dist， 0x3f， sizeof dist）； dist［1］ = 0； queue
spfa判斷圖中是否存在負環
時間複雜度
O（mn）
，
n
表示點數，
m
表示邊數
int n； // 總點數int h［N］， w［N］， e［N］， ne［N］， idx； // 鄰接表儲存所有邊int dist［N］， cnt［N］； // dist［x］儲存1號點到x的最短距離，cnt［x］儲存1到x的最短路中經過的點數bool st［N］； // 儲存每個點是否在佇列中// 如果存在負環，則返回true，否則返回false。bool spfa（）{ // 不需要初始化dist陣列 // 原理：如果某條最短路徑上有n個點（除了自己），那麼加上自己之後一共有n+1個點，由抽屜原理一定有兩個點相同，所以存在環。 queue
floyd演算法
時間複雜度是
O（n^3）
，
n
表示點數
初始化： for （int i = 1； i <= n； i ++ ） for （int j = 1； j <= n； j ++ ） if （i == j） d［i］［j］ = 0； else d［i］［j］ = INF；// 演算法結束後，d［a］［b］表示a到b的最短距離void floyd（）{ for （int k = 1； k <= n； k ++ ） for （int i = 1； i <= n； i ++ ） for （int j = 1； j <= n； j ++ ） d［i］［j］ = min（d［i］［j］， d［i］［k］ + d［k］［j］）；}
樸素版prim演算法
時間複雜度是
O（n2+m）
，
n
表示點數，
m
表示邊數
int n； // n表示點數int g［N］［N］； // 鄰接矩陣，儲存所有邊int dist［N］； // 儲存其他點到當前最小生成樹的距離bool st［N］； // 儲存每個點是否已經在生成樹中// 如果圖不連通，則返回INF（值是0x3f3f3f3f）， 否則返回最小生成樹的樹邊權重之和int prim（）{ memset（dist， 0x3f， sizeof dist）； int res = 0； for （int i = 0； i < n； i ++ ） { int t = -1； for （int j = 1； j <= n； j ++ ） if （！st［j］ && （t == -1 || dist［t］ > dist［j］）） t = j； if （i && dist［t］ == INF） return INF； if （i） res += dist［t］； st［t］ = true； for （int j = 1； j <= n； j ++ ） dist［j］ = min（dist［j］， g［t］［j］）； } return res；}
Kruskal演算法
時間複雜度是
O（m\log m）
，
n
表示點數，
m
表示邊數
int n， m； // n是點數，m是邊數int p［N］； // 並查集的父節點陣列struct Edge // 儲存邊{ int a， b， w； bool operator< （const Edge &W）const { return w < W。w； }}edges［M］；int find（int x） // 並查集核心操作{ if （p［x］ ！= x） p［x］ = find（p［x］）； return p［x］；}int kruskal（）{ sort（edges， edges + m）； for （int i = 1； i <= n； i ++ ） p［i］ = i； // 初始化並查集 int res = 0， cnt = 0； for （int i = 0； i < m； i ++ ） { int a = edges［i］。a， b = edges［i］。b， w = edges［i］。w； a = find（a）， b = find（b）； if （a ！= b） // 如果兩個連通塊不連通，則將這兩個連通塊合併 { p［a］ = b； res += w； cnt ++ ； } } if （cnt < n - 1） return INF； return res；}
染色法判別二分圖
時間複雜度是
O（n+m）
，
n
表示點數，
m
表示邊數
int n； // n表示點數int h［N］， e［M］， ne［M］， idx； // 鄰接表儲存圖int color［N］； // 表示每個點的顏色，-1表示未染色，0表示白色，1表示黑色// 引數：u表示當前節點，c表示當前點的顏色bool dfs（int u， int c）{ color［u］ = c； for （int i = h［u］； i ！= -1； i = ne［i］） { int j = e［i］； if （color［j］ == -1） { if （！dfs（j， ！c）） return false； } else if （color［j］ == c） return false； } return true；}bool check（）{ memset（color， -1， sizeof color）； bool flag = true； for （int i = 1； i <= n； i ++ ） if （color［i］ == -1） if （！dfs（i， 0）） { flag = false； break； } return flag；}
匈牙利演算法
時間複雜度是
O（nm）
，
n
表示點數，
m
表示邊數
int n1， n2； // n1表示第一個集合中的點數，n2表示第二個集合中的點數int h［N］， e［M］， ne［M］， idx； // 鄰接表儲存所有邊，匈牙利演算法中只會用到從第一個集合指向第二個集合的邊，所以這裡只用存一個方向的邊int match［N］； // 儲存第二個集合中的每個點當前匹配的第一個集合中的點是哪個bool st［N］； // 表示第二個集合中的每個點是否已經被遍歷過bool find（int x）{ for （int i = h［x］； i ！= -1； i = ne［i］） { int j = e［i］； if （！st［j］） { st［j］ = true； if （match［j］ == 0 || find（match［j］）） { match［j］ = x； return true； } } } return false；}// 求最大匹配數，依次列舉第一個集合中的每個點能否匹配第二個集合中的點int res = 0；for （int i = 1； i <= n1； i ++ ）{ memset（st， false， sizeof st）； if （find（i）） res ++ ；}
3。4 數學知識
試除法判定質數
bool is_prime（int x）{ if （x < 2） return false； for （int i = 2； i <= x / i； i ++ ） if （x % i == 0） return false； return true；}
試除法分解質因數
void divide（int x）{ for （int i = 2； i <= x / i； i ++ ） if （x % i == 0） { int s = 0； while （x % i == 0） x /= i， s ++ ； cout << i << ‘ ’ << s << endl； } if （x > 1） cout << x << ‘ ’ << 1 << endl； cout << endl；}
樸素篩法求素數
int primes［N］， cnt； // primes［］儲存所有素數bool st［N］； // st［x］儲存x是否被篩掉void get_primes（int n）{ for （int i = 2； i <= n； i ++ ） { if （st［i］） continue； primes［cnt ++ ］ = i； for （int j = i + i； j <= n； j += i） st［j］ = true； }}
線性篩法求素數
int primes［N］， cnt； // primes［］儲存所有素數bool st［N］； // st［x］儲存x是否被篩掉void get_primes（int n）{ for （int i = 2； i <= n； i ++ ） { if （！st［i］） primes［cnt ++ ］ = i； for （int j = 0； primes［j］ <= n / i； j ++ ） { st［primes［j］ * i］ = true； if （i % primes［j］ == 0） break； } }}
試除法求所有約數
vector
約數個數和約數之和
如果 N = p1^c1 * p2^c2 * 。。。 *pk^ck約數個數： （c1 + 1） * （c2 + 1） * 。。。 * （ck + 1）約數之和： （p1^0 + p1^1 + 。。。 + p1^c1） * 。。。 * （pk^0 + pk^1 + 。。。 + pk^ck）
歐幾里得演算法
int gcd（int a， int b）{ return b ？ gcd（b， a % b） ： a；}
求尤拉函式
int phi（int x）{ int res = x； for （int i = 2； i <= x / i； i ++ ） if （x % i == 0） { res = res / i * （i - 1）； while （x % i == 0） x /= i； } if （x > 1） res = res / x * （x - 1）； return res；}
篩法求尤拉函式
int primes［N］， cnt； // primes［］儲存所有素數int euler［N］； // 儲存每個數的尤拉函式bool st［N］； // st［x］儲存x是否被篩掉void get_eulers（int n）{ euler［1］ = 1； for （int i = 2； i <= n； i ++ ） { if （！st［i］） { primes［cnt ++ ］ = i； euler［i］ = i - 1； } for （int j = 0； primes［j］ <= n / i； j ++ ） { int t = primes［j］ * i； st［t］ = true； if （i % primes［j］ == 0） { euler［t］ = euler［i］ * primes［j］； break； } euler［t］ = euler［i］ * （primes［j］ - 1）； } }}
快速冪
求 m^k mod p，時間複雜度 O（logk）。int qmi（int m， int k， int p）{ int res = 1 % p， t = m； while （k） { if （k&1） res = res * t % p； t = t * t % p； k >>= 1； } return res；}
擴充套件歐幾里得演算法
// 求x， y，使得ax + by = gcd（a， b）int exgcd（int a， int b， int &x， int &y）{ if （！b） { x = 1； y = 0； return a； } int d = exgcd（b， a % b， y， x）； y -= （a/b） * x； return d；}
高斯消元
// a［N］［N］是增廣矩陣int gauss（）{ int c， r； for （c = 0， r = 0； c < n； c ++ ） { int t = r； for （int i = r； i < n； i ++ ） // 找到絕對值最大的行 if （fabs（a［i］［c］） > fabs（a［t］［c］）） t = i； if （fabs（a［t］［c］） < eps） continue； for （int i = c； i <= n； i ++ ） swap（a［t］［i］， a［r］［i］）； // 將絕對值最大的行換到最頂端 for （int i = n； i >= c； i —— ） a［r］［i］ /= a［r］［c］； // 將當前行的首位變成1 for （int i = r + 1； i < n； i ++ ） // 用當前行將下面所有的列消成0 if （fabs（a［i］［c］） > eps） for （int j = n； j >= c； j —— ） a［i］［j］ -= a［r］［j］ * a［i］［c］； r ++ ； } if （r < n） { for （int i = r； i < n； i ++ ） if （fabs（a［i］［n］） > eps） return 2； // 無解 return 1； // 有無窮多組解 } for （int i = n - 1； i >= 0； i —— ） for （int j = i + 1； j < n； j ++ ） a［i］［n］ -= a［i］［j］ * a［j］［n］； return 0； // 有唯一解}
遞迴法求組合數
// c［a］［b］ 表示從a個蘋果中選b個的方案數for （int i = 0； i < N； i ++ ） for （int j = 0； j <= i； j ++ ） if （！j） c［i］［j］ = 1； else c［i］［j］ = （c［i - 1］［j］ + c［i - 1］［j - 1］） % mod；
透過預處理逆元的方式求組合數
首先預處理出所有階乘取模的餘數fact［N］，以及所有階乘取模的逆元infact［N］如果取模的數是質數，可以用費馬小定理求逆元int qmi（int a， int k， int p） // 快速冪模板{ int res = 1； while （k） { if （k & 1） res = （LL）res * a % p； a = （LL）a * a % p； k >>= 1； } return res；}// 預處理階乘的餘數和階乘逆元的餘數fact［0］ = infact［0］ = 1；for （int i = 1； i < N； i ++ ）{ fact［i］ = （LL）fact［i - 1］ * i % mod； infact［i］ = （LL）infact［i - 1］ * qmi（i， mod - 2， mod） % mod；}
Lucas定理
若p是質數，則對於任意整數 1 <= m <= n，有： C（n， m） = C（n % p， m % p） * C（n / p， m / p） （mod p）int qmi（int a， int k， int p） // 快速冪模板{ int res = 1 % p； while （k） { if （k & 1） res = （LL）res * a % p； a = （LL）a * a % p； k >>= 1； } return res；}int C（int a， int b， int p） // 透過定理求組合數C（a， b）{ if （a < b） return 0； LL x = 1， y = 1； // x是分子，y是分母 for （int i = a， j = 1； j <= b； i ——， j ++ ） { x = （LL）x * i % p； y = （LL） y * j % p； } return x * （LL）qmi（y， p - 2， p） % p；}int lucas（LL a， LL b， int p）{ if （a < p && b < p） return C（a， b， p）； return （LL）C（a % p， b % p， p） * lucas（a / p， b / p， p） % p；}
分解質因數法求組合數
當我們需要求出組合數的真實值，而非對某個數的餘數時，分解質因數的方式比較好用： 1。 篩法求出範圍內的所有質數 2。 透過 C（a， b） = a！ / b！ / （a - b）！ 這個公式求出每個質因子的次數。 n！ 中p的次數是 n / p + n / p^2 + n / p^3 + 。。。 3。 用高精度乘法將所有質因子相乘int primes［N］， cnt； // 儲存所有質數int sum［N］； // 儲存每個質數的次數bool st［N］； // 儲存每個數是否已被篩掉void get_primes（int n） // 線性篩法求素數{ for （int i = 2； i <= n； i ++ ） { if （！st［i］） primes［cnt ++ ］ = i； for （int j = 0； primes［j］ <= n / i； j ++ ） { st［primes［j］ * i］ = true； if （i % primes［j］ == 0） break； } }}int get（int n， int p） // 求n！中的次數{ int res = 0； while （n） { res += n / p； n /= p； } return res；}vector
卡特蘭數
給定n個0和n個1，它們按照某種順序排成長度為2n的序列，滿足任意字首中0的個數都不少於1的個數的序列的數量為： Cat（n） = C（2n， n） / （n + 1）
NIM遊戲
給定N堆物品，第i堆物品有Ai個。兩名玩家輪流行動，每次可以任選一堆，取走任意多個物品，可把一堆取光，但不能不取。取走最後一件物品者獲勝。兩人都採取最優策略，問先手是否必勝。
我們把這種遊戲稱為NIM博弈。把遊戲過程中面臨的狀態稱為局面。整局遊戲第一個行動的稱為先手，第二個行動的稱為後手。若在某一局面下無論採取何種行動，都會輸掉遊戲，則稱該局面必敗。
所謂採取最優策略是指，若在某一局面下存在某種行動，使得行動後對面面臨必敗局面，則優先採取該行動。同時，這樣的局面被稱為必勝。我們討論的博弈問題一般都只考慮理想情況，即兩人均無失誤，都採取最優策略行動時遊戲的結果。
NIM博弈不存在平局，只有先手必勝和先手必敗兩種情況。
定理： NIM博弈先手必勝，當且僅當 A1 ^ A2 ^ … ^ An != 0
公平組合遊戲ICG
若一個遊戲滿足：
由兩名玩家交替行動；
在遊戲程序的任意時刻，可以執行的合法行動與輪到哪名玩家無關；
不能行動的玩家判負；
則稱該遊戲為一個公平組合遊戲。
NIM博弈屬於公平組合遊戲，但城建的棋類遊戲，比如圍棋，就不是公平組合遊戲。因為圍棋交戰雙方分別只能落黑子和白子，勝負判定也比較複雜，不滿足條件2和條件3。
有向圖遊戲
給定一個有向無環圖，圖中有一個唯一的起點，在起點上放有一枚棋子。兩名玩家交替地把這枚棋子沿有向邊進行移動，每次可以移動一步，無法移動者判負。該遊戲被稱為有向圖遊戲。
任何一個公平組合遊戲都可以轉化為有向圖遊戲。具體方法是，把每個局面看成圖中的一個節點，並且從每個局面向沿著合法行動能夠到達的下一個局面連有向邊。
Mex運算
設
S
表示一個非負整數集合。定義
mex（S）
為求出不屬於集合
S
的最小非負整數的運算，即：
mex（S） = min{x}
，
x
屬於自然數，且
x
不屬於
S
。
SG函式
在有向圖遊戲中，對於每個節點
x
，設從
x
出發共有
k
條有向邊，分別到達節點
y_1， y_2， …， y_k
，定義
SG（x）
為
x
的後繼節點
y_1， y_2， …， y_k
的
SG
函式值構成的集合再執行
mex（S）
運算的結果，即：
SG（x） = mex（{SG（y1）， SG（y2）， …， SG（yk）}）
特別地，整個有向圖遊戲
G
的
SG
函式值被定義為有向圖遊戲起點
s
的
SG
函式值，即
SG（G） = SG（s）
。
有向圖遊戲的和
設
G_1， G_2， …， G_m
是
m
個有向圖遊戲。定義有向圖遊戲
G
，它的行動規則是任選某個有向圖遊戲
G_i
，並在
G_i
上行動一步。
G
被稱為有向圖遊戲
G_1， G_2， …， G_m
的和。
有向圖遊戲的和的
SG
函式值等於它包含的各個子游戲
SG
函式值的異或和，即：
SG（G） = SG（G1） ^ SG（G2） ^ … ^ SG（Gm）
定理
有向圖遊戲的某個局面必勝，當且僅當該局面對應節點的
SG
函式值大於0。
有向圖遊戲的某個局面必敗，當且僅當該局面對應節點的
SG
函式值等於0。
4 算題說明
在進行高階演算法題前，至少得掌握這幾種基本的演算法思想：
模擬、列舉、遞迴、分治、二分查詢
，要了解
動態規劃、貪心、回溯、深度優先搜尋、寬度優先搜尋
的大致流程。
基礎部分的書籍推薦《
演算法基礎與線上實踐
》、進階部分的書籍推薦《
演算法競賽進階指南
》。
第二部分來自我結合網上資料的總結，第三部分的演算法模板來自北大的某位大神，當我們逐漸刷題量變多時，可以整理出自己的模板，從而能夠更加自如地應對大部分題。
