歸去來(lái)兮。

1.1 說(shuō)明

本篇為《挑戰(zhàn)程序設(shè)計(jì)競(jìng)賽（第2版）》讀書(shū)筆記系列坑雅，旨在：

• 梳理算法邏輯
• 探索優(yōu)化思路
• 深入代碼細(xì)節(jié)

1.2 目錄

按算法難度劃分為初中高三個(gè)級(jí)別，詳細(xì)目錄及鏈接如下：

• 初級(jí)篇

  1. 窮竭搜索
  2. 貪心
  3. 動(dòng)態(tài)規(guī)劃
  4. 數(shù)據(jù)結(jié)構(gòu)
  5. 圖論
  6. 數(shù)論

• 中級(jí)篇

  1. 二分搜索
  2. 常用技巧
  3. 數(shù)據(jù)結(jié)構(gòu)（二）
  4. 動(dòng)態(tài)規(guī)劃（二）
  5. 網(wǎng)絡(luò)流
  6. 計(jì)算幾何

• 高級(jí)篇

  1. 數(shù)論（二）
  2. 博弈論
  3. 圖論（二）
  4. 常用技巧（二）
  5. 智慧搜索
  6. 分治
  7. 字符串

1.3 題解

配套習(xí)題及詳解同步發(fā)布在GitHub倉(cāng)庫(kù)acm-challenge-workbook巢音，持續(xù)更新累澡。預(yù)計(jì)在2017年3月完成，歡迎watch鞍匾。習(xí)題難度從國(guó)內(nèi)機(jī)試交洗、國(guó)外IT名企面試到ACM地區(qū)賽不等，吃透算法習(xí)題冊(cè)橡淑，應(yīng)聘足以构拳。

1.4 題庫(kù)

• Google Code Jam（GCJ）
• Peking University Online Judge（POJ）
• CodeForces（CF）
• LeetCode（LC）
• Aizu Online Judge（AOJ）

2.1 窮竭搜索

2.1.1 核心思想

1. 深度優(yōu)先搜索（DFS）：從某個(gè)狀態(tài)開(kāi)始，不斷轉(zhuǎn)移，直至無(wú)法轉(zhuǎn)移置森，回退到前一步斗埂，再繼續(xù)轉(zhuǎn)移到其他狀態(tài)，直到找到最終解凫海。通常采用遞歸函數(shù)或者棧（Stack）來(lái)實(shí)現(xiàn)蜜笤。
2. 寬度優(yōu)先搜索（BFS）：從初始狀態(tài)開(kāi)始，總是先搜索至距離初始狀態(tài)近的狀態(tài)盐碱。每個(gè)狀態(tài)都只經(jīng)過(guò)一次把兔，因此復(fù)雜度為O(狀態(tài)數(shù)*轉(zhuǎn)移方式數(shù))。通常采用循環(huán)或隊(duì)列（Queue）實(shí)現(xiàn)瓮顽。

2.1.2 優(yōu)化細(xì)節(jié)

1. 特殊狀態(tài)枚舉：可行解空間多數(shù)可采用DFS县好，但當(dāng)其比較特殊時(shí)，可簡(jiǎn)短地實(shí)現(xiàn)暖混。
   • 全排列使用STL中的next_permutation
   • 組合或子集使用位運(yùn)算
2. 剪枝：明確知道從當(dāng)前狀態(tài)無(wú)論如何轉(zhuǎn)移都不會(huì)存在解的情況下缕贡，不再繼續(xù)搜索而是直接跳過(guò)。
3. 棧內(nèi)存與堆內(nèi)存：
   • main函數(shù)中的局部變量存儲(chǔ)在棧內(nèi)存中拣播，統(tǒng)一分配后不再擴(kuò)大晾咪，影響棧深度，與機(jī)器設(shè)置有關(guān)贮配。通常谍倦，C++中執(zhí)行上萬(wàn)次遞歸是可行的。
   • new或malloc的分配的是堆內(nèi)存泪勒，全局變量存儲(chǔ)在堆內(nèi)存中昼蛀，使用全局變量代替局部變量可減少棧溢出的風(fēng)險(xiǎn)。
4. 加深深度優(yōu)先搜索（IDDFS）：初始的DFS遞歸深度限制為1圆存，在找到解之前不斷增加遞歸深度叼旋。

2.2 貪心

2.2.1 核心思想

1. 貪心算法：遵循某種規(guī)律，不斷貪心選取當(dāng)前最優(yōu)策略沦辙。
2. 貪心證明：
   • 與其它選擇方案相比夫植，該算法并不會(huì)得到更差的解（歸納法）
   • 不存在其他的解決方案（反證法）

2.3 動(dòng)態(tài)規(guī)劃

2.3.1 核心思想

1. 動(dòng)態(tài)規(guī)劃（DP）：通過(guò)定義某種最優(yōu)子狀態(tài)，進(jìn)行狀態(tài)間轉(zhuǎn)移達(dá)到最終解油讯。
2. 記憶化搜索：將重復(fù)狀態(tài)通過(guò)標(biāo)記降低復(fù)雜度详民。
3. 多種形式的DP：搜索的記憶化或利用遞推關(guān)系的DP，或從狀態(tài)轉(zhuǎn)移考慮的DP撞羽。狀態(tài)定義和循環(huán)順序都會(huì)影響復(fù)雜度阐斜。

2.3.2 優(yōu)化細(xì)節(jié)

1. 使用memset初始化
2. 重復(fù)循環(huán)數(shù)組
3. dp僅bool是一種浪費(fèi)
4. 根據(jù)規(guī)模改變DP對(duì)象

2.3.3 經(jīng)典模型

1. 背包問(wèn)題（01背包衫冻，完全背包）
2. 最長(zhǎng)子序列（LCS诀紊，LIS）
3. 劃分?jǐn)?shù)（第二類(lèi)Stirling數(shù)，Bell數(shù)）

2.4 數(shù)據(jù)結(jié)構(gòu)

2.4.1 核心思想

1. 優(yōu)先隊(duì)列：包含兩類(lèi)操作插入和取值。插入一個(gè)數(shù)值邻奠，獲取最小值并刪除笤喳。堆可高效實(shí)現(xiàn)優(yōu)先隊(duì)列。
2. 堆：兒子的值一定不小于父親的值的一種二叉樹(shù)碌宴。插入時(shí)先在堆末插入杀狡，不斷上移直至無(wú)大小顛倒。取值時(shí)贰镣，刪除最小值呜象，將堆末節(jié)點(diǎn)復(fù)制到根，不斷下移直至無(wú)大小顛倒碑隆。插入和取值復(fù)雜度都為O(logn)恭陡。
3. 二叉搜索樹(shù)：對(duì)所有節(jié)點(diǎn)都滿(mǎn)足，左子樹(shù)上的所有節(jié)點(diǎn)比自己小上煤，右子樹(shù)上的所有節(jié)點(diǎn)比自己大休玩。插入與查詢(xún)類(lèi)似二分，刪除時(shí)將刪除節(jié)點(diǎn)左子樹(shù)最大值或右子樹(shù)（無(wú)左子樹(shù)時(shí)）上移劫狠，每種操作復(fù)雜度都為O(logn)拴疤。
4. 并查集：一種管理元素分組情況的數(shù)據(jù)結(jié)構(gòu)《琅ⅲ可以查詢(xún)兩個(gè)元素是否同組呐矾，可以合并兩組元素，但不能進(jìn)行分割操作懦砂。一次操作復(fù)雜度為阿克曼函數(shù)反函數(shù)a(n)凫佛，比O(logn)快。

2.4.2 優(yōu)化細(xì)節(jié)

1. 平衡二叉樹(shù)（AVL）：當(dāng)左右子樹(shù)深度差超過(guò)1時(shí)孕惜，將更深的子樹(shù)旋轉(zhuǎn)上移愧薛，達(dá)到整棵樹(shù)的平衡，避免二查搜索樹(shù)退化后復(fù)雜度升至O(n)衫画。
2. 路徑壓縮：并查集向上的遞歸操作中毫炉，沿途所有節(jié)點(diǎn)一旦向上走到一次根節(jié)點(diǎn)，就把其到父親的邊直接連向根削罩。
3. 并查集的同組：廣義可表示組內(nèi)所有元素代表的情況同時(shí)發(fā)生或不發(fā)生瞄勾。
4. STL標(biāo)準(zhǔn)庫(kù)：
   • 優(yōu)先隊(duì)列：priority_queue（默認(rèn)根為最大值）
   • 二查搜索樹(shù)：set（集合）、map（鍵和值對(duì)應(yīng)）弥激、multiset和multimap（可存放重復(fù)鍵值）

2.5 圖論

2.5.1 核心思想

1. 圖：頂點(diǎn)集合為V进陡、邊集為E的圖記作G=(V,E)，從u到v的邊記作e=(u,v)微服。根據(jù)邊是否有向分為有向圖和無(wú)向圖趾疚，根據(jù)是否有環(huán)分為有環(huán)圖和無(wú)環(huán)圖。圖可由鄰接表和鄰接矩陣兩種方式表示。
2. Bellman-Ford算法（單源最短路）：記錄起點(diǎn)到每個(gè)點(diǎn)i的最短距離d[i]糙麦，用所有的邊條件持續(xù)更新d[i]辛孵，直到每個(gè)d[i]都已經(jīng)為最小無(wú)法更新。圖可包含負(fù)權(quán)邊赡磅，包含負(fù)環(huán)的判斷方法為將所有d[i]初始化為0魄缚，第V次d[i]是否仍存在更新。復(fù)雜度為O(EV)焚廊。
3. Dijkstra算法（單源最短路）：從起點(diǎn)出發(fā)<s, d[s]=0>出發(fā)冶匹，更新s所有可到達(dá)的邊j，若d[j]有更新咆瘟，則加入最小堆徙硅，以便下次找到剩余集合中d[i]最小的點(diǎn)i，再?gòu)膇出發(fā)BFS搞疗，直到到達(dá)終點(diǎn)t嗓蘑。不能處理包含負(fù)權(quán)邊的圖。復(fù)雜度為O(ElogV)匿乃。
4. Floyd-Warshall算法（多源最短路）：定義從i到j(luò)且經(jīng)過(guò)k的最短路為d[i][j]用d[i][k]+d[k][j]來(lái)更新桩皿，三重循環(huán)直接得到任意兩點(diǎn)間的最短路。圖可包含負(fù)權(quán)邊幢炸，包含負(fù)環(huán)的判斷方法為是否存在頂點(diǎn)i使d[i][i]為負(fù)泄隔。復(fù)雜度O(V^3)。
5. Prim算法（最小生成樹(shù)）：假設(shè)V的子集X已經(jīng)構(gòu)造了部分最小生成樹(shù)宛徊，那么接下來(lái)就是選取從X到X的補(bǔ)集中權(quán)值最小的邊加入佛嬉。可使用最小堆維護(hù)待選的邊闸天，復(fù)雜度為O(ElogV)暖呕。
6. Kruskal算法（最小生成樹(shù)）：將所有邊升序排列，依次取出每條最小的邊苞氮，若該邊的兩個(gè)端點(diǎn)不在相同并查集內(nèi)湾揽，則將該邊加入最小生成樹(shù)，并將兩點(diǎn)用并查集連接笼吟。耗時(shí)最多的操作為邊的排序库物，復(fù)雜度O(ElogE)。

2.5.2 優(yōu)化細(xì)節(jié)

1. 最短路本質(zhì)是動(dòng)態(tài)規(guī)劃贷帮，最小生成樹(shù)本質(zhì)是貪心戚揭。
2. Bellman-Ford算法和Floyd-Warshall算法可處理包含負(fù)權(quán)邊的圖，并結(jié)合各自特性判斷是否存在負(fù)環(huán)撵枢。
3. 差分約束：將不等式組轉(zhuǎn)化為包含負(fù)權(quán)邊的單源最短路問(wèn)題民晒，一般采用Bellman-Ford方法解決精居。若d[i]+x>=d[j]，則創(chuàng)建有向邊e(i,j)=x镀虐。從起點(diǎn)s到終點(diǎn)t的最短路d[t]為s和t允許的最大差。若存在負(fù)環(huán)沟绪，則不等式組無(wú)解刮便；若d[t]=INF，則s和t相差可任意绽慈。

2.6 數(shù)論

2.6.1 核心思想

1. 輾轉(zhuǎn)相除算法（最小公約數(shù)）：gcd(a,b)=gcd(b,a%b)恨旱，循環(huán)至b為0，此時(shí)得到最小公約數(shù)為a坝疼。
2. 擴(kuò)展歐幾里德算法（解二元一次方程）：求解ax+by=gcd(a,b)搜贤，類(lèi)似輾轉(zhuǎn)相除法。求extgcd(a,b,&x,&y)時(shí)钝凶，遞歸求得d=extgcd(b,a%b,y,x)的解存入y和x仪芒。則ax+by=gcd(a,b)的解為x和y-(a/b)*x。
3. 素?cái)?shù)篩法：通過(guò)已求得的素?cái)?shù)耕陷，將所求范圍內(nèi)所有該素?cái)?shù)的倍數(shù)都標(biāo)記為合數(shù)掂名。依序遍歷空間，未被篩掉的即為新的素?cái)?shù)哟沫。復(fù)雜度O(nloglogn)饺蔑，可看作線性的。
4. 反復(fù)平方法（快速冪）：求x的n次冪嗜诀，可二分遞歸求x的n/2次冪猾警，即x^n=(x(n/2))^2 * x^(n&1)。復(fù)雜度為O(logn)隆敢。

2.6.2 優(yōu)化細(xì)節(jié)

1. ax+by=gcd(a,b)的解大蟹⒚蟆：x的絕對(duì)值不大于b，y的絕對(duì)值不大于a拂蝎。若要求得滿(mǎn)足某個(gè)范圍的解雳窟，可通過(guò)參數(shù)k調(diào)節(jié)，x+=k(b/d)匣屡、y-=k(a/d)為原方程的解簇封救。
2. 線性素?cái)?shù)篩法：遍歷解空間，無(wú)論當(dāng)前數(shù)是否為素?cái)?shù)捣作，將已經(jīng)求得得素?cái)?shù)集合中的數(shù)乘以它得到合數(shù)標(biāo)記篩去誉结。并且若該數(shù)為合數(shù)，它乘以的素?cái)?shù)為它的因子券躁，則對(duì)該數(shù)不再繼續(xù)循環(huán)已有的素?cái)?shù)集合惩坑。上述可保證掉盅，每個(gè)合數(shù)都只通過(guò)乘以它最小的因子得到，即復(fù)雜度為線性以舒。注意趾痘，該方法使得已有的素?cái)?shù)集合中的組合并不一定被立即篩去，在以后遍歷到特定合數(shù)時(shí)才會(huì)被標(biāo)記蔓钟。
3. 模運(yùn)算：用64位處理對(duì)32數(shù)的模穗泵，避免發(fā)生溢出餐屎。模運(yùn)算對(duì)加減乘可以直接應(yīng)用，但對(duì)同模的兩邊做除法時(shí)，若原始ac=bc(mod m)封锉，則a-b=m*k/c拂共，則a=b(mod m/gcd(m,c))雕欺。

3.1 二分搜索

3.1.1 核心思想

1. 二分搜索：對(duì)于某個(gè)有序區(qū)間聋丝，每次查找區(qū)間中點(diǎn)是否滿(mǎn)足條件，并以此為依據(jù)缀辩，決定遞歸查詢(xún)左半?yún)^(qū)間或右半?yún)^(qū)間臭埋。反復(fù)循環(huán)上述折半過(guò)程，直到條件或精度被滿(mǎn)足臀玄。

3.1.2 優(yōu)化細(xì)節(jié)

1. STL：以函數(shù)lower_bound()和up_bound()的形式實(shí)現(xiàn)了二分搜索
2. 結(jié)束判定：1次循環(huán)可將區(qū)間減半斋泄，循環(huán)100次可達(dá)到精度10^-30 。還可通過(guò)區(qū)間長(zhǎng)度與EPS判斷镐牺，但要避免EPS太小因浮點(diǎn)數(shù)精度問(wèn)題造成的死循環(huán)炫掐。

3.1.3 經(jīng)典模型

1. 有序數(shù)組中查找某值
2. 判斷一個(gè)假定解是否可行
3. 最大化最小值
4. 最大化平均值

3.2 常用技巧

3.2.1 核心思想

1. 尺取法：又稱(chēng)兩點(diǎn)法，通過(guò)在區(qū)間上標(biāo)記并順序移動(dòng)頭尾兩點(diǎn)睬涧，將復(fù)雜度降為線性募胃。
2. 反轉(zhuǎn)（開(kāi)關(guān)問(wèn)題）：若為初末態(tài)確定，則可通過(guò)貪心求得最少步驟畦浓。高斯消元法也可求得一組可行解痹束，且自由變?cè)邢蓿砸部梢郧蟮米顑?yōu)解讶请。
3. 集合的整數(shù)表示：通過(guò)二進(jìn)制將集合狀態(tài)映射至整數(shù)祷嘶。涉及到的位運(yùn)算包括：與、或夺溢、非（取反）论巍、異或、取負(fù)（取反+1）风响、邏輯左移右移嘉汰、交、并状勤。遍歷所有子集或找到所有大小為k的子集鞋怀，都可以通過(guò)位運(yùn)算操作求得字典序升序的二進(jìn)制碼双泪。
4. 折半枚舉（雙向搜索）：當(dāng)全局枚舉復(fù)雜度太大時(shí)，可將條目折半密似，分別枚舉所有情況焙矛。復(fù)雜度降為原本平方根。
5. 坐標(biāo)離散化：將數(shù)列排序并去重残腌，將原數(shù)列離散化映射至有限可控的區(qū)間村斟。

3.3 數(shù)據(jù)結(jié)構(gòu)（二）

3.3.1 核心思想

1. 線段樹(shù)：是一棵完美二叉樹(shù)，樹(shù)上的每個(gè)節(jié)點(diǎn)表示一個(gè)區(qū)間废累。根節(jié)點(diǎn)維護(hù)整個(gè)區(qū)間邓梅，其他每個(gè)節(jié)點(diǎn)維護(hù)父節(jié)點(diǎn)二分后的某個(gè)區(qū)間脱盲。查詢(xún)和更新復(fù)雜度都是O(logn)邑滨。
2. 樹(shù)狀數(shù)組（BIT）：將線段樹(shù)每個(gè)節(jié)點(diǎn)的右兒子去掉，用每個(gè)節(jié)點(diǎn)表示區(qū)間的右邊界代表該節(jié)點(diǎn)的索引钱反，這樣就可以通過(guò)一個(gè)線性數(shù)組維護(hù)所有必要的區(qū)間掖看。索引的二進(jìn)制最低位的1表示區(qū)間長(zhǎng)度，值為x&-x面哥。求和和更新復(fù)雜度都是O(logn)哎壳。
3. 平方分割：將n個(gè)元素裝入√n個(gè)桶內(nèi)，每個(gè)桶√n個(gè)元素的分桶法尚卫，每個(gè)桶分別維護(hù)自己內(nèi)部的信息归榕。對(duì)區(qū)間的復(fù)雜度操作可降至O(√n)。

3.3.2 優(yōu)化細(xì)節(jié)

1. 懶惰標(biāo)記：線段樹(shù)可以通過(guò)在父節(jié)點(diǎn)上維護(hù)一個(gè)懶惰標(biāo)記吱涉，來(lái)表示整棵子樹(shù)的狀態(tài)刹泄。在自頂向下的查詢(xún)操作中，在遞歸該父節(jié)點(diǎn)時(shí)怎爵，將標(biāo)記下移至兩個(gè)兒子節(jié)點(diǎn)特石，并且更新父節(jié)點(diǎn)真正維護(hù)的直接變量。
2. 稀疏表：與線段樹(shù)類(lèi)似的是其區(qū)間長(zhǎng)度都是2的整數(shù)次冪鳖链，但每個(gè)長(zhǎng)度層級(jí)的區(qū)間左端點(diǎn)都連續(xù)姆蘸。進(jìn)行RMQ查詢(xún)時(shí)，只需要找到不大于區(qū)間的最大2的整數(shù)冪芙委，根據(jù)這個(gè)長(zhǎng)度逞敷，待求解的左端點(diǎn)及右端點(diǎn)減去長(zhǎng)度即為該行在稀疏表內(nèi)的列的值。預(yù)處理時(shí)時(shí)間和空間復(fù)雜度都高達(dá)O(nlogn)灌侣，但結(jié)合二分查找的單次查詢(xún)比線段樹(shù)快兰粉，只需要O(loglogn)。
3. 維護(hù)多項(xiàng)式：如果需要維護(hù)的變量可以表示為索引i的n次多項(xiàng)式顶瞳，則可以用n+1個(gè)樹(shù)狀數(shù)組來(lái)維護(hù)玖姑°碉或者，線段樹(shù)的每個(gè)節(jié)點(diǎn)維護(hù)n+1個(gè)值焰络。
4. 區(qū)域樹(shù)：線段樹(shù)的每個(gè)節(jié)點(diǎn)可以維護(hù)一個(gè)數(shù)組或維護(hù)一棵線段樹(shù)戴甩，適合對(duì)矩形的區(qū)域進(jìn)行處理。并且闪彼，和樹(shù)狀數(shù)組一樣甜孤，多重線段樹(shù)嵌套可以實(shí)現(xiàn)高維度的區(qū)域樹(shù)。

3.4 動(dòng)態(tài)規(guī)劃（二）

3.4.1 核心思想

1. 狀態(tài)壓縮DP：通常結(jié)合進(jìn)制數(shù)的特點(diǎn)畏腕，將每個(gè)狀態(tài)壓縮表示為整數(shù)缴川。復(fù)雜特殊狀態(tài)的轉(zhuǎn)移就可以表示為整數(shù)下標(biāo)的等式。
2. 矩陣快速冪：若動(dòng)態(tài)規(guī)劃的遞推關(guān)系式可以表示為多元一次多項(xiàng)式描馅，則可以通過(guò)某常系數(shù)矩陣的冪與初始向量的乘積求得最后的結(jié)果向量把夸。其中求冪可以結(jié)合基于二分思想的快速冪算法。用n表示冪次數(shù)铭污，m表示向量規(guī)模恋日，則復(fù)雜度為O(m^3logn)。

3.4.2 優(yōu)化細(xì)節(jié)

1. 結(jié)合數(shù)據(jù)結(jié)構(gòu)：某些時(shí)候涉及到更新和查詢(xún)操作時(shí)嘹狞，如果利用線段樹(shù)等高級(jí)數(shù)據(jù)結(jié)構(gòu)處理岂膳，可以使得轉(zhuǎn)移方程中線性的遍歷轉(zhuǎn)化為對(duì)數(shù)級(jí)別的查詢(xún)。

3.5 網(wǎng)絡(luò)流

3.5.1 核心思想

1. 最大流：增加反向補(bǔ)償邊磅网，在殘流網(wǎng)絡(luò)上不斷尋找增廣路谈截。常用樸素尋找增廣路的Ford-Fulkerson算法，復(fù)雜度為O(FE)涧偷。通過(guò)最短路算法預(yù)處理為分層圖的Dinic算法簸喂，復(fù)雜度為O(EV^2)。
2. 最小割：將割中的邊全部刪去后嫂丙，源點(diǎn)無(wú)通路可再到達(dá)匯點(diǎn)娘赴。最小割是最大流的強(qiáng)對(duì)偶問(wèn)題，數(shù)值相等跟啤。
3. 二分圖匹配：匈牙利算法遞歸每個(gè)頂點(diǎn)诽表，每次遞歸，將已有匹配刪除看能否得到更優(yōu)解隅肥。
4. 一般圖匹配：常用Edmonds算法竿奏，較為復(fù)雜，盡量轉(zhuǎn)化為二分圖求解腥放。
5. 最小費(fèi)用流：在殘流網(wǎng)絡(luò)上擴(kuò)展最短增廣路時(shí)泛啸，使用邊的花費(fèi)作為邊權(quán)尋找最短路。f(e)表示e中的流量秃症，h(v)表示勢(shì)（殘流網(wǎng)絡(luò)中s到v的最短路）候址，d(e)表示考慮勢(shì)后e的長(zhǎng)度吕粹。復(fù)雜度為O(FElogV)或O(FV^2)「诼兀或者通過(guò)不斷消去負(fù)圈得到最小費(fèi)用流匹耕。

3.5.2 優(yōu)化細(xì)節(jié)

1. 最大流變體：
   • 多個(gè)源點(diǎn)匯點(diǎn)：構(gòu)造超級(jí)源點(diǎn)S和匯點(diǎn)T，用S連至多個(gè)源點(diǎn)荠雕，所有匯點(diǎn)連至T稳其。
   • 無(wú)向圖：構(gòu)造正反方向的兩條邊，容量與無(wú)向邊相同炸卑。
   • 頂點(diǎn)也有流量限制：將每點(diǎn)拆為入點(diǎn)和出點(diǎn)既鞠，入點(diǎn)至出點(diǎn)連邊。
   • 最小流量限制：構(gòu)造超級(jí)源S匯T盖文，對(duì)于每條邊構(gòu)造逆向的容量為下限的滿(mǎn)流圈嘱蛋；連接S到s及t到T之前，通過(guò)滿(mǎn)流判斷可行解椅寺。
   • 部分邊容量發(fā)生變化：若影響原流浑槽，則設(shè)法將殘流網(wǎng)絡(luò)中對(duì)應(yīng)邊的容量減少或通過(guò)構(gòu)造逆向圈等價(jià)減少蒋失。
   • 容量為負(fù)數(shù)：求最小割時(shí)可能出現(xiàn)負(fù)邊返帕，此時(shí)應(yīng)通過(guò)數(shù)值變換設(shè)法消除負(fù)邊。
2. 最小費(fèi)變體：
   • 類(lèi)最大流變體：構(gòu)造方式相似篙挽。
   • 最小流量限制：將原邊容量減少下限荆萤，構(gòu)造新邊容量為下限且費(fèi)用為原費(fèi)用減去一個(gè)足夠大的數(shù)。
   • 流量任意：由于點(diǎn)的勢(shì)會(huì)不斷增加铣卡，所以?xún)H在勢(shì)為負(fù)數(shù)時(shí)增廣链韭，即能保證費(fèi)用不斷減小。
   • 費(fèi)用為負(fù)：不能用Dijkstra算法煮落，要用Bellmen-Ford算法處理負(fù)權(quán)邊敞峭。另外，可以通過(guò)對(duì)所有邊的費(fèi)用和最終結(jié)果進(jìn)行適當(dāng)?shù)淖冃伪苊庳?fù)權(quán)邊蝉仇。
   • 最小化有流邊的費(fèi)用之和：無(wú)法通過(guò)最小費(fèi)用流模型求解旋讹，需要建其他模。
3. 匹配相關(guān)對(duì)偶問(wèn)題：
   • 連通圖中轿衔，最大匹配+最小邊覆蓋=頂點(diǎn)數(shù)
   • 最大獨(dú)立集+最小頂點(diǎn)覆蓋=頂點(diǎn)數(shù)
   • 二分圖中沉迹，最大匹配=最小頂點(diǎn)覆蓋

3.6 計(jì)算幾何

3.6.1 核心思想

1. 平面掃描：掃描線在平面上按既定軌跡移動(dòng)時(shí)，不斷根據(jù)掃描線掃過(guò)的部分更新害驹，從而得到整體所求結(jié)果鞭呕。掃描的方法，可以從左向右平移與y軸平行的直線宛官，也可以固定射線的端點(diǎn)逆時(shí)針旋轉(zhuǎn)葫松。
2. 凸包：包圍原點(diǎn)集的最小凸多邊形的點(diǎn)組成的集合瓦糕，稱(chēng)為原點(diǎn)集的凸包。凸包上的點(diǎn)不被原點(diǎn)集任意三點(diǎn)連成的三角形包含在內(nèi)部腋么。通過(guò)Graham掃描算法刻坊，將點(diǎn)集按坐標(biāo)排序后，分為上下兩條鏈求解党晋。每次末尾加入新頂點(diǎn)谭胚，如果出現(xiàn)了凹的部分，則把凹點(diǎn)刪去未玻。Graham可以在O(nlogn)的時(shí)間內(nèi)構(gòu)造凸包灾而。最遠(yuǎn)點(diǎn)對(duì)一定是凸包上的對(duì)踵點(diǎn)，可以通過(guò)旋轉(zhuǎn)卡殼法不斷找尋對(duì)踵點(diǎn)扳剿，在O(n)復(fù)雜度內(nèi)求解旁趟。
3. 數(shù)值積分：通常在復(fù)雜的幾何相交或求和問(wèn)題中，通過(guò)對(duì)某個(gè)方向變量的微分庇绽，將立體切片或?qū)⑵矫媲谐删€段后積分得到結(jié)果锡搜。

3.6.2 優(yōu)化細(xì)節(jié)

1. 向量表示：可以使用STL的complex類(lèi)表示向量，并進(jìn)行相應(yīng)的內(nèi)積外積操作瞧掺。
2. 計(jì)算誤差：計(jì)算幾何中的浮點(diǎn)數(shù)大小比較采取與ESP結(jié)合的方式耕餐，如a<0等價(jià)于a<-ESP，a≤0等價(jià)于a<ESP辟狈。由于double類(lèi)型的精確尾數(shù)大約是10進(jìn)制下的15位肠缔，當(dāng)ESP太小時(shí)，可能造成假陰性哼转。C++中可以采用更高精度的long double明未，Java可以使用BigDecimal。
3. 極限情況：當(dāng)可行解可以取連續(xù)一段值時(shí)壹蔓，很多時(shí)候只要考慮邊界的極限情況趟妥。

4.1 數(shù)論（二）

4.1.1 核心思想

1. 線性方程組：可以采用高斯消元法求解。將方程組用矩陣表示后佣蓉，遍歷每列披摄，保留該列系數(shù)最大的行（列主元高斯消元，減少誤差）偏螺，并將其乘以一定倍數(shù)用于消除其他行的該列元素行疏。
2. 一次同余方程：ax=b (mod m)。定義a的逆元為y滿(mǎn)足ay=1 (mod m)套像，則x=yb(mod m)酿联。逆元y可以用擴(kuò)展歐幾里得求解。
3. 費(fèi)馬小定律：若p為素?cái)?shù)，a與p互素贞让，則有a^(p-1)=1 (mod p)周崭。
4. 歐拉定理：對(duì)于一個(gè)正整數(shù)N的素?cái)?shù)冪分解N=P1^q1*P2q2...Pn^{qn，歐拉函數(shù)φ(N)=N*(1-1/P1)*(1-1/P2)*...*(1-1/Pn)喳张，意義是不大于N且與N互素的正數(shù)個(gè)數(shù)续镇。此時(shí)，對(duì)于與N互素的x销部，有x}φ(N)=1 (mod N)摸航。費(fèi)馬小定律可以看作歐拉定理的推廣。
5. 線性同余方程組：若有解則一定有無(wú)數(shù)解舅桩，解的全集可寫(xiě)作x=b (mod m)酱虎。初始化為x=0，m=1擂涛。逐次加入一個(gè)新的方程ax=b (mod m)读串，將上一步的x用mt+b的形式代入，轉(zhuǎn)化為一次同余方程撒妈。
6. 中國(guó)剩余定理：n=ab（a恢暖、b互素），則（x mod n）等價(jià)于（x mod a狰右，x mod b）杰捂。所以，通過(guò)對(duì)n的質(zhì)因數(shù)分解挟阻，可以通過(guò)只考慮模n的素因子的冪p^k來(lái)計(jì)算琼娘。
7. n!模p：將階乘表示為n!=ap^{e峭弟，則e=n/p+n/p}2+n/p^{3+…附鸽。由于階乘中不能被p整除的項(xiàng)呈現(xiàn)周期性，乘積為(p-1)!}(n/p)*(n mod p)!瞒瘸。根據(jù)威爾遜定理坷备，(p-1)!=-1(mod p)∏槌簦考慮可以被p整除的部分省撑，通過(guò)全部除以p，可以遞歸到n/p的范圍考慮俯在。
8. 組合數(shù)模p：將n和m用p進(jìn)制法表示后竟秫，根據(jù)Lucas定理，Lucas(n,m,p)=c(n%p,m%p)*Lucas(n/p,m/p,p) 跷乐，則對(duì)于每一位肥败，計(jì)算其組合數(shù)模p，將答案相乘即為C(n, m)模p。
9. 容斥原理：先不考慮重疊的情況馒稍，將所有對(duì)象計(jì)算出來(lái)皿哨，再不斷遞歸把重復(fù)計(jì)算的數(shù)目排斥出去，直到結(jié)果既無(wú)遺漏又無(wú)重復(fù)纽谒。由于遞歸時(shí)排斥采取減法证膨，從全局來(lái)看應(yīng)根據(jù)地柜深度的奇偶性判斷符號(hào)正負(fù)。
10. 莫比烏斯函數(shù)：在容斥定理中鼓黔，每次排斥的規(guī)模d如果是n的約數(shù)央勒，則被加減多次的總和只和n/d有關(guān)。求這個(gè)系數(shù)的函數(shù)叫莫比烏斯函數(shù)澳化，記作μ(n/d)订歪。若x可以被大于1的完全平方數(shù)整除，則μ(x)=0肆捕；否則計(jì)算x的質(zhì)因子個(gè)數(shù)k刷晋，μ(x)=(-1)^k。莫比烏斯反演定理利用μ(x)推出慎陵，f(n)=∑g(d)等價(jià)于g(d)=∑μ(n/d)*f(d)眼虱。
11. Polya計(jì)數(shù)定理：在組合問(wèn)題中，有時(shí)要求把旋轉(zhuǎn)和翻轉(zhuǎn)之后的狀態(tài)看作相同態(tài)席纽，計(jì)算本質(zhì)不同的個(gè)數(shù)捏悬。此時(shí)應(yīng)把所有方案重復(fù)計(jì)算相同次數(shù)，再把結(jié)果除以重復(fù)的次數(shù)润梯。另外过牙，立方體的染色、相同顏色的數(shù)量限制纺铭、相鄰狀態(tài)限制寇钉，都可以用Polya求解。

4.2 博弈論

4.2.1 核心思想

1. 必勝策略：任意方式都無(wú)法轉(zhuǎn)移到必勝態(tài)的為必?cái)B(tài)N舶赔，存在一種方式可以轉(zhuǎn)移到必?cái)B(tài)的為必勝態(tài)P扫倡。
2. Nim：初始有n堆石子，每堆有ai石子竟纳，游戲規(guī)則是每次從某堆中取走至少一顆撵溃，判斷初始狀態(tài)是否必勝。若ai數(shù)組異或結(jié)果非0則為必勝態(tài)锥累，否則為必?cái)B(tài)缘挑。
3. Grundy數(shù)：當(dāng)前狀態(tài)的Grundy值是除任意一步所能轉(zhuǎn)移到的狀態(tài)的Grundy值以外的最小非負(fù)整數(shù)。所以桶略，從Grundy為x出發(fā)语淘，可以轉(zhuǎn)移到Grundy為0到x-1的狀態(tài)鬼悠。Grundy數(shù)等價(jià)于Nim中的石子個(gè)數(shù)，再通過(guò)異或判斷狀態(tài)必勝與否亏娜。

4.2.2 優(yōu)化細(xì)節(jié)

1. 取放石子：Grundy數(shù)可以轉(zhuǎn)移到更大值焕窝，等價(jià)于Nim中放回石子。但可以通過(guò)采取對(duì)應(yīng)策略再轉(zhuǎn)移到原值的狀態(tài)维贺，所以對(duì)勝負(fù)沒(méi)有影響它掂。但此時(shí)，狀態(tài)可能出現(xiàn)循環(huán)溯泣，所以需要注意可能會(huì)出現(xiàn)不分勝負(fù)虐秋、達(dá)成平局、永不結(jié)束的情況垃沦。
2. 復(fù)合游戲：由于在Nim中客给，只要異或值相同，石子堆數(shù)不影響局面性質(zhì)肢簿。所以對(duì)分割后的各部分取異或靶剑，就可以用一個(gè)Grundy數(shù)來(lái)表示幾個(gè)游戲復(fù)合而成的狀態(tài)。

4.3 圖論（二）

4.3.1 核心思想

1. 強(qiáng)連通分量：圖中任意兩點(diǎn)可互達(dá)的子圖叫做強(qiáng)連通分量池充。任意有向圖都可以分解為若干個(gè)不相交的強(qiáng)連通分量桩引。將圖中的強(qiáng)連通分量都縮成一個(gè)頂點(diǎn)，可以將原圖轉(zhuǎn)化為DAG（有項(xiàng)無(wú)環(huán)圖）收夸。
2. 強(qiáng)連通分量分解：通過(guò)兩次DFS實(shí)現(xiàn)坑匠。第一次DFS時(shí)，回溯時(shí)為頂點(diǎn)標(biāo)號(hào)（后序遍歷）卧惜。標(biāo)號(hào)越小表示離圖尾越近厘灼，即搜索樹(shù)的葉子。第二次DFS時(shí)咽瓷，將所有邊反向后设凹，從標(biāo)號(hào)大的頂點(diǎn)開(kāi)始遍歷，每次遍歷的頂點(diǎn)集合組成一個(gè)強(qiáng)連通分量忱详，記錄該分量的拓?fù)湫蛭Ю础＝又偃∥丛L問(wèn)節(jié)點(diǎn)中最大標(biāo)號(hào)的頂點(diǎn)開(kāi)始DFS匈睁，拓?fù)湫蚣右弧Ｖ钡巾旤c(diǎn)全部遍歷桶错，算法結(jié)束航唆。總的復(fù)雜度是O(V+E)院刁。
3. 2-SAT：對(duì)于每個(gè)子句中文字個(gè)數(shù)不超過(guò)二的合取范式糯钙，可以將每個(gè)子句等價(jià)轉(zhuǎn)化為兩個(gè)蘊(yùn)含關(guān)系，將所有蘊(yùn)含關(guān)系為邊、每個(gè)變量取真取假為點(diǎn)任岸，構(gòu)建有向圖再榄。圖中的每個(gè)強(qiáng)連通分量?jī)?nèi)，若某個(gè)點(diǎn)為正確享潜，則分量中所有頂點(diǎn)都為真困鸥。對(duì)于每個(gè)布爾變量，考慮其取真取假的兩個(gè)點(diǎn)剑按，點(diǎn)所在的強(qiáng)連通分量拓?fù)湫虼蟮狞c(diǎn)情況為真疾就。由此，得到一組合法的布爾變量賦值艺蝴。
4. LCA（最近公共祖先）：有根樹(shù)中猬腰，兩個(gè)結(jié)點(diǎn)的公共祖先中距離最近的那個(gè)成為L(zhǎng)CA。高效求解LCA可以采用倍增法預(yù)處理加二分搜索猜敢，或中序遍歷后利用線段樹(shù)或BIT做RMQ求解姑荷。

4.4 常用技巧（二）

4.4.1 核心思想

1. 棧的應(yīng)用：在棧內(nèi)維護(hù)一個(gè)下標(biāo)和對(duì)應(yīng)值都單向遞增的序列，則可求距離自己最近的比自己大的值缩擂。
2. 雙向隊(duì)列的應(yīng)用：隊(duì)列中維護(hù)一個(gè)以某區(qū)間內(nèi)最小值開(kāi)始厢拭，單向遞增的序列，則可求窗口大小一定的滑動(dòng)最小值撇叁。
3. 倍增法：通過(guò)預(yù)處理供鸠，計(jì)算出距離每個(gè)點(diǎn)2的次冪處的狀態(tài)。由于轉(zhuǎn)移到的目的地滿(mǎn)足一定條件陨闹，且具有與下標(biāo)單向相關(guān)性楞捂，所以可以通過(guò)二分搜索，每次將2的冪減1趋厉，判斷是否出終極目標(biāo)的位置寨闹。

4.4.2 優(yōu)化細(xì)節(jié)

1. 數(shù)量的二進(jìn)制表示：在一定數(shù)量的物品中挑選若干個(gè)，可以通過(guò)每次是否添加2的次冪個(gè)物品來(lái)決定最終結(jié)果君账。將原本枚舉的復(fù)雜度O(n)降至二進(jìn)制位數(shù)O(logn)繁堡。
2. 連續(xù)狀態(tài)轉(zhuǎn)移：在DP中，如果某狀態(tài)可由連續(xù)的下標(biāo)的一些狀態(tài)轉(zhuǎn)移來(lái)乡数，并要求其最值椭蹄。可以試著把狀態(tài)轉(zhuǎn)移方程分為兩部分净赴，一部分為常量绳矩，另一部分為只與前一狀態(tài)下標(biāo)有關(guān)。則問(wèn)題轉(zhuǎn)化為玖翅，求某個(gè)函數(shù)在某個(gè)滑動(dòng)窗口內(nèi)的最值翼馆。如果窗口大小固定不變割以，則可利用雙向隊(duì)列求解滑動(dòng)最值。

4.5 智慧搜索

4.5.1 核心思想

1. 剪枝：調(diào)整搜索順序应媚，從分支少或影響大的部分開(kāi)始搜索严沥。無(wú)任何效用或無(wú)法到達(dá)最終態(tài)的步驟可以提前剪枝。沒(méi)有最優(yōu)解則剪枝中姜，通诚可以通過(guò)貪心等算法求得最優(yōu)解下界的下界。
2. IDA：通過(guò)搜索判斷是否有某個(gè)不超過(guò)x的解扎筒，將x從0開(kāi)始每次加1莱找，首次求到解的x就是最優(yōu)解。這樣嗜桌，在搜索過(guò)程中氏义，就不會(huì)訪問(wèn)比最優(yōu)解更大的狀態(tài)匿值。迭代加深搜索（IDDFS）類(lèi)似于寬度有限搜索订讼，按距離初始狀態(tài)的遠(yuǎn)近訪問(wèn)各個(gè)狀態(tài)钧汹，而IDA會(huì)通過(guò)估算下屆提前剪枝優(yōu)化。
3. A*：BFS和Dijkstra利用下界優(yōu)化层亿，將優(yōu)先隊(duì)列中的鍵值改為初始狀態(tài)到當(dāng)前狀態(tài)的距離加上到目標(biāo)狀態(tài)的距離下界桦卒。此時(shí)，優(yōu)先隊(duì)列頂端元素未必是初始狀態(tài)到當(dāng)前狀態(tài)的最短路匿又。

4.5.2 優(yōu)化細(xì)節(jié)

1. IDA與A對(duì)比：
   • IDA針對(duì)DFS方灾，A針對(duì)BFS。
   • IDA不怎么花費(fèi)內(nèi)存碌更，A需要關(guān)于搜索空間的線性的內(nèi)存裕偿。
   • 通過(guò)不同路徑到達(dá)同一狀態(tài)，IDA效率急劇下降痛单，而A可以通過(guò)選取合適的下屆保證每個(gè)狀態(tài)至多檢查一次嘿棘。
   • IDA*在不斷增加遞歸深度限制時(shí)重復(fù)搜索了很多狀態(tài)，但總的訪問(wèn)狀態(tài)數(shù)和最后一次訪問(wèn)狀態(tài)數(shù)是同一數(shù)量級(jí)的旭绒。

4.6 分治

4.6.1 核心思想

1. 分治：將問(wèn)題劃分為更小規(guī)模的子問(wèn)題鸟妙，遞歸解決子問(wèn)題，再將結(jié)果合并從而高效解決問(wèn)題挥吵。
2. 數(shù)列上的分治：每次遞歸數(shù)列長(zhǎng)度減半重父，合并時(shí)除將子問(wèn)題的情況合并外，還需要考慮左右兩個(gè)子數(shù)列交互問(wèn)題蔫劣。通常需要在遞歸時(shí)坪郭，維護(hù)數(shù)列狀態(tài)，如排序或某些統(tǒng)計(jì)值大小脉幢。
3. 樹(shù)上的分治：樹(shù)的重心是指刪除該頂點(diǎn)后最大子樹(shù)頂點(diǎn)數(shù)最小的點(diǎn)歪沃。通過(guò)樹(shù)的重心來(lái)分解樹(shù)，可以避免分解不均勻?qū)е碌耐嘶F(xiàn)象嫌松。按重心分割沪曙，可以保證，每次劃分后子樹(shù)的大小都不超過(guò)n/2萎羔，所以遞歸深度不超過(guò)O(logn)液走。
4. 平面上的分治：將待求解平面按x或y坐標(biāo)分為兩部分，各子問(wèn)題遞歸求解贾陷，再合并缘眶。對(duì)于兩子平面交互的部分，通乘璺希可以通過(guò)一些限制條件巷懈，只考慮有可能達(dá)到最優(yōu)解的一些狀態(tài)，可以極大降低復(fù)雜度慌洪。

4.6.2 優(yōu)化細(xì)節(jié)

1. 樹(shù)的遞歸：遞歸分解無(wú)根樹(shù)時(shí)顶燕，可以代入兩個(gè)參數(shù)，當(dāng)前節(jié)點(diǎn)及父節(jié)點(diǎn)冈爹。在更新當(dāng)前節(jié)點(diǎn)時(shí)涌攻，其所有相連頂點(diǎn)中，除去父節(jié)點(diǎn)及已被分解出去的子樹(shù)根節(jié)點(diǎn)频伤，其余就是可以繼續(xù)遞歸的子節(jié)點(diǎn)恳谎。

4.7 字符串

4.7.1 核心思想

1. KMP：通過(guò)DP計(jì)算next數(shù)組，next[i]表示以模式串的第i個(gè)字符結(jié)尾的后綴與模式串前綴的最長(zhǎng)公共子串中憋肖，公共子串結(jié)尾的位置因痛。當(dāng)模式串與母串進(jìn)行匹配時(shí)，若發(fā)生字符不匹配的情況瞬哼，可以將母串指針位置保持不變婚肆，將模式串的指針前移至next位置的后一個(gè)字符，若依然不等坐慰，遞歸next直到相等或者超出模式串頭较性。復(fù)雜度O(m+n)。
2. Trie：樹(shù)上的邊對(duì)應(yīng)字符结胀，從根到節(jié)點(diǎn)的路徑上的字符序列即為該節(jié)點(diǎn)表示的字符串赞咙。Trie是一個(gè)高效維護(hù)字符串集合的數(shù)據(jù)結(jié)構(gòu)，查找長(zhǎng)度為l的字符串復(fù)雜度為O(l)糟港，同時(shí)節(jié)約空間攀操。
3. AC自動(dòng)機(jī)：又叫Aho-Corasick算法，將多個(gè)模式串的所有前綴用Trie表示秸抚，再在Trie上進(jìn)行KMP速和。
4. Robin-Carp哈希：將字符串看作b進(jìn)制數(shù)歹垫，循環(huán)移動(dòng)頭尾，可以得到每個(gè)串的哈希結(jié)果颠放，用來(lái)判斷兩字符串是否匹配排惨。可推廣到二維情況的哈希算法碰凶。
5. 后綴數(shù)組（SA）：將字符串的所有后綴按字典序排列后得到的數(shù)組暮芭，sa[i]表示排名第i的后綴的起始位置，rank[i]表示其實(shí)位置為i的后綴的排名欲低。利用倍增的思想辕宏，可以在log(n(logn)^2)時(shí)間內(nèi)得到后綴數(shù)組。通過(guò)計(jì)算得到的長(zhǎng)度為k的所有后綴及其排名砾莱，利用rank[i]和rank[i+2]組合得到長(zhǎng)度為2k的后綴及排名瑞筐。
6. 高度數(shù)組（LCP）：后綴數(shù)組中兩個(gè)相鄰后綴的最長(zhǎng)公共前綴。由于h[i-1]≥h[i]-1恤磷，可以從左到右遍歷后綴頭的位置面哼，通過(guò)尺取法，在O(n)時(shí)間內(nèi)求得扫步。由于高度數(shù)組的傳遞性魔策，結(jié)合RMQ，可以求得任意兩個(gè)后綴間的最長(zhǎng)前綴河胎。

4.7.2 經(jīng)典模型

1. 串的狀態(tài)轉(zhuǎn)移：KMP／AC自動(dòng)機(jī)
2. 單字符串匹配：KMP／Robin-Carp哈希
3. 多字符串匹配：Robin-Carp哈希／AC自動(dòng)機(jī)／SA+二分搜索／擴(kuò)展KMP
4. 最長(zhǎng)公共子串：strcat+SA+LCP+RMQ
5. 最長(zhǎng)回文子串：strcat+SA+LCP+RMQ／Manacher

轉(zhuǎn)載前請(qǐng)私信