[原文鏈接]http://www.coderspace.net/bbs/viewthread.php?tid=119&extra=page%3D1
看了這份非官方的NOIp大綱,還是弱不禁風.不過分治、貪心似乎被無視了.
目前指熟練掌握了1/3,還有近1/2的部分不熟練,聯想起"不要總想著AC",需要大量做題了.
排序:
(1,5)冒泡/選排(這個很常用,一定要保證正確性)
(2,5)快排(Pascal選手可以去FPC文件夾里找代碼,C/C++選手注意sort的正確性)
(3,4)歸并排序(最好要會,因為有可能有題要卡快排)
數據結構:
(2,2)循環隊列(節省空間用)
(2,4)單調隊列(DP里經常用)
(1,3)完全二叉樹的數組存儲
(2,5)并查集(一定要會路徑壓縮)
(3,4)圖的前向星存法
(4,2)Trie樹,后綴數組(這些學過的就再復習一下,沒學過就不用看了,估計考的概率不大)
(3,2)森林轉二叉樹(樹狀DP常用)
動態規劃:
(1,5)基本的背包問題(一定要熟練寫出方程,尤其注意邊界的取值)
(3,4)多線程DP(二取方格數)
(3,2)LIS的二分優化
(2,4)DP的隊列優化(LCIS,單調隊列很常用的)
(3,4)樹狀DP(其實就是記憶化搜索,很好理解)
圖論:
(1,5)最短路(dijkstra,floyd,spfa)
(2,5)最小生成樹(prim,kruskal)
(2,5)拓撲排序
(2,3)floyd求最小環
(3,4)求(有向/無向)圖的強連通分量
(1,3)判斷圖中是否有環
(3,2)圖的關鍵路徑
(4,1)差分約束系統(就是求最長路,用spfa)
其他:
(2,4)RMQ問題的ST算法(LCA問題也可以轉化為RMQ問題)
(4,5)高精度的加減乘除開方(開方一般情況下直接二分比較方便)
(3,4)表達式求值(棧或并查集皆可,一般來說并查集比較容易實現)
(2,2)擴展歐幾里得算法(解同余方程用)
(1,5)乘法轉加法神器:log
(1,4)求最大子序列和的備忘錄算法
(2,3)位運算優化搜索(N皇后問題,建議去USACO做一下)
(4,2)搜索剪枝(推薦做USACO的fence rail那題)