---
# System prepended metadata

title: 競程寒假

---

# 競程寒假
不知道大家寒假有什麼規劃，應該都會想趁寒假變強吧:D
提供大家一些目標：
1. 寫一堆dfs、動態規劃的題目（寒假把這兩個用到很熟就超讚的了）
2. 準備好下學期的內容（題目蠻難，不知道怎麼下手會想辦法引導大家）
3. CF上藍（真的很想上藍但上不去我也許可以給點建議）

團隊練習這邊也給一點方向，希望可以和其他學校有得拼：
三個人熟悉基礎的算法，再分工各自專研部分主題，發揮團隊合作的精神XD


## 主題一覽
每一行都由一組負責，基本上是一次聚會(3小時的時間)都交給你們。

難度：簡單(1)到難(5)，自己憑感覺給的
- 字串
    1. z-function(2), suffix array(4)
    2. KMP(2), AC自動機(4) 
- 樹
    1. 最小生成樹(2)、倍增求LCA(3)、次小生成樹（難度3） 
    2. disjoint set(2)、trie(2)
- 圖論
    1. 橋、關節點、聯通塊、強聯通塊(3)
    2. 二分圖匹配(3)、KM算法(4)
    3. 網路流(4) 
    4. 最短路徑: Floyd-Warshall(3), Dijkstra(3, priority_queue version), Bellmon-Ford(3), Johnson's algorithm(4)
- 幾何
    1. 二維凸包(2)、最近點對(3)、旋轉卡尺(4) (ps.蠻數學的東西)
- other
    1. 莫隊(3)、整體二分搜(5)

## 重要時程
1/24(sun)：填完分組表格
1/30(sat)：至少先寫出相關主題的一個經典題目（主要是想確定大家有弄懂各自的題目）。
2/6(sat)：做出一點簡報內容（主要是想確定大家知道內容要寫什麼，並提供一些可以補充的東西）。
2/20(sat)：開學前，希望大家完成90%的內容，開學負擔才不會太重。

p.s. 把經典題和應用的題目連結留下來，之後讓大家練習
p.s. 有些組別會有很多內容，先研究簡單的主題一步一步來！


## 簡報內容
建議用google簡報做，大家比較容易共同編輯。
內容需涵蓋（若有更好的講解步驟可以自己改，能教會大家為主）
1. 演算法介紹(用途，可以優化什麼東西，以經典例題為例？)
2. 時間複雜度分析
3. 實作簡單講解
4. 丟例題

## 好用工具
1. [幫你畫好圖的網站](https://csacademy.com/app/graph_editor/)
    可以輸入邊，他會幫你畫好圖，再截圖到ppt裡。
2. csdn
    中國的學術博客內容真的很多...
4. 大家有好用工具可以在這邊分享

## 分組名單

- 組員可以放CF handle。
- 創一個HackMD，裡面放一些資料連結(寫過的相關題目、簡報等)，方便追蹤一下進度，我可能也會在裡面寫一些字給一點方向。
(這樣搞會不會讓大家壓力很大啊qqqqqqqq）

| 主題  |     組員1     |     組員2     |      組員3      | HackMD連結                                                                                                                                                                          |
| ----- |:-------------:|:-------------:|:---------------:| ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
| 字串1 |  cutiemango   |               |                 | [z-algorithm](https://hackmd.io/@Cutiemango/B1A8muQIL)  [suffix_array](https://hackmd.io/@Cutiemango/rkyP8QDBD)                                                                                                                            |
| 字串2 |   ConorWang   |               |                 |                                                                                                                                                                                     |
| 樹1   | sasaki1223112 |               |                 | [MST](https://hackmd.io/gg_J8uFUSWiAqE6lV85qwg?both)                                 [LCA](https://hackmd.io/X-qZ2D7pR6GhRo3h62YhxA?view)          [次小生成樹](https://hackmd.io/ItL68lvDQayCUCYJMWU-uw?both)                                                                                                                            |
| 樹2   |    JTRrrr     |     cutew     |     qawl987     | [Disjoint set](https://hackmd.io/A7LPQWE4RO2ginlK7-Vewg?view&fbclid=IwAR1bB7iahJeNHIkeZuYyOh83HngN_y4BZT6i8isiIHei8Mq_ZwFHVq6lElw) [Trie](https://hackmd.io/444lq0KsSdGc4GswEZlkfQ) |
| 圖論1 | sasaki1223112 |               |                 |    [AP&bridge](https://hackmd.io/0OhArgX8SX-NRmqpQWX0ow)  [CC、SCC](https://hackmd.io/QRQmWqYITI2ZEsRmIc12_w)                                                                                                                                                                               |
| 圖論2 |   quan0715    |               |                 |   [二分圖匹配](https://hackmd.io/V9d3keTzRFWa2B2iD37uDQ)                                                                                                                                                                                 |
| 圖論3 |   PuddingYG   | pryang0601 |       | [網路流](https://hackmd.io/Tn3w1_FiQdK5PNshblUCzg)                                                                                                                                                                                    |
| 圖論4 | Wilson.liang  |             |                 | [最短路徑](https://hackmd.io/@WilsonLiang/rk-c0D8lu?fbclid=IwAR33hQidYsBg2uXRL0oDlW4pA_8bg1A8G5e57HV7OhFaeJ3PDsix5-G1l7I)                                                           |
| 幾何1 |   cielxxxx    |   mafusuki    | jordenisalegend | [幾何](https://hackmd.io/@2db3oZuORs63CFUsxBg4zg/HkwCbz7g_/edit)                                                                                                                    |
| 其他1 |    Alex-30    |               |                 | [Mo's algorithm](https://hackmd.io/@Alex30/ry2gVHZld)                                                                                                                               |
