NOIP考點系統過濾

目錄

1. 圖論【搜尋】【樹】【圖的聯通】【二分圖】【歐拉圖】【拓撲序】【計算幾何】待更... ...
2. 技巧與思想
3. String
4. DP
5. 數論
6. 資料結構
7. 博弈論
8. 其他

一、圖論

1.搜尋

①雙向bfs

②dfs

③記憶化

• 一般說來，動态規劃總要周遊所有的狀态，而搜尋可以排除一些無效狀态。

• 更重要的是搜尋還可以剪枝，可能剪去大量不必要的狀态，是以在空間開銷上往往比動态規劃要低很多。 記憶化算法在求解的時候還是按着自頂向下的順序，但是每求解一個狀态，就将它的解儲存下來， 以後再次遇到這個狀态的時候，就不必重新求解了。 這種方法綜合了搜尋和動态規劃兩方面的優點，因而還是很有實用價值的。

• 搜尋相對于動态規劃最大的劣勢無非就是重複計算子結構，是以我們在搜尋的過程中，對于每一個子結構隻計算一次，之後儲存到數組裡，以後要用到的時候直接調用就可以了，這就是記憶化搜尋。

• 記憶化搜尋=搜尋的形式+動态規劃的思想

• http://blog.csdn.net/urecvbnkuhbh_54245df/article/details/5847876

• 可以用記憶化搜尋計算狀态轉移方程。不必事先确定各狀态的計算順序，但需要記錄每個狀态 “是否已經計算過”。 ———劉汝佳《算法競賽入門經典》

④疊代加深

• http://blog.csdn.net/u014800748/article/details/44998693
• http://blog.csdn.net/logo_fc/article/details/64541202

2.樹

①樹的重心和直徑

　　樹的重心

　樹的重心也叫樹的質心。對于一棵樹n個節點的無根樹，找到一個點，使得把樹變成以該點為根的有根樹時，最大子樹的結點樹最小。

　換句話說，删除這個點後最大連通塊（一定是樹）的結點數最小。

• http://blog.csdn.net/u013076044/article/details/45915745（樹的重心的性質以及具體實作代碼）

　　樹的直徑（樹上最長路）

• http://www.cnblogs.com/wuyiqi/archive/2012/04/08/2437424.html（樹的直徑的詳細證明）
• http://www.cnblogs.com/wuyiqi/archive/2012/03/10/2388501.html（實作代碼）

②dfs序

• http://blog.csdn.net/qq_24489717/article/details/50569644（詳解）

③樹鍊剖分

• http://blog.sina.com.cn/s/blog_6974c8b20100zc61.html

④LCA（http://www.cnblogs.com/JVxie/p/4854719.html）

在一棵沒有環的樹上，每個節點肯定有其父親節點和祖先節點，而最近公共祖先，就是兩個節點在這棵樹上深度最大的公共的祖先節點。

換句話說，就是兩個點在這棵樹上距離最近的公共祖先節點。

是以LCA主要是用來處理當兩個點僅有唯一一條确定的最短路徑時的路徑。

• 常用的求LCA的算法有：Tarjan/DFS+ST/倍增 （後兩個算法都是線上算法，也很相似，時間複雜度在O(logn)~O(nlogn)之間，較難了解吧~）
• 有的題目可以用線段樹來做，代碼量很大，時間複雜度也偏高，在O(n)~O(nlogn)之間，優點在于簡單粗暴

• Tarjan算法（離線）：
  • 在一次周遊中把所有詢問一次性解決，是以其時間複雜度是O(n+q)。優點在于相對穩定，時間複雜度也比較居中，也很容易了解
  • 基本思路：

　　　　　　1.任選一個點為根節點，從根節點開始。

　　　　　　2.周遊該點u所有子節點v，并标記這些子節點v已被通路過。

　　　　　　3.若是v還有子節點，傳回2，否則下一步。

　　　　　　4.合并v到u上。

　　　　　　5.尋找與目前點u有詢問關系的點v。

　　　　　　6.若是v已經被通路過了，則可以确認u和v的最近公共祖先為v被合并到的父親節點a。

　　　　　　周遊的話需要用到dfs來周遊(我相信來看的人都懂吧...)，至于合并，最優化的方式就是利用并查集來合并兩個節點。

⑤Prufer編碼和Cayley定理

•  http://www.matrix67.com/blog/archives/682

⑥Prim堆優化 [ O(nlogn) ]、Kruskal [ O(mlogm) ]

• 兩者差別

1. PRIM是稠密圖用的。KRUSKAL是稀疏圖用的。
2. prim針對點，kruskal針對邊。一般都是推薦kruskal加路徑壓縮的啟發式合并的并查集，prim加堆優化也不錯，隻是代碼長了點（stl另當别論）
3. 由于Kruskal裡面需要用到排序，是以，時間複雜度受到了排序的影響。而且，Kruskal算法又是從邊出發的，是以，如果邊的數量太多的話，必定會影響排序所用的時間。是以，如果邊的數量太多的話，最好是用Prim算法。相比較之下，Kruskal算法的代碼比Prim稍微短一點。至于穩定性嘛~~~好像沒什麼差別....

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　——————出自 noip吧 Prim和 Kruskal的差別

• http://www.cnblogs.com/biyeymyhjob/archive/2012/07/30/2615542.html

⑦分治

3、圖的聯通

強連通分量

有向圖強連通分量：在有向圖G中，如果兩個頂點vi,vj間（vi>vj）有一條從vi到vj的有向路徑，同時還有一條從vj到vi的有向路徑，則稱兩個頂點強連通(strongly connected)。如果有向圖G的每兩個頂點都強連通，稱G是一個強連通圖。有向圖的極大強連通子圖，稱為強連通分量(strongly connected components)。

•  當 DFN(u) = Low(u) 時，以u為根的搜尋子樹上所有節點是一個強連通分量。（對于 DFN 和 low 的解釋）
• Tarjan算法

4、二分圖

　　二分圖又稱作二部圖，是圖論中的一種特殊模型。 設G=(V,E)是一個無向圖，如果頂點V可分割為兩個互不相交的子集(A,B)，并且圖中的每條邊（i，j）所關聯的兩個頂點i和j分别屬于這兩個不同的頂點集(i in A,j in B)，則稱圖G為一個二分圖。

5、歐拉圖

歐拉圖是指通過圖（無向圖或有向圖）中所有邊且每邊僅通過一次通路，相應的回路稱為歐拉回路。

相關性質：

　　1.無向連通圖G是歐拉圖，當且僅當G不含奇數度結點(G的所有結點度數為偶數)；

　　2.無向 連通圖G含有歐拉通路，當且僅當G有零個或兩個 奇數度的結點；

　　3.有向連通圖D是歐拉圖，當且僅當該圖為連通圖且D中每個結點的入度=出度

　　4.有向連通圖D含有歐拉通路，當且僅當該圖為連通圖且D中除兩個結點外，其餘每個結點的入度=出度，且此兩點滿足deg－(u)－deg+(v)=±1。（起始點s的入度=出度-1，結束點t的出度=入度-1 或兩個點的入度=出度）

　　5.一個非平凡連通圖是歐拉圖當且僅當它的每條邊屬于奇數個環。

　　6.如果圖G是歐拉圖且 H = G - uv，則H有奇數個u,v-迹僅在最後通路v；同時，在這一序列的u,v-迹中，不是路徑的迹的條數是偶數。(Todia[1973])　　 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　-----------源自 百度百科

6、拓撲排序

7、計算幾何（先忽略這個）

二、技巧與思想

1、二分

2、離散化

• 什麼是離散化

3、位運算

4、分塊

5、數列差分以及字首和

6、哈夫曼編碼

7、cdq分治

8、啟發式合并

轉載于:https://www.cnblogs.com/ExileValley/p/7713779.html