NOIP競(jìng)賽復(fù)習(xí)重點(diǎn)歸納總結(jié)模逆元（求a的逆元，即a×x≡1modm）：當(dāng)m為質(zhì)數(shù)時(shí)，逆元為`qpow(a,m-2,m)`（費(fèi)馬小定理）。（五）圖論：最短路徑、最小生成樹(shù)與拓?fù)渑判?.最短路徑Dijkstra算法（非負(fù)權(quán)圖）：用優(yōu)先隊(duì)列優(yōu)化，時(shí)間復(fù)雜度O(mlogn)。Floyd算法（多源最短路徑）：時(shí)間復(fù)雜度O(n3)，適合小圖。SPFA（處理負(fù)權(quán)邊）：隊(duì)列優(yōu)化的Bellman-Ford算法，時(shí)間復(fù)雜度O(mn)（最壞情況）。2.最小生成樹(shù)Kruskal算法（按邊權(quán)排序，用并查集判斷環(huán)）：適合稀疏圖。Prim算法（按頂點(diǎn)擴(kuò)展，用優(yōu)先隊(duì)列優(yōu)化）：適合稠密圖。3.拓?fù)渑判騅ahn算法（入度表+隊(duì)列）：用于有向無(wú)環(huán)圖（DAG）的排序，判斷是否有環(huán)。三、問(wèn)題類(lèi)型：分類(lèi)解題思路總結(jié)NOIP的題目可分為模擬、枚舉、遞推、分治等類(lèi)型，以下是解題思路：（一）模擬題：細(xì)節(jié)處理與邊界條件特點(diǎn)：按題目描述模擬過(guò)程（如游戲、流程）。技巧：仔細(xì)讀題，明確每一步的操作。處理邊界條件（如起始、結(jié)束狀態(tài)）。用變量記錄中間狀態(tài)（如當(dāng)前位置、分?jǐn)?shù)）。例：NOIP2018普及組《標(biāo)題統(tǒng)計(jì)》（統(tǒng)計(jì)字符串中的標(biāo)題字?jǐn)?shù)）。（二）枚舉題：剪枝技巧與范圍優(yōu)化特點(diǎn)：遍歷所有可能的情況（如暴力枚舉、枚舉子集）。技巧：剪枝（如排除不可能的情況，減少遍歷次數(shù)）。優(yōu)化枚舉順序（如從大到小枚舉，提前找到答案）。例：NOIP2017普及組《跳房子》（枚舉跳躍距離）。（三）遞推與分治：從子問(wèn)題到全局遞推：找到遞推關(guān)系（如斐波那契數(shù)列：`f(n)=f(n-1)+f(n-2)`），用迭代實(shí)現(xiàn)（避免遞歸棧溢出）。分治：將問(wèn)題分解為子問(wèn)題（如歸并排序：分解為兩個(gè)子數(shù)組，排序后合并），用遞歸或迭代實(shí)現(xiàn)。（四）二分答案：最大化最小值與最小化最大值特點(diǎn)：?jiǎn)栴}要求“最大的最小值”或“最小的最大值”（如跳石頭問(wèn)題）。思路：二分答案（如假設(shè)答案為mid）。判斷mid是否可行（如是否能移除不超過(guò)m個(gè)石頭）。調(diào)整二分范圍（如mid可行，則嘗試更大的答案；否則嘗試更小的答案）。例：NOIP2012提高組《跳石頭》（二分最小距離）。四、應(yīng)試技巧：考場(chǎng)策略與調(diào)試方法（一）時(shí)間管理讀題：每道題讀2-3遍，明確題意（如輸入輸出格式、數(shù)據(jù)范圍）。思考：先想思路（如動(dòng)態(tài)規(guī)劃的狀態(tài)定義、圖論的算法選擇），再寫(xiě)代碼。編碼：按思路寫(xiě)代碼，避免邊想邊寫(xiě)（容易出錯(cuò)）。調(diào)試：留足夠時(shí)間調(diào)試（如每道題留15-30分鐘）。（二）調(diào)試技巧輸出中間結(jié)果：如輸出變量的值（如`cout<<"x:"<<x<<endl;`），判斷是否符合預(yù)期。使用斷點(diǎn)：如果允許（如本地調(diào)試），用斷點(diǎn)逐步執(zhí)行代碼（查看變量的值）。檢查邏輯錯(cuò)誤：如循環(huán)條件（是否多走了一步）、變量初始化（是否為0）。（三）代碼規(guī)范變量命名：用有意義的名字（如`n`表示數(shù)量，`a`數(shù)組表示數(shù)據(jù)）。代碼縮進(jìn)：用4個(gè)空格或Tab（保持代碼清晰）。注釋?zhuān)宏P(guān)鍵部分加注釋?zhuān)ㄈ鐮顟B(tài)轉(zhuǎn)移方程的含義）。避免冗余：重復(fù)的代碼提取為函數(shù)（如輸入函數(shù)、輸出函數(shù)）。五、復(fù)習(xí)規(guī)劃：從基礎(chǔ)到?jīng)_刺的階段建議（一）基礎(chǔ)階段（1-2個(gè)月）目標(biāo)：鞏固C++語(yǔ)法，學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)（數(shù)組、棧、隊(duì)列、并查集、線(xiàn)段樹(shù)、樹(shù)狀數(shù)組）。任務(wù)：完成洛谷的入門(mén)題（如《HelloWorld》、《變量定義》）。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)（如并查集、線(xiàn)段樹(shù)）。做普及組真題（如NOIP2020普及組《排水系統(tǒng)》）。（二）提升階段（2-3個(gè)月）目標(biāo)：學(xué)習(xí)核心算法（動(dòng)態(tài)規(guī)劃、貪心、數(shù)論、圖論），提高解題能力。任務(wù)：學(xué)習(xí)算法的理論知識(shí)（如動(dòng)態(tài)規(guī)劃的狀態(tài)定義）。做提高組真題（如NOIP2019提高組《樹(shù)的重心》）?？偨Y(jié)解題思路（如動(dòng)態(tài)規(guī)劃的常見(jiàn)類(lèi)型）。（三）沖刺階段（1個(gè)月）目標(biāo)：適應(yīng)考試節(jié)奏，提高解題速度，查漏補(bǔ)缺。任務(wù)：做模擬題（如洛谷的NOIP模擬賽、?？偷腘OIP模擬賽）。總結(jié)錯(cuò)題（如整數(shù)溢出、數(shù)組越界）。調(diào)整心態(tài)（保持冷靜，避免緊張）。六、總結(jié)NOIP競(jìng)賽的復(fù)習(xí)需要系統(tǒng)、全面，注重基礎(chǔ)和技巧的結(jié)合。關(guān)鍵在于：掌握C++的核心語(yǔ)法和STL的使用。熟練掌握數(shù)據(jù)結(jié)構(gòu)（并查集、線(xiàn)段樹(shù)、樹(shù)