louisfghbvc的部落格

紀錄: 基本上排名是在上升(?)

心得:

從大二開始去打CPE，一開始都很矇，都1~2題。到後來不停鑽研演算法，以及強化各個資料結構應用。終於進步到5題。

5題的時候確實是瓶頸，因為有些題目看到還是沒想法，像我最弱的就是dp跟貪心還有BFS。

從弱的下手，自從推甄完後，我開始狂練dp，去Leetcode打dp題，跟itsa題庫dp題幾乎全做完。

Leetcode周賽幾乎都有dp題，周賽就像小型的CPE，總共4題，我覺得比起CPE是比較容易的，不過第4題通常是困難題，dp或是高等演算法。

終於在畢業之前，將CPE破台，雖然說這次(6/9)的CPE真的是有點簡單(笑)。不過寫的有點抖，第5題寫很久，會疲乏(眼睛會痠，思考能力下降)。

有時候有簡單也有難的時候，反正多考多機會。

我的經驗告訴我，前3題都是暴力法，4~7中通常有一題是水題(就是暴力能過)

通常第4題都是那種偏數學，或是模擬。

第6題，常常都是生成樹或DP

第7題，通常噁心題

如何變強:

不停的練習題目，基礎到進階。以及狂打比賽(itsa，學校辦的比賽，校外比賽)

最好是要有固定的網站讓你練，Uva是最佳(因為CPE題目來源)，uhunt那邊都有題目可以練(大推uhunt可以照著他的章節練，關鍵字: CP3)

不過我大一到大三好像也沒啥再練Uva，是大四突然覺醒

像我是LeetCode的周賽(四上~四下)在練，如果周賽破台基本上CPE破台也不難。你會發現，解題思路跟手速會越來越快(其實不一定拉，比賽難度範圍有Bias)

而且LeetCode在打的時候，可以看看別人的文章，收穫良多，學到高強資結跟演算法(Rolling Hash、LRU cache 、Trie、Tarjan algorithm等等)。

或者codeforces，atcoder等等，也是可。雖說類型不太一樣(偏思維題)。其實沒有一個正確答案。

但真的就是多練習題目，不要放棄。

再來，最好是CPE一顆星兩顆星題目可以做一下，熟悉一下他的模式，然後歷屆比賽，也可以多練練。

我用的是程式語言C++

首先:

我是C++/C混著用。有時候Scanf()很方便或是printf()，當然這樣或許不是很好的習慣，不過我是習慣了XD。

基本的字串轉數字(stoi之類的)，數字轉字串(to_string())都要會。以及怎麼樣做無限輸入(cin直接放在while，scanf()的話是!=EOF)。

要會善用STL演算法，函式(比如: sort, next_permutation, lower_bound..等等)

有著基礎之後，至少水題都要會。

再來:

--資料結構--

stack，queue，deque，priority_queue，list 都要會用，STL都有容器可以用。

vector非常好用。tree的觀念也要有

Disjoint Set並查集 必須要會用，這超級好用，很多比賽都常常需要。

map，set必會。

--演算法--

太多，基礎是質數篩法，還有一些數學的基本觀念(幾何，三角函數等等)要有。

二分搜(當你發現答案是一個有順序的時候就能用用看，基本上就是猜答案)。

貪心法(典型的區間排序，或是灑水器問題，事實上貪心有時候比dp難)。

DP(至少要會背包，LCS，LIS，記憶化搜索，通常遇到遞迴求解，發現答案有重複，就能記憶化搜索存到state裡面)

圖論:  至少要會SPFA，Dijkstra。Floyd-Warshall，最小生成樹，DFS，BFS。

遞迴必須熟悉、枚舉(八皇后問題基礎必學)。

字串: kmp(蠻有趣的，建議學，二星題庫有)

以上都是必會。其他就自行體驗了(一時之間很難全說明)，只能說經驗也是蠻重要的。

雜談:

--進階演算法--

CPE不太常出現，但是通常打競賽都遲早要接觸

-Max Flow(EK算法, Dinic): 通常大型比賽可能會有，不過難在建模，不常做這種題型是真的不會

-Min Cost (Max) Flow: 除了流量之外，搭配權重

-KM二分匹配: 二分圖，基本上有互不相干關係都能用上，比如男女必須配對之類的

-BitMask+DP: TSP會用到，以及其他能壓縮狀態的時候，然後又要爆搜的時候，自行體會

-Suffix Array, Trie:  2D找多字串搜索可以用Trie壓縮(LeetCode有題目)。SA的話，O(NlogN)算法要搞懂，要用上的時候真的很好用。

-Rolling Hash(Rabin Karp算法): 其實跟KMP用途一樣，找的時候加快，不過這個更猛，可以學一下，也是滑動窗口概念

-Sliding Window: LeetCode常出現，通常就是很重複，然後有些東西有範圍性，就能用到。

-倍增觀念，LCA，Fast Pow: LCA蠻不賴的，Pow就自己寫的時候可以用倍增方式加快，還有那該死的浮點數誤差==

-凸包: 好少做這種題型(幾何)，因為我是拿來做最遠點對加速(ITSA)

-線段樹，BIT Tree: 學校自辦賽有出，通常就是要加速查找(區間最小值，最大值，和)的時候會用到。

-SCC強連通:  好像不常出現(UVa有)，就是Tarjan算法，反正就一系列的都學一學?

-割點、橋: Tarjan算法，典型的題目。

當然不只這些，多多嘗試不同題型，會很有趣。腳踏實地的搞懂每個觀念。

說實在，我也不是到那麼資深，許多高難競賽演算法還沒設略，只能說坑就是要一直補，學得越多，新東西要摸索有些能依樣畫葫蘆，就可以比較快。

然後學到後面就發現，自己數學真的超差。ಥ_ಥ，到現在還不會FFT