# 彰中資訊寒訓首頁

[解題統計](https://docs.google.com/spreadsheets/d/1yFKQ7Oq8kgaOC1tog1-Ay2_y5hcouxJTCokT7dFTkUg/edit?usp=sharing)
### 學習資源
- [Competitive programming handbook](https://cses.fi/book/book.pdf)
-

## 2/3(Wed)
- [基礎語法複習(ppt)](https://drive.google.com/file/d/17LMeD9B56l9yBL4PQeAyNc4ePGCSo6mD/view?usp=sharing)
- [時間複雜度(ppt)](https://drive.google.com/file/d/18m6jp4zZc6dDOUK311CCngSEa6F3Qcnc/view?usp=sharing)
- [遞迴(ppt)](https://drive.google.com/file/d/1Ijh8BToWYwXVi_CWDNypOokgn6ST3rzV/view?usp=sharing)
- [枚舉(ppt)](https://drive.google.com/file/d/1_qKJnENNxCUPKpaU4EsdzcagqkFBJC9H/view?usp=sharing)
### 補充教材
STL 語法教學：[vector](https://hackmd.io/@deta/vector)、[stack](https://hackmd.io/@detaomega/stack)、[queue](https://hackmd.io/@detaomega/queue)、[deque](https://hackmd.io/@detaomega/deque)

### 題目
語法：
1. [chsh1204:vector的基本操作練習](http://163.23.148.33/JudgeOnline/problem.php?id=1204)
2. [chsh 1134:好玩木塊第二版(vector)](http://163.23.148.33/JudgeOnline/problem.php?id=1134)
3. [zerojudge c123: 00514 - Rails（stack)](https://zerojudge.tw/ShowProblem?problemid=c123)
4. [TCGS b016:螞蟻雄兵(練習語法)](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b016)
5. [zerojudge a007: 判斷質數(估複雜度練習)](https://zerojudge.tw/ShowProblem?problemid=a007)

遞迴與枚舉枚舉：

6. [TCGS b022:費氏數列](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b022)
7. [TCGS b023:河內塔](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b023)
8. [zerojudge e446: 排列生成](https://zerojudge.tw/ShowProblem?problemid=e446)
<!-- [formosa OJ1215](https://oj.nctu.edu.tw/problems/1215/) -->
<!-- [formosa OJ1217](https://oj.nctu.edu.tw/problems/1217/) -->

**hard**

9. [TCGS d005](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=d005)
10. [zerojudge f637](https://zerojudge.tw/ShowProblem?problemid=f637)

## 2/4(Thr)
* [圖論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)

### 題目

圖論：
1.[zerojudge c812 DFS](https://zerojudge.tw/ShowProblem?problemid=c812)
2.[zerojudge b298 DFS](https://zerojudge.tw/ShowProblem?problemid=b298)
:::spoiler 題解
首先廠商關係可以用圖論表示 (然後關係是有向邊)
接下來每次DFS將有問題的廠商標記起來

比方說 如果今天有問題的商家是 $2,1,8$，商家關係是這張圖

dfs $2$ 後


dfs $1$ 後


dfs $8$ 後


這過程可以開一個Is_Draw陣列來記錄是不是有dfs過

vector <int> G[maxn];
bool Is_Draw[maxn];

void dfs(int now) {
    Is_draw[now] = 1;
    
    for (int i=0; i<G[now].size(); i++) {
        dfs (G[now][i]);
    }
}

int main() {
    int x;
    for (int i=1; i<=l; i++) {
        cin >> x;
        dfs(x);
    }
    
    for (int i=1; i<=Q; i++) {
        cin >> x;
        if ( Is_draw[x]) ...
        else ...
    }
}

然而當圖長這樣後
有問題的廠商是 $1,2,3...,n-1,n$
分析一下要dfs節點是 $n+n-1+...+2+1$
時間複雜度是 $O(n^2)$ !!!
$n = 100000$
$${\color{blue}{TLE!!!}}$$

有dfs的廠商不用dfs了，因為如果今天的商家有拜訪過那他下游的廠商也一定拜訪過

分析一下時間複雜度，每間廠商都只dfs一次，時間複雜度是$O(n)$ $=>$${\color{green}{AC}}$
:::spoiler AC code

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5+5;
vector<int> G[maxn];
bool Is_Draw[maxn] = {};

void dfs(int x) {
	Is_Draw[x] = 1;
	for (int i=1; i<G[x].size(); i++) {
        int k = G[x][i];
		if(!Is_Draw[k]) {
			dfs(k);
		}
	}
}
int main() {
	int n, m, l, q;	
	cin >> n >> m >> l >> q;
	for(int i=1; i<=m; i++) {
		int u, v;
		cin >> u >> v; 
		G[u].push_back(v);
	} 
	
	for(int i=1; i<=l; i++) {
		int x;
		cin >> x;
		if(!Is_Draw[x])
			dfs(x);
	}
	for(int i=1; i<=q; i++) {
		int x;
		cin >> x;
		cout << (Is_Draw[x] == 0 ? "YA~~\n" : "TUIHUOOOOOO\n");
	}
}

:::
3.[zerojudge a290 BFS](https://zerojudge.tw/ShowProblem?problemid=a290)
4.[zerojudge c129 BFS](https://zerojudge.tw/ShowProblem?problemid=c129)
5.[zerojudge e550 DFS or BFS](https://zerojudge.tw/ShowProblem?problemid=e550)
5.[zerojudge f167 Toposort](https://zerojudge.tw/ShowProblem?problemid=f167)
6.[zerojudge f628 Toposort](https://zerojudge.tw/ShowProblem?problemid=f628)

<style>
.part
{
margin-left: 24px;
}

h1.part
{
text-align:center;
}

h2.part
{
margin-left: 0px;
border: solid;
border-width: 1px 0px 1px 0px;
color: black;
text-align:center;
font-size: 150%;
background-color: #F5F5F5;
padding: 6px;
}

h3.part
{
margin-left: 0px;
border-top: solid 1.5px;
padding: 5px 1px;
}

h4.part
{
margin-left: 15px;
border: dotted;
border-width: 1px 0px 0px 0px;
}

h5.part
{
font-size: 128%;
}
/* Taken from hackmd.io/_RdJOUWOTrOYZi8fowyDpQ */
</style>

## 2/6(Sat)
[動態規劃](https://drive.google.com/file/d/1OrxJRWLPSaisPxOauVNEub7TzRl6K0R4/view?usp=sharing)
[線段數講義1](https://hackmd.io/jZyCdkU9TYmCBrbPVhJjVw)
[線段數+根號算法(分塊)](https://drive.google.com/file/d/1GEE19OH1uh78KGupL-WSNbreC6P1r_6j/view?usp=sharing)
題目

1. [b025: 棋盤格城市](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b025)
2. [b028: 忙碌的超商店員](tcgs.tc.edu.tw:1218/ShowProblem?problemid=b028)
3. [b029: 福袋!福袋!](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b029)

## 2/7 (Sun)

線段樹:
1. [【模板】线段树 1](https://www.luogu.com.cn/problem/P3372)

二分搜:

2. [CF 1217A](https://codeforces.com/problemset/problem/1217/A)
3. [GJ h098: F.田忌賽馬](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=h098)

**hard**

4. [【模板】线段树 2](https://www.luogu.com.cn/problem/P3373)(用到沒教過的懶人標記法)