---
tags: CP
---
# Competitive Programming

[TOC]

## 課程題單
[連結](https://hackmd.io/@jakao/problemList)

## online judge

* [zerojudge](https://zerojudge.tw/)
* [TIOJ](https://tioj.ck.tp.edu.tw/)
* [codeforces](https://codeforces.com)
* [atcoder](https://atcoder.jp/)
* [codechef](https://www.codechef.com/)
* [vjudge](https://vjudge.net/contest)
* [kattis](https://open.kattis.com)
* [UVA](https://onlinejudge.org)
* [競程日記](https://oj.icpc.tw)

## 資源

* [從零開始的演算法競賽入門教學](https://emanlaicepsa.github.io/)
* [演算法筆記](http://www.csie.ntnu.edu.tw/~u91029/)
* [另一個競賽相關整理](https://github.com/goodjack/awesome-cs-training)
* [經典演算法書(點get下載)](http://93.174.95.29/main/F6F195012783A8B3C8BB7628882A51B7)
* [cses book](https://cses.fi/book/book.pdf)
* [cp-algorithm](http://cp-algorithms.com/)
* [算法竞赛入门经典](https://github.com/dzsky/fucksky/blob/master/%E7%AE%97%E6%B3%95%E7%AB%9E%E8%B5%9B%E5%85%A5%E9%97%A8%E7%BB%8F%E5%85%B8%EF%BC%88%E7%AC%AC2%E7%89%88%EF%BC%89%20(%E7%AE%97%E6%B3%95%E8%89%BA%E6%9C%AF%E4%B8%8E%E4%BF%A1%E6%81%AF%E5%AD%A6%E7%AB%9E%E8%B5%9B).pdf)
* [演算法視覺化](https://visualgo.net/en)
* [下面有不少連結資源可以看看?](http://web.ntnu.edu.tw/~algo/Activity.html#7)

## 函式庫&其他
* STL
* vector
* queue
* deque
* stack
* priority_queue
* map(unordered_map)(multimap)
* set(unordered_set)(multiset)
* pair
* list
* bitset
* pb_ds
* 好用的函式
* lower_bound,upper_bound
* sort
* nth_element
* unique
* next/prev_permutation
* 複雜度
* 時間
* 空間
* IO優化

## algortihm
* [動態規劃(dp)](https://youtu.be/0WeUvhh3z1k)
* 背包問題
* LCS
* Edit Distance
* 區間DP
* [單調對列優化](https://youtu.be/1pvr9KYT_fE)
* [矩陣快速冪優化](https://youtu.be/Vwjq02Ete_M)
* [位元DP(含TSP,Hamiltonian)](https://youtu.be/iDu5whexSjY?t=2326)
* [DP on DAG/tree](https://www.youtube.com/watch?v=Jz3YlivPZqU)
<font color="#5CADAD">
* 斜率優化
* 四邊形優化
* aliens(wqs二分搜)
* 多項式快速冪優化
* 插頭DP(輪廓線DP)
</font>
* [貪婪(greedy)](https://youtu.be/NKycp3HcP90)
* LIS
* Fractional knapsack problem
* [分治(Divide&Conquer)](https://youtu.be/A51xibuoIIE)
* 序列分治
* 樹分治
<font color="#5CADAD">
* 重心剖分
* 操作分治
</font>
* 搜尋法(search)
* [二分搜 ](https://youtu.be/TNk-JsfxZLA)
* [三分搜](https://youtu.be/gYcolIyLAPs)
<font color="#5CADAD">
* 整體二分搜
</font>
* 資料結構(data structure)
* [並查集(dsu)](https://youtu.be/6d2tE_ItMAo)
* 線段樹(segment tree) [1](https://youtu.be/VkTf_lo-hnk) [2](https://youtu.be/xkhpdhzy0i0) [3](https://youtu.be/yTpQ497BHwI)
* 稀疏表(sparse table)
* [樹狀樹組(binary indexed tree)](https://youtu.be/2tO-t1YSSzo?t=916)
* 區間修改
* [分塊(SQRT-Decomposition)](https://youtu.be/b3DbWXFKw5o?t=1327)
<font color="#5CADAD">
* [Treap](https://www.youtube.com/watch?v=b3DbWXFKw5o)
* 動態開點
* [可持久化(Persistent data structure)](https://youtu.be/b3DbWXFKw5o?t=3225)
* KD-tree
* [樹鍊剖分(Heavy Light Decomposition)](https://youtu.be/PHjpBvsUjuY?t=2004)
</font>
<font color="#FF95CA">
* 時間線段樹
* merge-sort tree
* quick-sort tree
* interval tree
* link-cut tree
* top tree

</font>
* [圖論(graph)](https://www.youtube.com/watch?v=sAGm-ToOknk)
* 深度優先搜尋(dfs)
* 廣度優先搜尋(bfs)
* multi-source bfs

* [最小生成樹(minimum spanning tree)](https://www.youtube.com/watch?v=TAoZ9qQFdRY)
* [Kruskal](https://youtu.be/Z-tz9cFnq3Y)
* Prim

* [最短路徑(shortest path)](https://youtu.be/TAoZ9qQFdRY?t=898)
* dijkstra
* bellman-ford
* Floyd-Warshall
* SPFA
* [最近共同祖先(lowest common ancestor)](https://www.youtube.com/watch?v=PHjpBvsUjuY)
* [拓樸排序(topological sort)](https://youtu.be/Jz3YlivPZqU?t=405)
* [樹壓平](https://youtu.be/PHjpBvsUjuY?t=1526)
<font color="#5CADAD">
* 由拉路徑
* 強連通分量(scc)
* 二分圖匹配(bipartite matching)
* 網路流(flow)
</font>
* 數論(number theory)
* prime
* [sieve](https://hackmd.io/@jakao/math1#/3)
* 線性篩
* miller-rabin
* [快速冪](https://youtu.be/Vwjq02Ete_M)
* 小費馬
<font color="#5CADAD">
* 擴展GCD
* 中國餘式定理(chinese remainder)
* fft,ntt
* 莫比烏斯反演
</font>
* 字串(stirng)
* [字典樹(trie)](https://youtu.be/s4Ak-KrXRkk)
* [kmp](https://youtu.be/FHCgBzZcZm0?t=1176)
* [zvalue(擴展KMP)](https://youtu.be/FHCgBzZcZm0?t=2435)
* [hash](https://youtu.be/eIKDP7FfGZM?t=1273)
* [suffix array](https://www.youtube.com/watch?v=FHCgBzZcZm0)
<font color="#5CADA">
* AC automata
* suffix automata
* [palindrome tree](https://youtu.be/FHCgBzZcZm0?t=2700)
</font>
* [爆搜(brute force)](https://youtu.be/hbDQf42eOQY)
* 回溯法(backtracking)
* [莫隊(Mo's algorithm)](https://youtu.be/b3DbWXFKw5o?t=2181)
* [中間相遇法(meet in the middle)](https://youtu.be/-LZ30m0zXZY)
* 幾何(geometry)
* 點，線
* 內外積
* 面積
* [凸包](https://www.youtube.com/watch?v=z1S_iDiebVE)
* 賽局(game)
* SG

## 其他奇怪的東西?無聊可以亂看 (一堆噁心的提單或講義)
* https://vjudge.net/article/529
* https://blog.csdn.net/luomingjun12315/article/details/47438607
* https://vjudge.net/user/tigerisland45
* https://vjudge.net/user/Von
* https://vjudge.net/user/xyz1178700373
* https://vjudge.net/user/Isun
* https://codeforces.com/blog/entry/55274