NOIP複賽知識點簡述

全國青少年信息學奧林匹克聯賽（National Olympiad in Informatics in Provinces，簡稱NOIP）

轉眼已到了下半年，馬上将迎來一場重要的比賽——NOIP。

考前趕緊來總結一下一些必要的知識點。

普及組必學

1、模拟算法（暴力枚舉），按照題目的要求，題目怎麼說就怎麼做，保證時間和正确性即可。

2、搜索與回溯，主要的是DFS（深度優先搜索）和BFS（寬度優先搜索），基本沒有直接的暴力搜索。一般是記憶化搜索加剪枝，普及組第三題難度。

3、簡單操作：如篩法、前綴和、快速幂、高精度、輾轉相除法等，掌握全面即可應對大部分處理數據上的問題。

4、隊列（單調隊列）、棧、堆、鍊表等基礎數據結構。

5、簡單二分和分治（快速排序，歸并排序）。

6、貪心，要保證貪心的正确性，如果無法證明也可以用來騙分。

7、數學知識、公式計算，要點在于公式的化簡與變形，經過反複操作後也許就能得出重要結論。

8、簡單的動态規劃，容易推出狀态轉移方程，要注意初值與計算邊界條件。

9、字符串基本操作，插入、删除、查找等。

10、經典例題變形加深：八皇後、馬的走法、背包問題等。

提高組必學

0、普及組的10條。

1、較難的動态規劃，多維的狀态，轉移方式較多。

2、簡單數論，如擴展GCD，歐拉函數等。

3、進階算法：倍增，并查集，差分約束、拓撲排序，排列組合數，逆元，哈希。

4、最短路問題，需要掌握弗洛伊德算法、SPFA算法、dijkstra算法，以及它們對應的優化，再根據題目實際要求進行變形，用同樣模闆達到各種不一樣的效果。

5、最小生成樹問題，主要的兩種算法為Prim和Kruskal，同樣要加上對應的優化，再根據題目進行變形，以滿足題目的實際要求。

6、二分圖染色、二分圖匹配，一般題目都隐藏得很深，需要找到題目的本質，才能發現正确的解法。

7、強連通分量Tarjan，最近公共祖先LCA。

8、數據結構：線段樹、字典樹、主席樹、樹狀數組等。

9、樹的更多操作：樹鍊剖分、樹的直徑、樹的重心等。

10、字符串操作：KMP等。

更多拓展

大部分是省賽内容，如果想NOIP取得好成績的話，挑一些簡單的學習一下吧！

搜索：

啟發式搜索（A*）

叠代加深

IDA*

随機化搜索

圖論：

網絡流

仙人掌算法

樹：

平衡樹

樹套樹

圓方樹

線段樹合并

數學：

容斥原理

莫比烏斯反演

中國剩餘定理

歐拉定理

矩陣乘法

FFT

博弈論相關

計算幾何

字符串：

字符串哈希

AC自動機

後綴數組

後綴自動機

回文自動機

manacher

面對這些算法與數據結構，你是不是已經手足無措了呢？那就趕緊來學習吧！

相互學習，相互進步，加油！

定期推送帳号信息學新聞，競賽自主招生，信息學專業知識，信息學疑難解答，信息學訓練營信息等諸多優質内容的wx公衆平台noipnoi

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!