ACM培訓(xùn)資料數(shù)據(jù)結(jié)構(gòu)與算法

ACM培訓(xùn)資料數(shù)據(jù)結(jié)構(gòu)與算法從基礎(chǔ)到進(jìn)階的完整競(jìng)賽知識(shí)體系Contents課程目錄算法競(jìng)賽核心知識(shí)體系，從基礎(chǔ)到進(jìn)階的完整學(xué)習(xí)路徑。01基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)體系02算法設(shè)計(jì)五大范式03圖論算法深入04數(shù)學(xué)與數(shù)論基礎(chǔ)05字符串處理技術(shù)06復(fù)雜度分析與競(jìng)賽策略Chapter01基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)體系線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)與哈希集合的核心原理與應(yīng)用場(chǎng)景DATASTRUCTURES線性結(jié)構(gòu)：數(shù)組、鏈表、棧與隊(duì)列線性結(jié)構(gòu)是算法競(jìng)賽的基石。數(shù)組與鏈表構(gòu)成存儲(chǔ)基礎(chǔ)，棧與隊(duì)列提供特定的訪問(wèn)約束，而單調(diào)棧、雙端隊(duì)列等變體則將基礎(chǔ)結(jié)構(gòu)升級(jí)為高效的競(jìng)賽武器，理解其本質(zhì)差異與適用場(chǎng)景是解題的第一步。01數(shù)組支持O(1)隨機(jī)訪問(wèn)但插入刪除需O(n)，適合頻繁查詢場(chǎng)景；鏈表插入刪除O(1)但訪問(wèn)需O(n)，適合動(dòng)態(tài)增刪場(chǎng)景O(1)訪問(wèn)02棧的LIFO特性在表達(dá)式求值、括號(hào)匹配、函數(shù)調(diào)用模擬中不可或缺，是DFS遞歸的隱式載體LIFO03隊(duì)列的FIFO特性是BFS的核心數(shù)據(jù)結(jié)構(gòu)，循環(huán)隊(duì)列通過(guò)取模運(yùn)算避免空間浪費(fèi)，實(shí)現(xiàn)O(1)入隊(duì)出隊(duì)FIFO04單調(diào)棧維護(hù)遞增/遞減序列，可在O(n)時(shí)間內(nèi)解決"下一個(gè)更大元素"和"最大矩形面積"等經(jīng)典問(wèn)題O(n)05雙端隊(duì)列（Deque）支持兩端O(1)操作，是滑動(dòng)窗口最優(yōu)化和單調(diào)隊(duì)列DP的基礎(chǔ)工具DequeDataStructures樹(shù)形結(jié)構(gòu)：二叉樹(shù)、堆與線段樹(shù)樹(shù)形結(jié)構(gòu)從二叉樹(shù)遍歷到線段樹(shù)區(qū)間操作，構(gòu)成了競(jìng)賽中最豐富的工具庫(kù)。掌握這些結(jié)構(gòu)能覆蓋競(jìng)賽中60%以上的數(shù)據(jù)結(jié)構(gòu)題。二叉樹(shù)遍歷前序、中序、后序遍歷是遞歸思維的入口，BST支持O(logn)查找、插入和刪除操作O(logn)堆與優(yōu)先隊(duì)列O(logn)內(nèi)維護(hù)最值元素，Dijkstra最短路徑、Huffman編碼與Top-K問(wèn)題的核心結(jié)構(gòu)Top-K線段樹(shù)支持區(qū)間查詢與修改，配合懶標(biāo)記可處理區(qū)間加法、區(qū)間賦值等批量操作LazyTag樹(shù)狀數(shù)組代碼僅十余行，支持單點(diǎn)修改和前綴查詢，適合逆序?qū)Φ冉y(tǒng)計(jì)問(wèn)題BITAVL與紅黑樹(shù)通過(guò)旋轉(zhuǎn)操作保持平衡，需理解平衡因子和顏色約束的設(shè)計(jì)思想平衡因子DataStructures·算法競(jìng)賽哈希表與集合：O(1)查找的實(shí)現(xiàn)與優(yōu)化哈希表通過(guò)散列函數(shù)將鍵映射到桶中，實(shí)現(xiàn)平均O(1)的查找效率。在競(jìng)賽中，合理選擇哈希策略和沖突解決方案，以及善用STL容器，是處理計(jì)數(shù)、去重、快速查找問(wèn)題的關(guān)鍵技能。沖突解決策略鏈地址法將沖突元素鏈接為鏈表，實(shí)現(xiàn)簡(jiǎn)單且對(duì)裝載因子不敏感；開(kāi)放尋址法通過(guò)線性探測(cè)或二次探測(cè)尋找空位，空間效率更優(yōu)鏈地址法STL容器選型unordered_map平均查找O(1)但最差O(n)，map基于紅黑樹(shù)查找O(logn)但自帶排序，需根據(jù)場(chǎng)景選擇O(1)vsO(logn)HashKill防御競(jìng)賽中哈希碰撞可被對(duì)手惡意構(gòu)造數(shù)據(jù)攻擊，采用隨機(jī)化種子或雙哈希策略可有效防御雙哈希有序集合維護(hù)set和multiset基于紅黑樹(shù)實(shí)現(xiàn)有序集合維護(hù)，支持O(logn)的插入、刪除和二分查找，適用于動(dòng)態(tài)維護(hù)排名問(wèn)題紅黑樹(shù)Chapter02算法設(shè)計(jì)五大范式暴力枚舉、分治、貪心、動(dòng)態(tài)規(guī)劃與回溯的思想精髓ALGORITHMFUNDAMENTALS暴力枚舉與分治算法暴力枚舉通過(guò)窮舉所有可能解來(lái)尋找答案，雖然復(fù)雜度較高但思路清晰，常作為驗(yàn)證工具；分治算法將問(wèn)題分解為獨(dú)立子問(wèn)題分別求解再合并，體現(xiàn)了"化繁為簡(jiǎn)"的設(shè)計(jì)哲學(xué)。暴力枚舉窮舉所有可能解，適用于解空間較小的問(wèn)題，常作為復(fù)雜算法正確性的驗(yàn)證基準(zhǔn)n≤20優(yōu)化枚舉關(guān)鍵在于縮小搜索空間：位運(yùn)算枚舉子集與全排列生成是兩種核心實(shí)現(xiàn)方式O(2?)分治流程遵循"分解→解決→合并"三步流程，要求子問(wèn)題相互獨(dú)立且與原問(wèn)題結(jié)構(gòu)相同化繁為簡(jiǎn)歸并排序通過(guò)分治實(shí)現(xiàn)穩(wěn)定排序，合并過(guò)程可復(fù)用于求逆序?qū)Α^(qū)間和等擴(kuò)展問(wèn)題O(nlogn)快速冪利用分治將冪運(yùn)算大幅優(yōu)化，結(jié)合取模運(yùn)算是數(shù)論題的基礎(chǔ)模板O(logn)AlgorithmDesign貪心算法：局部最優(yōu)到全局最優(yōu)貪心算法在每一步選擇當(dāng)前狀態(tài)下的局部最優(yōu)解，期望通過(guò)一系列局部最優(yōu)達(dá)到全局最優(yōu)。其核心挑戰(zhàn)在于正確性證明——必須嚴(yán)格論證局部最優(yōu)選擇的累積不會(huì)導(dǎo)致全局次優(yōu)，交換論證法和反證法是最常用的證明手段。正確性證明策略交換論證法假設(shè)存在更優(yōu)解并推導(dǎo)出矛盾，反證法證明偏離貪心選擇必然導(dǎo)致更差結(jié)果。兩種方法共同構(gòu)成貪心算法正確性的嚴(yán)謹(jǐn)數(shù)學(xué)基礎(chǔ)。ExchangeArgumentContradictionProofStrategy區(qū)間調(diào)度問(wèn)題按結(jié)束時(shí)間升序排序后貪心選擇不重疊區(qū)間，可證明該策略得到的區(qū)間數(shù)量是全局最優(yōu)的。每次選擇結(jié)束最早的區(qū)間，為后續(xù)選擇留下最大空間。EarliestFinishMaxCompatible結(jié)束時(shí)間優(yōu)先Huffman編碼每次合并頻率最小的兩個(gè)節(jié)點(diǎn)構(gòu)建最優(yōu)前綴碼，貪心策略保證了編碼總長(zhǎng)度最小。高頻字符獲得短編碼，低頻字符獲得長(zhǎng)編碼，實(shí)現(xiàn)數(shù)據(jù)壓縮最優(yōu)。MergeLowestMinTotalBits最優(yōu)前綴碼活動(dòng)安排與任務(wù)調(diào)度按截止時(shí)間排序的貪心策略可最大化完成任務(wù)數(shù)量或最小化最大延遲。適用于資源受限場(chǎng)景下的多任務(wù)最優(yōu)調(diào)度決策。DeadlineOrderMinLateness截止時(shí)間優(yōu)先AlgorithmDesign動(dòng)態(tài)規(guī)劃：狀態(tài)設(shè)計(jì)與轉(zhuǎn)移方程動(dòng)態(tài)規(guī)劃通過(guò)將問(wèn)題分解為重疊子問(wèn)題并存儲(chǔ)子問(wèn)題解來(lái)避免重復(fù)計(jì)算，其核心在于狀態(tài)定義、轉(zhuǎn)移方程和邊界條件三要素。01DP三要素缺一不可：狀態(tài)定義決定問(wèn)題刻畫(huà)方式，轉(zhuǎn)移方程描述子問(wèn)題間的遞推關(guān)系，邊界條件確定遞歸終止點(diǎn)ThreePillars0201背包問(wèn)題：dp[i][j]表示前i個(gè)物品裝入容量j的背包的最大價(jià)值，轉(zhuǎn)移方程dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])0/1Knapsack03最長(zhǎng)公共子序列（LCS）：dp[i][j]表示s1前i個(gè)字符與s2前j個(gè)字符的LCS長(zhǎng)度，相同則+1否則取max(dp[i-1][j],dp[i][j-1])LCS04最長(zhǎng)上升子序列（LIS）：樸素DP為O(n2)，利用二分查找維護(hù)單調(diào)遞增數(shù)組可優(yōu)化至O(nlogn)LIS05記憶化搜索（自頂向下）與遞推（自底向上）是DP的兩種實(shí)現(xiàn)方式，前者代碼直觀，后者常數(shù)更小TwoModesAdvancedDP動(dòng)態(tài)規(guī)劃進(jìn)階：高級(jí)模型與優(yōu)化技巧進(jìn)階DP模型包括狀態(tài)壓縮DP、區(qū)間DP、樹(shù)形DP和數(shù)位DP等，每種模型對(duì)應(yīng)特定的問(wèn)題結(jié)構(gòu)。配合斜率優(yōu)化、單調(diào)隊(duì)列優(yōu)化等技巧，可將部分O(n2)的DP降至O(n)或O(nlogn)，是競(jìng)賽中沖擊高分的關(guān)鍵能力。狀態(tài)壓縮DP位運(yùn)算編碼子集狀態(tài)為整數(shù)，適用n≤20集合類(lèi)問(wèn)題O(n2·2?)區(qū)間DP處理合并區(qū)間類(lèi)問(wèn)題，按區(qū)間長(zhǎng)度遞增枚舉分割點(diǎn)dp[i][j]樹(shù)形DP在樹(shù)上定義狀態(tài)并自底向上轉(zhuǎn)移，處理樹(shù)結(jié)構(gòu)問(wèn)題最大獨(dú)立集數(shù)位DP記憶化搜索逐位確定，統(tǒng)計(jì)區(qū)間內(nèi)滿足條件的數(shù)字個(gè)數(shù)逐位確定斜率優(yōu)化轉(zhuǎn)移方程轉(zhuǎn)化為直線截距最值，單調(diào)隊(duì)列維護(hù)凸包O(n2)→O(n)ALGORITHM·BACKTRACKING回溯算法：系統(tǒng)試錯(cuò)與高效剪枝回溯算法通過(guò)深度優(yōu)先搜索在解空間樹(shù)中系統(tǒng)遍歷所有可能選擇，遇到不滿足約束的分支立即剪枝回退。回溯框架做出選擇→遞歸探索→撤銷(xiāo)選擇，通過(guò)遞歸實(shí)現(xiàn)解空間樹(shù)的深度優(yōu)先遍歷DFSTraverseN皇后問(wèn)題三個(gè)布爾數(shù)組分別記錄列、主對(duì)角線、副對(duì)角線占用狀態(tài)，O(1)判斷當(dāng)前位置合法性O(shè)(1)剪枝策略可行性剪枝：不滿足約束則跳過(guò)；最優(yōu)性剪枝：不可能優(yōu)于已知最優(yōu)解則跳過(guò)可行性+最優(yōu)性數(shù)獨(dú)求解回溯+約束傳播：預(yù)處理候選數(shù)字集合，每次選擇候選最少的空格填入以減少分支約束傳播GraphTheory·Fundamentals圖的表示與遍歷：DFS和BFS圖論算法的基礎(chǔ)在于正確的圖的表示和高效的遍歷。鄰接矩陣與鄰接表各有適用場(chǎng)景，DFS和BFS是圖論中最核心的兩種遍歷方式，分別對(duì)應(yīng)遞歸思維和層次思維，是后續(xù)所有高級(jí)圖論算法的基石。鄰接矩陣適合稠密圖（邊數(shù)接近n2），查詢?nèi)我鈨牲c(diǎn)間邊權(quán)僅需O(1)時(shí)間。但空間復(fù)雜度為O(n2)，當(dāng)頂點(diǎn)數(shù)n較大時(shí)內(nèi)存開(kāi)銷(xiāo)不可接受，競(jìng)賽中較少使用。?O(1)查詢·O(n2)空間鄰接表適合稀疏圖（邊數(shù)遠(yuǎn)小于n2），空間復(fù)雜度優(yōu)化至O(n+m)。遍歷鄰邊效率高，是算法競(jìng)賽中最常用的圖存儲(chǔ)方式，支持動(dòng)態(tài)加邊操作。??O(n+m)空間·競(jìng)賽首選DFS深度優(yōu)先遞歸實(shí)現(xiàn)簡(jiǎn)潔直觀，用于連通分量標(biāo)記、拓?fù)渑判颉⒏铧c(diǎn)橋判定、Tarjan強(qiáng)連通分量算法等。遞歸深度過(guò)大時(shí)需手動(dòng)模擬棧防止棧溢出。??Tarjan·拓?fù)渑判颉じ铧c(diǎn)橋BFS廣度優(yōu)先天然適合求無(wú)權(quán)圖最短路徑，按層次擴(kuò)展保證第一次到達(dá)即為最優(yōu)解。雙向BFS從起點(diǎn)終點(diǎn)同時(shí)擴(kuò)展，可將搜索空間從O(b^d)降至O(b^(d/2))。??最短路·雙向BFS優(yōu)化前向星按起點(diǎn)排序存儲(chǔ)所有邊的靜態(tài)數(shù)組結(jié)構(gòu)，遍歷效率高且內(nèi)存連續(xù)訪問(wèn)友好。適合大規(guī)模圖的存儲(chǔ)，常與鏈?zhǔn)角跋蛐桥浜蠈?shí)現(xiàn)高效圖算法。??邊集數(shù)組·內(nèi)存連續(xù)GraphAlgorithms最短路徑：Dijkstra、SPFA與Floyd最短路徑算法的選擇取決于圖的性質(zhì)和問(wèn)題需求：Dijkstra適用于非負(fù)權(quán)單源最短路，SPFA處理含負(fù)權(quán)邊的情況，F(xiàn)loyd解決全源最短路問(wèn)題。01Dijkstra基于貪心思想，每次選取距源點(diǎn)最近的未訪問(wèn)節(jié)點(diǎn)擴(kuò)展，配合優(yōu)先隊(duì)列，不適用于負(fù)權(quán)邊O(mlogn)02SPFABellman-Ford的隊(duì)列優(yōu)化，支持負(fù)權(quán)邊和負(fù)環(huán)檢測(cè)，競(jìng)賽中可能被特殊數(shù)據(jù)卡掉O(km)avg·O(nm)worst03Floyd-Warshall三重循環(huán)求所有點(diǎn)對(duì)最短路徑，適合n≤400的稠密圖，代碼僅五行O(n3)04第K短路反向圖Dijkstra加A*搜索，估價(jià)函數(shù)為當(dāng)前點(diǎn)到終點(diǎn)的最短距離A*Search05差分約束不等式約束轉(zhuǎn)化為圖的邊，用SPFA求最短路判定可行解或最優(yōu)解SPFA建模GraphAlgorithms最小生成樹(shù)與連通性分析最小生成樹(shù)用最小代價(jià)連接所有頂點(diǎn)，Kruskal和Prim分別從邊和點(diǎn)的角度貪心構(gòu)建。并查集是連通性維護(hù)的核心工具，Tarjan算法則通過(guò)一次DFS揭示圖的深層結(jié)構(gòu)——割點(diǎn)、橋和強(qiáng)連通分量，是理解圖連通性的關(guān)鍵。Kruskal按邊權(quán)升序排序后逐條加邊，用并查集判斷是否成環(huán)，適合稀疏圖，實(shí)現(xiàn)簡(jiǎn)單直觀O(mlogm)Prim從某頂點(diǎn)開(kāi)始逐步擴(kuò)展生成樹(shù)，用優(yōu)先隊(duì)列維護(hù)當(dāng)前最小邊，適合稠密圖，與Dijkstra思想相似O(mlogn)并查集支持合并與查詢操作，路徑壓縮加按秩合并使均攤復(fù)雜度近乎常數(shù)，是處理連通性問(wèn)題的利器O(α(n))Tarjan通過(guò)一次DFS計(jì)算dfn和low數(shù)組，可同時(shí)求出割點(diǎn)、橋與強(qiáng)連通分量，算法優(yōu)美高效O(n+m)拓?fù)渑判蛲ㄟ^(guò)計(jì)算入度逐步消除無(wú)依賴(lài)節(jié)點(diǎn)，可判斷有向圖是否有環(huán)，也是DAG上動(dòng)態(tài)規(guī)劃的預(yù)處理步驟O(n+m)GraphTheory·NetworkFlow網(wǎng)絡(luò)流：最大流、最小割與費(fèi)用流網(wǎng)絡(luò)流理論以最大流最小割定理為基石，將流量最大化問(wèn)題與容量最小割集等價(jià)。Dinic算法通過(guò)BFS分層和DFS找阻塞流高效求解，費(fèi)用流則在流量最優(yōu)的基礎(chǔ)上追求費(fèi)用最優(yōu)。競(jìng)賽難點(diǎn)在于將實(shí)際問(wèn)題抽象為網(wǎng)絡(luò)流模型。Dinic算法BFS構(gòu)建分層圖，DFS找阻塞流，復(fù)雜度O(V2E)，單位容量圖O(E√V)O(V2E)最小割最大流最大流等于最小割容量，求最大流后從源點(diǎn)可達(dá)頂點(diǎn)集即得最小割方案Max=Min最小費(fèi)用最大流增廣時(shí)選費(fèi)用最短路徑，SPFA代替BFS，Bellman-Ford處理負(fù)權(quán)反向邊SPFA二分圖匹配源點(diǎn)連左部、右部連匯點(diǎn)、容量均為1，最大流即最大匹配數(shù)Cap=1上下界網(wǎng)絡(luò)流引入附加源匯和流量平衡條件，將帶下界約束的流通問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)最大流BalanceGraphTheory·Matching二分圖匹配：匈牙利算法與KM算法二分圖匹配解決兩組元素之間的最優(yōu)配對(duì)問(wèn)題。匈牙利算法通過(guò)增廣路思想求最大基數(shù)匹配，KM算法在此基礎(chǔ)上引入頂標(biāo)機(jī)制求解最大權(quán)完美匹配。這些算法在任務(wù)分配、資源調(diào)度等場(chǎng)景中有著廣泛的實(shí)際應(yīng)用。01增廣路核心從未匹配點(diǎn)出發(fā)交替經(jīng)過(guò)未匹配邊和已匹配邊，找到增廣路后匹配數(shù)+1O(VE)02Hopcroft-Karp每輪BFS找到多條最短增廣路同時(shí)增廣，適合大規(guī)模二分圖O(E√V)03KM頂標(biāo)機(jī)制維護(hù)lx[i]+ly[j]≥w[i][j]不變式，在相等子圖中尋找完美匹配最大權(quán)匹配04K?nig定理最大獨(dú)立集=頂點(diǎn)總數(shù)?最大匹配數(shù)，最小點(diǎn)覆蓋=最大匹配數(shù)等價(jià)轉(zhuǎn)化05帶花樹(shù)算法將奇環(huán)縮為"花"轉(zhuǎn)化為二分圖匹配，處理一般圖最大匹配一般圖CHAPTER04數(shù)學(xué)與數(shù)論基礎(chǔ)素?cái)?shù)、模運(yùn)算、組合數(shù)學(xué)與計(jì)算幾何的核心工具COMPETITIVEMATH·NUMBERTHEORY數(shù)論基礎(chǔ)：素?cái)?shù)、GCD與模運(yùn)算數(shù)論工具在競(jìng)賽中使用頻率極高。素?cái)?shù)篩法快速生成素?cái)?shù)表，擴(kuò)展歐幾里得求解貝祖等式和逆元，快速冪處理大數(shù)模冪運(yùn)算。PRIMESIEVE素?cái)?shù)篩法埃氏篩O(nloglogn)從2開(kāi)始逐個(gè)標(biāo)記合數(shù)；歐拉篩O(n)保證每個(gè)合數(shù)僅被最小質(zhì)因子篩去一次，效率更高O(n)EXTENDEDGCD擴(kuò)展歐幾里得在求GCD的同時(shí)得到ax+by=gcd(a,b)的系數(shù)，可直接求模逆元和線性同余方程的解，是數(shù)論核心工具ax+by=gcdFASTPOWER快速冪利用二進(jìn)制分解將a?modp從O(n)優(yōu)化到O(logn)，處理大數(shù)冪運(yùn)算的標(biāo)準(zhǔn)模板，避免溢出O(logn)CRT中國(guó)剩余定理求解一元線性同余方程組，要求模數(shù)兩兩互質(zhì)；擴(kuò)展CRT可處理模數(shù)不互質(zhì)的情況，應(yīng)用廣泛互質(zhì)模數(shù)MATRIXPOWER矩陣快速冪將線性遞推從O(n)優(yōu)化到O(k3logn)，k為遞推階數(shù)。適用于斐波那契數(shù)列、線性動(dòng)態(tài)規(guī)劃等場(chǎng)景，是加速遞推計(jì)算的關(guān)鍵技術(shù)O(k3logn)SUMMARY工具總結(jié)這些工具看似簡(jiǎn)單，卻是組合計(jì)數(shù)、密碼學(xué)和矩陣快速冪等高級(jí)話題的基礎(chǔ)。掌握這些核心算法，能夠有效解決競(jìng)賽中的數(shù)論問(wèn)題，提升代碼效率與解題能力基礎(chǔ)·核心Combinatorics組合數(shù)學(xué)：計(jì)數(shù)原理與特殊數(shù)列組合數(shù)學(xué)解決計(jì)數(shù)問(wèn)題，從基礎(chǔ)的排列組合到容斥原理、卡特蘭數(shù)，構(gòu)成了一套完整的計(jì)數(shù)工具鏈。在模意義下計(jì)算組合數(shù)需要配合逆元和盧卡斯定理，是競(jìng)賽數(shù)論與DP交叉出題的熱點(diǎn)領(lǐng)域。01組合數(shù)：C(n,m)=n!/(m!(n-m)!)，模意義下計(jì)算需預(yù)處理階乘及其逆元，利用費(fèi)馬小定理或擴(kuò)展歐幾里得求逆。02容斥原理：|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|，處理"至少滿足一個(gè)條件"的計(jì)數(shù)問(wèn)題。03卡特蘭數(shù)：Cn=C(2n,n)/(n+1)，應(yīng)用于合法括號(hào)序列數(shù)、n個(gè)節(jié)點(diǎn)的BST數(shù)、凸多邊形三角剖分?jǐn)?shù)等場(chǎng)景。04盧卡斯定理：C(n,m)modp=C(n/p,m/p)·C(n%p,m%p)modp，適用于n、m很大但p較小（p為素?cái)?shù)）的情況。05錯(cuò)排公式：D(n)=(n-1)(D(n-1)+D(n-2))計(jì)算全錯(cuò)排列數(shù)，是容斥原理的經(jīng)典應(yīng)用。ComputationalGeometry計(jì)算幾何：基礎(chǔ)操作與凸包算法計(jì)算幾何以向量叉積為核心工具，精度控制是生命線。GrahamScan求凸包配合旋轉(zhuǎn)卡殼解決極值問(wèn)題。叉積與方向cross(P-A,B-A)的正負(fù)判斷點(diǎn)在線段的左、共線或右側(cè)。叉積模長(zhǎng)等于平行四邊形面積，是計(jì)算幾何中最基礎(chǔ)的方向判定工具。CrossProductGrahamScan極角排序后入棧，非左拐彈出棧頂構(gòu)建凸包，時(shí)間復(fù)雜度O(nlogn)。先找最左下點(diǎn)作為基準(zhǔn)，保證凸包頂點(diǎn)按逆時(shí)針順序輸出。O(nlogn)旋轉(zhuǎn)卡殼對(duì)踵點(diǎn)旋轉(zhuǎn)求直徑與最遠(yuǎn)點(diǎn)對(duì)，可求最小外接矩形。利用凸包的單調(diào)性，在凸包邊上滑動(dòng)兩條平行線，高效求解各類(lèi)極值問(wèn)題。RotatingCalipers半平面交逐步切割求公共區(qū)域，用于多邊形核與可行域。將半平面按極角排序后，用雙端隊(duì)列維護(hù)交集凸多邊形，復(fù)雜度O(nlogn)。Halfplane精度控制優(yōu)先longlong整數(shù)運(yùn)算避免浮點(diǎn)誤差；必須使用double時(shí)設(shè)eps=1e-8進(jìn)行模糊比較。叉積符號(hào)判斷是精度敏感的關(guān)鍵環(huán)節(jié)。eps=1e-8CHAPTER05字符串處理技術(shù)從KMP模式匹配到Trie樹(shù)與后綴數(shù)組的進(jìn)階之路StringAlgorithmsKMP算法與Trie字典樹(shù)KMP算法通過(guò)失配數(shù)組避免主串指針回溯，實(shí)現(xiàn)O(n+m)的單模式匹配；Trie樹(shù)將字符串按字符逐層展開(kāi)，支持O(L)的前綴查詢。KMP失配數(shù)組next[i]表示前i個(gè)字符的最長(zhǎng)相等前后綴長(zhǎng)度，匹配失敗時(shí)按next值跳轉(zhuǎn)而非回溯主串next[i]KMP復(fù)雜度總復(fù)雜度O(n+m)，n為主串、m為模式串長(zhǎng)度，可求模式串在主串中的所有出現(xiàn)位置O(n+m)Trie基本結(jié)構(gòu)每個(gè)節(jié)點(diǎn)代表一個(gè)字符，根到葉路徑構(gòu)成字符串，插入與查詢復(fù)雜度均為O(L)O(L)Trie擴(kuò)展應(yīng)用統(tǒng)計(jì)前綴出現(xiàn)次數(shù)、字符串去重、異或最大值查詢，以及AC自動(dòng)機(jī)的基礎(chǔ)結(jié)構(gòu)AC自動(dòng)機(jī)01-Trie整數(shù)按二進(jìn)制位從高位到低位插入，可在O(logMAX)內(nèi)查詢異或結(jié)果最大的數(shù)O(logMAX)STRINGALGORITHMSAC自動(dòng)機(jī)與后綴數(shù)組AC自動(dòng)機(jī)在Trie樹(shù)上疊加KMP的失配思想，實(shí)現(xiàn)多模式串同時(shí)匹配；后綴數(shù)組將字符串所有后綴排序，配合height數(shù)組提供強(qiáng)大的子串分析能力。Fail指針構(gòu)建在Trie樹(shù)上構(gòu)建fail指針，BFS逐層構(gòu)建，匹配時(shí)沿fail鏈跳轉(zhuǎn)O(n+Σm)多模式匹配應(yīng)用關(guān)鍵詞搜索、DNA序列匹配、敏感詞檢測(cè)，一次掃描完成一次掃描后綴數(shù)組構(gòu)建所有后綴按字典序排序，sa[i]為排名第i的后綴起始位置O(nlogn)Height數(shù)組相鄰排名后綴的最長(zhǎng)公共前綴，配合RMQ求任意LCPO(1)LCP經(jīng)典應(yīng)用場(chǎng)景最長(zhǎng)重復(fù)子串、回文子串、不同子串計(jì)數(shù)、周期檢測(cè)4類(lèi)問(wèn)題CHAPTER06復(fù)雜度分析與競(jìng)賽策略時(shí)間空間分析、常數(shù)優(yōu)化與比賽實(shí)戰(zhàn)技巧AlgorithmAnalysis復(fù)雜度分析：大O表示法與主定理復(fù)雜度分析用大O表示法描述算法的漸近性能，主定理為分治算法提供快速?gòu)?fù)雜度判定，均攤分析處理非均勻開(kāi)銷(xiāo)的數(shù)據(jù)結(jié)構(gòu)操作。大O表示法描述最壞情況下漸近增長(zhǎng)：O(1)<O(logn)<O(n)<O(n2)<O(2?)<O(n!)O(1)→O(n!)主定理分析T(n)=aT(n/b)+O(n?)遞推：比較log_b(a)與c得出漸近復(fù)雜度log_b(a)vsc均攤分析動(dòng)態(tài)數(shù)組擴(kuò)容均攤O(1)；并查集路徑壓縮均攤O(α(n))Amortized時(shí)間基準(zhǔn)1秒約10?次操作；n≤10?需O(nlogn)；n≤20可接受O(2?)10?/s空間復(fù)雜度int數(shù)組10?約40MB，競(jìng)賽限制256MB，需滾動(dòng)數(shù)組優(yōu)化≤256MBCompetitiveProgramming競(jìng)賽實(shí)戰(zhàn)技巧與優(yōu)化策略競(jìng)賽成績(jī)不僅取決于算法能力，還受工程實(shí)現(xiàn)、調(diào)