寫在前面

• 隨著四月的到來, 離省選越來越近了.
• 從NOIP到現(xiàn)在, 學(xué)到了很多很多東西, 有的學(xué)的比較深入, 有的只是略知一二
• 從明天開始, 進(jìn)行針對省選的算法復(fù)習(xí)計(jì)劃. 省選前完成.
• 重點(diǎn)是對算法的理解和應(yīng)用, 還會注重模板習(xí)慣的養(yǎng)成

計(jì)劃內(nèi)容
1.?數(shù)據(jù)結(jié)構(gòu)

• 一直覺得我數(shù)據(jù)結(jié)構(gòu)學(xué)的還可以, 不過列出來發(fā)現(xiàn)會的也沒多少.
• 少就少吧, 省選夠用就行...

• 線段樹
• 樹狀數(shù)組
• 并查集
• 哈希表
• STL
• treap
• splay
• 樹鏈剖分
• 主席樹(可忽略)
• 字符串(KMP, 后綴數(shù)組)

2. 圖論

• 掌握經(jīng)典的算法, 并會應(yīng)用是重點(diǎn)
• 經(jīng)常和動態(tài)規(guī)劃結(jié)合

• 最短路(Floyed, 堆優(yōu)化dijkstra, SPFA)
• 最小生成樹(Prim, Kruskal), 以及生成樹相關(guān)
• 強(qiáng)連通分量(Tarjan)
• 拓?fù)渑判?/span>
• 歐拉路徑和哈密爾頓環(huán)
• 橋和關(guān)鍵路徑
• 二分圖
• 其他(2-SAT, Floyed判圈)

3. 網(wǎng)絡(luò)流

• 算法是基礎(chǔ), 建模是關(guān)鍵
• 多看原來做過的題目, 總結(jié)建模方法

• 最大流, 最小割(Dinic)
• 費(fèi)用流(SPFA)
• 上下界網(wǎng)絡(luò)流
• 弄清時間復(fù)雜度...

4. 數(shù)學(xué)

• 東西很多, 基本上都在訓(xùn)練指南上有
• 我數(shù)學(xué)不好, 所以會幾個基礎(chǔ)算法然后考試暴力吧.

• 歸納法
• gcd
• 篩法求素?cái)?shù)
• 普通歐拉函數(shù), 篩法求歐拉函數(shù)
• 逆元(歐拉函數(shù), 擴(kuò)展歐幾里得), 預(yù)處理逆元
• 容斥原理
• 解線性模方程
• 離散對數(shù)(BSGS)
• 中國剩余定理
• 組合數(shù), 盧卡斯定理
• 莫比烏斯函數(shù)
• 矩陣乘法(循環(huán)矩陣)

5. 搜索

• 可能到時候就搜索可以用上
• 然而我搜索練得少...

• dfs
• bfs
• A*
• IDA*
• 啟發(fā)式dfs
• 雙向dfs
• 雙向bfs
• 記憶化搜索

6. 動態(tài)規(guī)劃

• 最好是想出動態(tài)規(guī)劃的方法來
• 能否用動態(tài)規(guī)劃關(guān)鍵是看有無后效性和有無重疊子問題
• 但有時看上去有后效性的問題可以轉(zhuǎn)化成沒有后效性
• 什么優(yōu)化的就看著來了
• 基本上不加優(yōu)化部分分可能也能拿到少許

• 棋盤型動態(tài)規(guī)劃
• 序列型動態(tài)規(guī)劃
• 背包型動態(tài)規(guī)劃
  
• 區(qū)間型動態(tài)規(guī)劃
  
• 劃分型動態(tài)規(guī)劃
  
• 路徑型動態(tài)規(guī)劃
• 樹型動態(tài)規(guī)劃
• 狀態(tài)壓縮動態(tài)規(guī)劃
• 基于連通性的動態(tài)規(guī)劃
• 斜率優(yōu)化, 單調(diào)性優(yōu)化, 凸殼(都不會)

7. 分治

• 效率極高, 但一般想不到, 思路比較怪異
• 如果滿足離線要求往往很BT

• 逆序?qū)?/span>
• 二分, 三分
• CDQ分治
• 整體二分

8. 貪心

• 發(fā)現(xiàn)從NOIP以來我還沒有做過一道貪心的題目
• 但是思想很重要

• 擬陣很神(就是沒看懂)

9. 群論

• 掌握的不好

• Burnside引理
• Polya定理

10. 離散化

• 找過一般方法, 應(yīng)該能應(yīng)對一些題目

11. 計(jì)算幾何

• 發(fā)現(xiàn)竟然忘了計(jì)算幾何
• 注意不要去死記, 訓(xùn)練指南上的代碼普適性好但還要因題而異, 有可能有更簡單的方法
• 有時看不出是計(jì)算幾何但是可以轉(zhuǎn)化成計(jì)算幾何的題目, 比如半平面交之類的

• 基本知識(差積、點(diǎn)積)
• 凸包
• 多邊形
• 旋轉(zhuǎn)卡殼
• 半平面交

12. 暴力技巧(亂搞)

• 同樣是暴力, 有的人20分有的人就能40分.
• 暴力也有技巧, 而且不一定學(xué)的算法多暴力寫的就好, 往往思維活躍的人暴力寫得好(Orz wxjlzbcd)
• 大膽猜測不失為一種好辦法.

總結(jié)

以上是生活随笔為你收集整理的算法复习计划的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。