---
# System prepended metadata

title: 中央競程下學期

---

# 中央競程下學期
## 3/3 z-algorithm and SA
建議把簡報下載下來，才不會有字不見的情況發生！！

Z-algorithm: 
https://hackmd.io/@Cutiemango/B1A8muQIL
https://drive.google.com/file/d/1pTSWoFCAYNTQYLoHuSiQnT51Vc7p1n_4/view?usp=sharing
SA:
https://hackmd.io/@Cutiemango/rkyP8QDBD
https://drive.google.com/file/d/1TJCVHhHq5rtw1L2j8ahK7e7YpblmkI-l/view?usp=sharing

## 3/10 KMP
KMP
https://docs.google.com/presentation/d/1k2PNjS0XU2VX9WpH0VeAXyCoVivTlmYg2_LvgK1fjEg/edit?usp=sharing
好資源:
[CP algorithm(裡面code寫得蠻乾淨)](https://cp-algorithms.com/string/prefix-function.html)

[KMP 中國視頻](https://study.163.com/course/courseLearn.htm?courseId=468002#/learn/video?lessonId=875004&courseId=468002)
> 如果要請你登入，可以用此[方法](https://youtu.be/oeT2Z-5FjWg)

[KMP 用動態規畫概念解釋](https://www.mdeditor.tw/pl/prIb/zh-tw)

## 3/17 DFS複習
* [圖論1](https://docs.google.com/presentation/d/13h9oWi_ZvUoo9csH1nzBEQkiJn0NTobfEmxsHqBbfHs/edit?ts=5c4472fd#slide=id.g4c18c720c1_0_5)
* [圖論2](https://hackmd.io/@joylintp/SkYyNouGD#/1/1)
* [圖論3](https://drive.google.com/file/d/1ULVU0j--X5j_9WDWDchr2rnfosfb2hw-/view)
* [DAG](https://drive.google.com/file/d/1TYE9h4mAQD42nTg4Nm1l-kdToiOZ5Qox/view?usp=sharing)


[**dfs範例程式碼**](https://ideone.com/xYX8bZ)

### 補充教材
[struct and pair](https://hackmd.io/@royyaha/r1S_9q3qN)

dfs, bfs練習
[zerojudge b298: 老闆阿我要退貨](https://zerojudge.tw/ShowProblem?problemid=b298)
[zerojudge c812: 1. 觀光景點](https://zerojudge.tw/ShowProblem?problemid=c812)
[zerojudge d537: 4. 染色遊戲](https://zerojudge.tw/ShowProblem?problemid=d537)


## 3/24

[AP&bridge](https://hackmd.io/0OhArgX8SX-NRmqpQWX0ow)  
[CC、SCC](https://hackmd.io/QRQmWqYITI2ZEsRmIc12_w)           

## 3/31

[Disjoint set投影片](https://drive.google.com/file/d/1rhIu0jUJpc_ukyfBOUKuLa8isczHHH-6/view?usp=sharing)
[Trie程式碼](https://pastebin.com/P0xLUrAW)  
[Trie投影片](https://drive.google.com/file/d/11YwugvvBaduNy801Yo5DbEOTYdmIu-b7/view?usp=sharing)
[Trie題目單](https://hackmd.io/jWPb0Y5jS4Kzy_zmjDAjyw?both)  

[Disjoint set(沒優化版本)](https://ideone.com/f0HmDx)

## 4/14 二分圖匹配

如果你不想努力，請參考 :
[HackMD (內有PPT可供觀賞)(文末貼心附贈張百寬的程式碼)](https://hackmd.io/V9d3keTzRFWa2B2iD37uDQ?view)

## 4/28
https://hackmd.io/@rDXPSsqWRemlNf_FCKoGlQ/Hy6IJrHP_

## 5/12
[MST](https://hackmd.io/gg_J8uFUSWiAqE6lV85qwg?both)
[LCA](https://hackmd.io/X-qZ2D7pR6GhRo3h62YhxA?view) 
[次小生成樹](https://hackmd.io/ItL68lvDQayCUCYJMWU-uw?both)


:::spoiler 倍增code
```cpp=
#include <bits/stdc++.h>
using namespace std;

const int maxn = 20;
const int l_maxn = __lg(maxn) + 1;

int up[maxn][l_maxn]{}, depth[l_maxn]{};
vector<int> edge[maxn];

void dfs(int u, int pre) {
    for(int i = 0, v = pre; i < l_maxn; i++) {
        up[u][i] = v;
        v = up[v][i];
    }
    
    cout << "current node: " << u << endl;
    for(int i = 0; i < l_maxn; i++) {
    	cout << "up[" << u << "][" << i << "] = " << up[u][i] << endl; 
	}
	cout << endl;
	
	
    for(auto v : edge[u]) if(v != pre) {
        dfs(v, u);
    }
}

void init(int root) {
    dfs(root, root);
}

void add_edge(int u, int v) {
	edge[u].push_back(v);
	edge[v].push_back(u);
}

int main() {
	add_edge(3, 8);
	add_edge(8, 5);
	add_edge(5, 1);
	add_edge(1, 4);
	add_edge(4, 7);
	add_edge(7, 2);
	add_edge(2, 9);
	
	init(3);
}
```
:::
[次小生成樹code by 昱求](https://github.com/chshroy/practice/blob/master/TOJ/207(SUBMST).cpp)