競程總覽和題單和各類應用常見演算法資結

{%hackmd @lumynou5/dark-theme %} # 競程總覽和題單和各類應用常見演算法資結 **打到一半我整理一下** 請善用左邊跳轉跟ctrl+f **關於競程** 下列討論都以c/c\+\+為主 python(本文默認py3)建議當特殊功能輔助用另開一類 ~~寫java建議棄賽~~ 不是啦jvm真的偏慢有的競賽跑不過or很容易卡常 **關於應用** c可以做但很難不過好處永遠是快 c\+\+比較容易而且也蠻快還有OOP跟STL可以用 python應用比較特別除了網頁/字串我暫時沒什麼想法 java作為老牌網路和應用軟體常用語言篇幅不小 ~~跟競程完全相反~~ 速度也還行又能跨平台除了競程常見四類 js和web asm也很重要 tcp/ip可以學一下另外資料庫也是一類順便把作業系統與編譯器的資料一起放一放 ~~想不開一起來寫一個新語言~~ ## 分類 ![](https://hackmd.io/_uploads/rJAgtLvA3.png =65%x) 借一張吳邦一教授(就ap325作者)的ppt 雖然我的分類有點小小的不同 **基礎類** apcs觀念1\~5實作1\~2or3     肯定要會吧不然你跟我說你學過程式? 語法,陣列     看起來可以很簡單但是可以非常難要有點數感找關係比較容易 遞迴     前兩個會了那來學學共通語言討論演算法跑多快 演算法複雜度和主定理     這沒什麼問題吧常常會有問題叫你排序 排序     各種找東西通常有排序過用一些單調性求解 二分搜,外掛二分搜,三分搜     刷leetcode必備技能不過除了實作STL或作業系統其實不那麼常見 linked list     局部最佳解可以得出全局最佳解時除了貪心絕對不可能過 貪心 **常見競程類** apcs實作3\~5 cpe3\~7題     簡單數學         演算法分析時如果有**機率性** 或**不同節點複雜度不同** **平均**後可能總和更小 均攤分析     圖論         圖的定義 連通,有向,環,樹,帶權,二分圖         有了**二元樹** 就可以來做**二分** 透過左右一邊大一邊小做出**二分搜** 二元搜索樹         在圖上要找東西像是**最短/長路徑** 或符合某些條件的東西(說實話範圍很廣) bfs,dfs     資料結構         STL跟各類二元樹常用實作之一有線性heap的特別版還有treap的進階變體 heap         一樣是STL實作 map或set用網路應用也很多了解原理比較重要 hash         也是STL實作 map跟set用用**旋轉**(雖然有點麻煩)做出**類似數學歸納法的平衡** 紅黑樹         tree+heap 樹的性質,堆的順序,紅黑樹的效果有分割式能避免旋轉treap         方便好用又不用底層實作(還是要學啦) 大部分題目都很難單用陣列就解出 STL         也是STL裡的函數雖然並不是資結但說實話我不知道放哪用來計算字典序的下一項         **輸入值域很大**(像int)但總數不多 離散化(其實不是資結但因為會用到資結就放進來)     遞迴和他們的進階(不太嚴謹啦不一定要用遞迴不過不要太在意)         遞迴的時候一直**重複算**算過的東西嗎那就把先算到的存起來吧背後有個**DAG** dp         遞迴的時候問題的答案從兩個**不重疊**的子問題求嗎那寫完遞迴式就解完了 分治     區間問題         需要求一整段的**不會變**的**總和**嗎那就先算到頭的總和再扣掉前面的總和 前綴和         相對的需要一直對一段**區間**一起**修改**嗎那就標記某點以後全部加/減一個數 差分         更廣泛的如果問題是**多次詢問**不同區間的值(像極值) 列出某些區間再合起來 稀疏表         可是稀疏表不能**修改** 所以可以用一棵樹不同層儲存不同的長度然後去改樹 線段樹         線段樹**區間改值**要懶標而且空間又大可以擁有這些特性但**空間n** 不過**適合區間和** BIT         有了前兩棵樹和平衡樹就可以解決**二維區間問題** 用樹套樹 但是好難我不會qq         看起來在**樹上找最近共同祖先**跟區間毫無關聯但他就是能**轉化成RMQ**問題 LCA     區間問題但是貪心         計算時要窮舉但是**有些值用過就不用**了(常有單調性) 維護左右兩點**區間範圍** 雙指針         類似的區間移動時要**跑一遍整個區間** 要**維護區間內的值**(常用動態資結) 滑動視窗         假設要考慮**某點以前/後到底的所有值** 並且某些**單調性**會讓一些值被跳過用單調棧     區間問題但是離線(好難qq 要意識到時間也是序列)         區間問題除了每次操作分開處理也能**預先處理詢問重複**的地方最後一起算 CDQ分治         **離線**後對於**二分**問題可用整體二分 把每筆**操作分到該去的區間** **重疊**的便可**共用答案**         **離線**後若可得相鄰區間解可用莫隊算法 **排序詢問的區間** 再從前面的區間往後面的爬     字串和序列(不須連續但順序不能相反)問題         要尋找**最長的遞增/減序列** 運用**單調性**進行**二分**可以有$O(nlogn)$ LIS         對**兩個字串找最長共同序列** 有**dp**解但能**轉化**為二維LIS 再變為**一維LIS** LCS         對**兩個字串做匹配** 透過尋找**子字串中重複**的部分快速跳到**下一個匹配點** KMP         尋找**字串中最長回文** 對每個點計算**以前面的字為中心鏡像**最長能多長 馬拉車     數學(含一點線性代數)和數論(離散數學或抽象代數)(台灣有點缺這方面大家補一下)         算多重加法=乘法算多重乘法=冪次 **冪次不是cpu基本運算**怎麼辦 快速冪(有點線代)         公因數可以用**輾轉相除法** 但是為了其他目的(像除法跟取餘是同指令) 擴展歐基里德         數學題/排組/總方案數數字常超大答案常模一個數 **取模環境下除法怎麼做** 模逆元 **還沒寫進去類** 快慢算法,baby-step giant-step,位dp,tsp,km二分匹配,Rolling Hash(Rabin Karp算法) suffix array 數學 https://oi-wiki.org/math/ 戴克斯特拉佛洛伊德 Bellman-Ford Kruskal prim 最小生成樹並查集對頂堆 pb_ds A* 樹套樹最近點對反演變化莫比烏斯反演 https://judge.tcirc.tw/Problems?page=5&&tabid=AP325 ,01背包莫隊 **應用類** 競程不常見但應用常見卷積,FTT     簡單數學(真的只有簡單運算啦)         **超過int**怎麼辦(金融) 只好陣列模擬但java,python都自帶大數競程不愛出 大數運算     數論類延續中等類數論         會開方了那來學學**對數** 不過要先認識原根 之後就可以算離散對數了資安加密需要         NTT 四叉樹,大數各類網站中一中電研 zerojudge leetcode codeforce atcoder 各類比賽 apcs cpe 學科能力競賽 npsc ncpc ista icpc ioi leetcode周賽雙周賽 CF atcoder ioi題庫 https://yuihuang.com/ioi/ 各類題庫 https://yuihuang.com/exercise/ OIwiki https://oi-wiki.org/ cses https://cses.fi/problemset/ ## 內文 ### 基礎類語法不會 ~~那你去google語法啊在這裡做什麼~~ [runoob c](https://www.runoob.com/cprogramming/c-tutorial.html) [runoob c++](https://www.runoob.com/cplusplus/cpp-tutorial.html) [runoob python3](https://www.runoob.com/python3/python3-tutorial.html) [陣列](https://opensourcedoc.com/c-programming/array/) **題單:** 上面隨便挑個[zj基礎題](zerojudge.tw/Problems?tabid=BASIC#tab00)或[板中題](https://zerojudge.tw/Problems?tag=%E6%95%99%E5%AD%B8%E9%A1%8C)都能練 [**遞迴**](https://www.csie.ntu.edu.tw/~b98902112/cpp_and_algo/cpp02/recursion.html)給個[一題](https://zerojudge.tw/ShowProblem?problemid=c002)簡單題然後一題[N皇后](https://hackmd.io/@YLowy/r1wIe9-DD)剪枝跟[位元運算+lowbit版](https://zhuanlan.zhihu.com/p/22846106) 當你發現有東西重複計算就代表可以去看dp了 **比較型排序** 包含插入,泡沫,選擇這三個看看就好不實用 qsort(c內建),std::sort(c++內建) 快又實用比較函式學一下方便逆序或特殊結構 **非比較型排序** 包含記數,桶排,合併有時候會在特定題目用上遇到或有點空就學一下吧 [**貪心**(第一段)](https://hackmd.io/@tcirc-40th/home/https%3A%2F%2Fhackmd.io%2F%40tcirc-40th%2Fry8pDcZdi)([像經典換硬幣](https://judge.tcirc.tw/ShowProblem?problemid=d042) 就你平常買東西那樣另外給[一題](https://zerojudge.tw/ShowProblem?problemid=l243)好了) **STL** 去google前幾個就會有包含 stack,queue,set,map,vector 這行最優先很基礎 priority_queue(pq),unordered_set,unordered_map 上面變體遇到難題就會發現你需要他 pair,list(同python默認list) pair是懶人福音 list特別情況才會用到(幾乎沒也可換linked list) [**dp**](https://web.ntnu.edu.tw/~algo/DynamicProgramming.html)([像經典換硬幣](https://zerojudge.tw/ShowProblem?problemid=d904)) 有時候 **題單:** 超萬能的[ap325](https://judge.tcirc.tw/Problems?tabid=AP325#tab03) 全做完就對了第一題裡面有講義連結入門類只用到1~6章