CSP-S復(fù)習(xí)梳理

知識點(diǎn)復(fù)習(xí)

對于大型數(shù)據(jù)結(jié)構(gòu)一天復(fù)習(xí)1~2個(gè)，周一樹狀數(shù)組線段樹，周二ST表與單調(diào)棧與單調(diào)隊(duì)列，周三分塊，周四字典樹與可持久化數(shù)據(jù)結(jié)構(gòu)，周五堆與二叉搜索樹與平衡樹。
對于算法，一天復(fù)習(xí)1~2類，周一圖論，周二數(shù)論，周三搜索與倍增，周四動態(tài)規(guī)劃與貪心，周五二分三分模擬退火。

線段樹

感覺有可能考（主要是noip聯(lián)考一天至少1道線段樹），但我好像不是很會的樣子，要注重復(fù)習(xí)一下帶懶標(biāo)記的線段樹，以及什么問題可以轉(zhuǎn)化為線段樹問題，重中之重可能是掃描線。線段樹可以維護(hù)的平衡樹都可以。

樹狀數(shù)組

自我感覺不太可能考，一般應(yīng)用于求數(shù)點(diǎn)問題或快速統(tǒng)計(jì)問題，樹狀數(shù)組能解決的線段樹都可以，但樹狀數(shù)組常數(shù)很小約等于沒有。

ST表

感覺思路比較玄學(xué)，不是太能理解，但是考的概率還是有的，不帶修的用ST表的時(shí)間復(fù)雜度是比其他數(shù)據(jù)結(jié)構(gòu)都優(yōu)秀的。

單調(diào)數(shù)據(jù)結(jié)構(gòu)

一般思路都比較巧妙，或者用來優(yōu)化其他算法，但好像基本上一出就有很多暴力的部分分？

分塊

如果考場上想不到其他數(shù)據(jù)結(jié)構(gòu)來寫，可以考慮分塊，而且基本上是不會卡分塊的，好寫又好調(diào)，思路直觀，雖然時(shí)間復(fù)雜度是根號級別，但常數(shù)小，實(shí)際跑起來與線段樹差不多。

字典樹與可持久化數(shù)據(jù)結(jié)構(gòu)

感覺考的概率很小，可以考慮使用pbds庫，雖然常數(shù)大了點(diǎn)，但基本都能實(shí)現(xiàn)。

堆與二叉搜索樹與平衡樹

可能考的概率不是很高，但是個(gè)人感覺平衡樹應(yīng)該算是比較簡單的吧。

圖論

每年基本都會考，而且基本都是壓軸題，圖論感覺一考就很難。

數(shù)論

基本沒考過，頂多考個(gè)矩陣相關(guān)的優(yōu)化，概率極小。

搜索與倍增

搜索——騙分神器，有時(shí)候有奇效，善用可行性剪枝、最優(yōu)性剪枝與記憶化搜索。倍增——基本用來優(yōu)化各種神秘的算法，單獨(dú)考的不多。

動態(tài)規(guī)劃與貪心

最優(yōu)性問題兩兄弟，先想貪心，一般感覺是對的然后糊大樣例再對拍就行了，DP往往復(fù)雜度比較高，但代碼實(shí)現(xiàn)簡單。

二分三分模擬退火

可以大膽嘗試以各種數(shù)據(jù)作為自變量來構(gòu)造函數(shù)，看是一次/單峰/多峰來進(jìn)行判定，不會就打退火。