---
tags: 資訊之芽
title: Sprout生長紀錄 – C++ 演算法學習
---

# Sprout 學習紀錄 – C++ 演算法學習

---

## <font color="#2f4db0">目錄</font>

### 1. 學習成果
### 2. 延伸成果（主要部分）

----

[TOC]

---

## <font color="#2f4db0">資源統整</font>

----

### 課表及導流

(點擊主題之超連結，會連結到該周課程的題目code)
| 次數 | 主題 |
| ---------- |:------------------------------------------------------------------------------------------------------------------------ |
| 1st 03/05 | [Data structure && Monotone queue](https://drive.google.com/drive/folders/1ZM-C_HeuE-vDYE2EPeNPUIyhXioJQz2m?usp=sharing) |
| 2nd 03/12 | [Binary tree && Complexity](https://drive.google.com/drive/folders/1AF8_PVsvYf2LDaNRGANBDHWRAOJvao8d?usp=sharing) |
| 3rd 03/19 | [Heap && Flood fill](https://drive.google.com/drive/folders/1GbjK4akmC_4WEX6y8rrzMGme9DXrn4N-?usp=sharing) |
| 4th 03/26 | [Enumerate && Binary search](https://drive.google.com/drive/folders/1LmcuxI5cxTj_3rNIU0DWPBcgbKW056oE?usp=sharing) |
| 5th 04/02 | [Greedy](https://drive.google.com/drive/folders/1SSMLpCcquCtPp3fLTlJL9mZ78OZmYHYz?usp=sharing) |
| 6th 04/09 | [Divide and Conquer](https://drive.google.com/drive/folders/1pmmlQqCSh_MPU_K4EQDbkKZEGOX6vRd-?usp=sharing) |
| 7th 04/16 | [Dynamic Program 01](https://drive.google.com/drive/folders/1L9Lj1THDNizrTkBsPOq367uVL5CqW1nd?usp=sharing) |
| 8th 04/23 | 1st Certification exam |
| 9th 05/07 | Dynamic Program 02 |
| 10th 05/14 | Dynamic Program 03 |
| 11th 05/21 | Random |
| 12th 05/28 | Graph 1 |
| 13th 06/04 | Geometry |
| 14th 06/11 | Segment tree |
| 15th 06/18 | Final certification exam |

---
---

## <font color="#2f4db0">學習成果</font>

### Week 1 Data structure

課程內容：
使用vector實作stack , queue , deque
使用指標實作Linked list
單調對列(檸檬汽水傳說，長條圖最大矩形面積)

手寫作業內容：
證明與反證、歸納法

----

### Week 2 Binary tree && Complexity

課程內容：
實作建造二元樹(插入，刪除，搜尋)
估計複雜度
P與NP問題
樹重心

手寫作業內容：
極限與時間複雜度定義

----

### Week 3 Heap && Flood fill

課程內容：
Heap概念，實作Priority_queue
Flood fill -> DFS/BFS (貓抓老鼠，染色遊戲)
BFS與DFS比較

手寫作業內容：
記憶體布局

----

### Week 4 Enumerate && Binary search

課程內容：
數獨遊戲，八皇后問題
Permutation (排列枚舉->樹實作)
二分搜（古墓），三分搜（快樂函數）

手寫作業內容：
排序，字串匹配

----

### Week 5 Greedy

課程內容：
greedy概念與思路(攜帶高棕梠)
霍夫曼編碼與最優編碼樹
線段重疊問題

手寫作業內容：
貪心法證明

----

### Week 6 Divide and Conquer

課程內容：
實作：分地問題 , Merge sort , 逆序數對 , 最近點對
分治複雜度分析(Substitution Method,Recursion-Tree Method,Master Method)
多項式乘法 $O(n^{log_2 3})$

手寫作業內容：動態規劃證明題

----

### Week 7 Dynamic Program 01

課程內容：
實作：LIS , LCS , 區間DP(合成高棕梠) , 最大連續和的變形（環狀，無限，不連續）
轉移以及mod處理

----

### Week 8 1st Certification exam

pA：樹上DFS，求路徑極值
pB：linked list 實作
pC：二分搜 + greedy
pD：greedy + 二分搜 + 資結
pE：最短路徑 + 樹重心 + 分治

手寫作業內容：
記憶體布局

----

### Week 9 Dynamic Program 02

課程內容：
各式背包問題，meet in middle

手寫作業內容：歸約法

----

### Week 10 Dynamic Program 03

課程內容：
dp優化：矩陣優化，單調優化$\rightarrow$有限背包
位元dp
鄰接矩陣$\rightarrow$路徑數

手寫作業內容：P與NP問題

----

### Week 11 Random

課程內容：
Random skills
Rolling hash
Error rate calculation

手寫作業內容：Fenwick tree, lowbit

----

### Week 12 Graph 1

課程內容：
Topological Sort $\rightarrow$ determine DAG
Disjoint set $\rightarrow$ Component
Minimum Spanning Tree $\rightarrow$ Kruskal and Prim algorithm
Shortest Path $\rightarrow$ Dijkstra, Bellmen, and Floyd

手寫作業內容：Hash Concept

----

### Week 13 Geometry

課程內容：
Vector operation
Float bias
Angle_sort
Convex_hull

----

### Week 14 Segment tree

課程內容：
Segment tree
Lazy tag

---

## <font color="#2f4db0">延伸成果</font>

#### 除了上課教到的東西，我將感興趣的內容再延伸學習呈現，或是把一些我很喜歡的內容挑出來討論。
##### 例如在Binary tree單元中學到如何建造二元樹，但會有歪斜的問題，因為我想要更加了解std::set是如何被做出來的，所以我就在有空的時候，上網找文章，試著自己做一顆AVL tree。

----

### LaTex

因為手寫資芽作業速度太慢，所以我在後期都主要用HackMD寫手寫作業，而因為資芽有很多問題都跟數學相關，為了作業美觀以及打字方便，我就開始學LaTex。

LaTex的入門對我來說絕非件容易的事情，先是我很不習慣一些LaTex的打法(ex 打分數要打成\frac{分子}{分母})，在前期typing上會有很多的錯誤，而有很多公式需要自己查，所以在前期使用LaTex時，所花費的時間是原本寫作業時間的兩倍以上。

在熟悉使用之後，我就逐漸的原本寫在紙本筆記轉到電腦上並加入LaTex，例如：微積分、社課簡報、課業筆記。以下是某次手寫作業的呈現。

:::spoiler 第十一周手寫作業p2(b)
:::

----

### Limitation -> Calculus

在第二周的課程中，有提到limit的基本概念，我對此部分非常感興趣，又因為我曾經有學過零星的微積分，因此也激發了我買書學微積分的慾望。<font color="#e8961c">（詳見我微積分的學習歷程）。 </font>

:::spoiler 微積分學習歷程（C4 integral）
:::

----

### AVL tree

課程當中沒有提到如何解決這個問題，出於想要實作所有出 STL 資料庫中的資料結構，我上網開始學習 `std::set` 的實作方法。這段程式碼是一個AVL樹的實現，AVL樹是一種自平衡二元搜尋樹，能夠在 $O(\log n)$ 的時間內完成插入、刪除、查詢等操作。

首先，定義了一個 Node 類別，用來表示樹節點的基本屬性，包括節點值、高度和左右子節點的指針。其中，GetHeight 函數用於獲取節點高度，getBalanceFactor 函數用於計算平衡因子，即左右子樹高度差。

接下來，定義了兩個旋轉操作，即 rrRotate 和 llRotate。當 AVL 樹的平衡因子超過 $1$ 或 $-1$ 時，需要進行旋轉操作來保持平衡。rrRotate 用於對左子樹進行右旋轉，llRotate 用於對右子樹進行左旋轉。在進行旋轉操作時，需要更新相關節點的高度。

接著，定義了 Insert 和 Delete 函數，用於插入和刪除節點。插入節點時，需要先遍歷樹找到插入位置，然後更新相關節點的高度和平衡因子，如果平衡因子超過 $1$ 或 $-1$，需要進行相應的旋轉操作來保持平衡。刪除節點時，需要先遍歷樹找到要刪除的節點，然後根據其左右子節點的情況進行不同的操作。如果只有一個子節點，直接將該子節點上移；如果有兩個子節點，則找到其右子樹中的最小節點代替要刪除的節點，然後再刪除該最小節點。最後，也需要更新相關節點的高度和平衡因子，並進行相應的旋轉操作。

這些操作都是基於 AVL 樹的自平衡特性進行的，可以保證樹的高度不會超過 $O(\log n)$，從而保證了操作的時間複雜度。因此，AVL 樹是一種非常有效的二元搜尋樹，常被用於需要快速查詢和更新的場合。

而除了學習以外，因為我也是講師，所以我就把所學教給社團其他人。
<font color="#e8961c">（我把更多實作上的細節以及實作心得放在社課經驗學習歷程）</font>


:::spoiler Template

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

class Node{
	int value , height;
	Node *rchild , *lchild;
	
	Node* newNode(int value){
		Node *node = new Node();
		node->value = value;
		node->height = 1;
		node->lchild = nullptr;
		node->rchild = nullptr;
		return node;
        // init a new node and return
	}
	
	int GetHeight(Node *node){
		if(node == nullptr) return 0;
		else return node -> height;
        // get the geigth of the node,
        // if the node == nullptr return 0;
	}
	
	#define GTH GetHeight
	Node *rrRotate(Node *y){ //(y->nt(rc)->ntc(rc))
		Node *nt = y->lchild; // new_root
		Node *ntc = nt->rchild; // origin y_rchild
		nt -> rchild = y; // rotate
		y -> lchild = ntc; // rotate
		y -> height = max(GTH(y->lchild) , GTH(y->rchild)) + 1;
		nt -> height = max(GTH(nt->lchild) , GTH(nt->rchild)) + 1;
		return nt;
	}
	
	Node *llRotate(Node *y){ //(y->nt->ntc)
		Node *nt = y->rchild; // new_root
		Node *ntc = nt->lchild; // origin y_rchild
		nt -> lchild = y; // rotate
		y -> rchild = ntc; // rotate
		y -> height = max(GTH(y->lchild) , GTH(y->rchild)) + 1;
		nt -> height = max(GTH(nt->lchild) , GTH(nt->rchild)) + 1;
		return nt;
	}
	
	#define GBF getBalanceFactor
	int getBalanceFactor(Node *node){
		if(node == nullptr) return 0;
		return GTH(node -> lchild) - GTH(node -> rchild); 
	}
	
	public: Node* Insert(Node *node , int value){
		if(node == nullptr) return newNode(value);
		if(value < node->value){
			node -> lchild = Insert(node -> lchild , value);
		}
		else if(value > node->value){
			node -> rchild = Insert(node -> rchild , value);
		}
		else{ // error
			return node;
		}
		node -> height = max(GTH(node->lchild) , GTH(node->rchild)) + 1;
		int balance = GBF(node);
		if(balance > 1){ // lc>rc
			if(value < node->lchild->value) return rrRotate(node);
			// value 是底部節點的 value ， 如果它小於 node.lchild 的 value
			// 代表它被插在左節點的左側 ， 則平衡時只需要 llRotate 
			else if(value > node->lchild->value){
				node -> lchild = llRotate(node->lchild);
				return rrRotate(node);
			}
			else return rrRotate(node); // won't occur
		}
		if(balance < -1){
			if(value > node->rchild->value) return llRotate(node);
			else if(value < node->rchild->value){
				node -> rchild = rrRotate(node->rchild);
				return llRotate(node);
			}
			else return node;
		}
		return node;
	}
	
	Node* NodeWithMinimum(Node *node){
		Node *now = node;
		while(now -> lchild != nullptr) now = now->lchild;
		return now;
	}

	public: Node* Delete(Node *node , int value){ // find and delete
		if(node == nullptr) return node; // error
		if(value < node->value){
			node -> lchild = Delete(node->lchild , value);
		}
		else if(value > node->value){
			node -> rchild = Delete(node->rchild , value);
		}
		else{ // find it
			if(node -> lchild == nullptr || node -> rchild == nullptr){
				// 其中一個為 null ， 則直接上搬 
				Node* tmp;
				if(node -> lchild == nullptr) tmp = node -> rchild;
				else if(node -> rchild == nullptr) tmp = node -> lchild;
				node = tmp;
				free(tmp);
			}
			else{
				Node* tmp = NodeWithMinimum(node -> rchild);
					node -> value = tmp -> value;
					node -> rchild = Delete(node -> rchild , tmp -> value); 
				free(tmp);
			}
		}
		
		if(node == nullptr) return node;
		
		node -> height = max(GTH(node->lchild) , GTH(node->rchild)) + 1;
		int balance = GBF(node);
		if(balance > 1){
			if(GBF(node -> lchild) >= 0){
				return rrRotate(node);
			}
			else{
				node -> lchild = llRotate(node -> lchild);
				return rrRotate(node);
			}
		}
		else if(balance < -1){
			if(GBF(node -> rchild) <= 0){
				return llRotate(node);
			}
			else{
				node -> rchild = rrRotate(node -> rchild);
				return llRotate(node);
			}
		}
		else return node;
	}
	
	public: void printTree(Node *root, string indent ,bool last) {
		if (root != nullptr) {
		cout << indent;
		if (last) {
		  cout << "R----";
		  indent += "   ";
		} 
		else {
		  cout << "L----";
		  indent += "|  ";
		}
		cout << root -> value << endl;
		printTree(root->lchild, indent, false);
		printTree(root->rchild, indent, true);
		}
	}
};

int main() {
  Node* root = nullptr;
  root = root->Insert(root, 33);
  root = root->Insert(root, 13);
  root = root->Insert(root, 53);
  root = root->Insert(root, 9);
  root = root->Insert(root, 21);
  root = root->Insert(root, 61);
  root = root->Insert(root, 8);
  root = root->Insert(root, 11);
  root-> printTree(root, "" ,true);
  root = root->Delete(root, 13);
  cout << "After deleting " << endl;
  root-> printTree(root,"" ,true);
}

:::

----

### 強歸納法

在第一周的證明作業中的第四題

:::spoiler Problem
:::
\
我想用歸納法證明它。從前學的歸納法是透過 $n=1$ 成立，設 $n=k$ 存在，證明 $n=k+1$成立，於是我試著證明 $n=k+1$ 成立，卻怎麼也想不到解。
在我苦惱不已時，朋友幫我指點迷經，他告訴我，有一種東西叫做「強歸納法」，而我上網查了資料，得到：

:::spoiler property (from wikipedia)
:::
\
之後我改以遞迴角度思考這一題，
假設 $n=k-1$ 成立，欲證明 $n=k$ 成立，可以透過 $n=a$ 及 $n=b$ 時的值遞推到 $n=k$
若要證明 $n=k$ 時成立，則取 $a = t(1 < t < k-1)$ 且 $b = k-t$，帶入得到總和為 $t(k-t) + \frac{(t^2-t)}{2} + \frac{((k-t)^2-(k-t))}{2} = \frac{k^2-k}{2}$，得證。

----

### P and NP problems

:::spoiler 名詞解釋（來自資芽Week 9 Hw）
**P 問題** : 是由存在多項式複雜度求解演算法的問題形成的集合。
**NP 問題** : 是由存在多項式複雜度驗證演算法的問題形成的集合。
**NP-hard 問題** : 可以使得任意 NP 問題多項式時間歸約到的問題。
**NP_complete 問題** : NP $\cap$ NP-hard

:::

<br>

這個問題從 w9 的作業（歸約法）開始就開始鋪梗了，歸約法是一種，透過一種演算法，驗證另一演算法複雜度上界的方法。
有了這個基礎， w10 手寫作業就在開始探討怎麼把某些NP問題歸約到NP-hard再到NPC，作業內容主要就在探討CNF-SAT的相關問題。我一直覺得NP和P問題很酷，在做完這份作業後也大概知道這整個問題的架構。

----

### Matrix

用struct和運算子重載寫出了一個 Matrix 的 template ， 包含像是矩陣乘法、快速冪等功能（相加相減、轉置、reverse、高斯消去等待擴充），大大提升(~~數學作業效率~~) 相關問題的coding 效率，而且這樣在使用矩陣時也比較系統化。

:::spoiler Template

#include<bits/stdc++.h>
#define int long long
#define endl "\n"
#define AC cin.tie(0);ios_base::sync_with_stdio(0);
#define pb push_back
#define popb pop_back
#define popf pop_front
#define mp(a,b) make_pair(a,b)
#define F first
#define S second
#define INF 1e14
#define pii pair<int,int>
//const int mod = 1e9+7;
using namespace std;

struct Matrix
{
	vector<vector<int>> v;
	int n , m;
	void init_(int _n , int _m){
		n = _n , m = _m;
		v.resize(n,vector<int>(m));
	}
	void input()
	{
		for(int i=0 ; i<n ; i++){
			for(int j=0 ; j<m ; j++) cin >> v[i][j];
		}
	}
};

Matrix operator*(const Matrix m1 , const Matrix m2){
	assert(m1.m == m2.n);
	Matrix ret;
	ret.init_(m1.n,m2.m);
	for(int i=0 ; i<m1.n ; i++){
		for(int j=0 ; j<m2.m ; j++){
			for(int k=0 ; k<m1.m ; k++){
				ret.v[i][j] += m1.v[i][k] * m2.v[k][j];
//				ret.v[i][j] %= mod;
			}
		} 
	}
	return ret;
}

void print(Matrix ret)
{
	cout << endl;
	for(int i=0 ; i<ret.n ; i++){
		for(int j=0 ; j<ret.m; j++){
			cout << ret.v[i][j] << "\t";
		}
		cout << endl;
	}
}

signed main()
{
	AC;
	int a , b , c;
	cin >> a >> b >> c;
	Matrix m1 , m2 , ret;
	m1.init_(a,b);
	m2.init_(b,c);
	m1.input();
	m2.input();
	ret = m1 * m2;
	print(ret);
}
 

:::

----

### Geometry

W13 的主題是 Geometry ，一個我完全沒有概念的主題，課程從計算內積外積開始，一步步寫出包含 vector operation 的 template、判斷線段相交、點線段距、點集形成面積、極角排序、凸包等等問題。在 C++ 裡面可以寫幾何相關問題真的很酷。

:::spoiler Template

#include<bits/stdc++.h>
#define int long long
#define endl "\n"
#define AC cin.tie(0);ios_base::sync_with_stdio(0);
#define pb push_back
#define popb pop_back
#define popf pop_front
#define mp(a,b) make_pair(a,b)
#define F first
#define S second
#define INF 1e14
#define pii pair<int,int>
const int mod = 1e6+7;
const double eps = 1e-6;
const double pi = acos(-1);
using namespace std;
typedef pair<double,double> pt;
#define x first
#define y second
#define O point(0,0)

pt point(double x , double y){
	return mp(x,y);
}

double operator*(const pt &p1 , const pt &p2){
	return p1.x * p2.x + p1.y * p2.y; // 內積 
}
double operator^(const pt &p1 , const pt &p2){
	return p1.x * p2.y - p1.y * p2.x; // 外積 
}

pt operator+(const pt &p1 , const pt &p2){
	return mp(p1.x+p2.x , p1.y+p2.y);	
}
pt operator-(const pt &p1 , const pt &p2){
	return mp(p1.x-p2.x , p1.y-p2.y);	
}
pt operator*(const pt &p1 , int k){
	return mp(p1.x*k , p1.y*k);
}
pt operator/(const pt &p1 , int k){
	return mp(p1.x/k , p1.y/k);
}

double abs(const pt& p1){ // vector -> length
	return sqrt(p1*p1);
}

double areas(const vector<pt> v , const int sz){ // 多邊形面積 
	double area = 0;
	for(int i=0 ; i<sz-1 ; i++){
		area += v[i] ^ v[i+1];
	}
	return area;
}

double p3_area(const pt &o , const pt &a , const pt &b){
	return (a-o) ^ (b-o);
}

int sign(double a){ // double > = < 
	if(fabs(a) < eps) return 0;
	return a > 0 ? 1 : -1;
}

int ori(const pt& o , const pt& a , const pt& b){ // OA 轉 OB 方向 
	double cross = (a-o) ^ (b-o);
	return sign(cross);
	//順時針 or 逆時針 
}

bool btw(const pt &a , const pt &b , const pt &c){
	if(ori(a,b,c) != 0) return 0;
	return sign((c-a) * (c-b)) <= 0;
	// 若在c在直線 ab 上，判斷其是否在線段 ab 上 
}

bool banana(const pt &p1 , const pt &p2 , const pt &p3 , const pt &p4){
	int a123 = ori(p1,p2,p3);
	int a124 = ori(p1,p2,p4);
	int a341 = ori(p3,p4,p1);
	int a342 = ori(p3,p4,p2);
	if(a123 == 0 && a124 == 0){
		return btw(p1,p2,p3) || btw(p1,p2,p4) || btw(p3,p4,p1) || btw(p3,p4,p2);
	}
	return a123 * a124 <= 0 && a341 * a342 <= 0;
}

pt intersection(const pt &p1 , const pt &p2 , const pt &p3 , const pt &p4){
	double ap124 = fabs(p3_area(p1,p2,p4));
	double ap123 = fabs(p3_area(p1,p2,p3));
	return (p3*ap124 + p4*ap123) / (ap123+ap124);
}

double pt_to_seg_dis(const pt &a , const pt &b , const pt &c){ // dis of c->seg(a,b)
	if(sign((b-a)*(c-a)) >=0 && sign((a-b)*(c-b)) >=0){
		double area = fabs(p3_area(a,b,c));
		double len_seg = abs(b-a);
		return area/len_seg;
	}
	else return min(abs(a-c) , abs(b-c));
}

double pt_to_line_dis(const pt &a , const pt &b , const pt &c){ // dis of c->seg(a,b)
	if(ori(a,b,c) == 0) return 0;
	else{
		double area = fabs(p3_area(a,b,c));
		double len_seg = abs(b-a);
		return area/len_seg;
	}
}

bool cmp2(pt a , pt b){
		#define is_neg(t) (t.y < 0 || t.y==0 && t.x < 0)
		int A = is_neg(a) , B = is_neg(b); 
		if(A != B) return A<B;
		else return sign((a-O) ^ (b-O)) > 0;
}
vector<pt> angle_sort(vector<pt> v){	
	sort(v.begin(),v.end(),cmp2);
	return v;
}

vector<pt> convex_hull(vector<pt> dots){
	if(dots.size() == 1) return {dots[0]};
	sort(dots.begin() , dots.end());
	vector<pt> stk(1,{dots[0]});
	
	int t = 1;
	for(int i=1 ; i < dots.size() ; i++){
		while(t > 1 && ori(stk[t-2] , stk[t-1] , dots[i]) >= 0)
			stk.popb() , t--;
		stk.pb(dots[i]) , t++;
	}
	
	const int alr = t;
	for(int i=dots.size()-2 ; i>=0 ; i--){
		while(t > alr && ori(stk[t-2] , stk[t-1] , dots[i]) >= 0)
			stk.popb() , t--;
		stk.pb(dots[i]) , t++;
	}
	stk.popb();
	return stk;
}

signed main()
{
}

:::

----

### 長條圖最大矩形

Problem：[長條圖最大矩形](https://neoj.sprout.tw/problem/513/)

這題的概念是跟 W1 的單調隊列相關，枚舉每根柱子的最佳長度肯定不是一個明智的做法，我們發現，當從左掃到右，若新的柱子比舊的柱子還短，那舊的柱子就對答案沒有影響了(怎麼樣都包含它)，所以我們把每根柱子的長度及index放入遞增的單調隊列中，當我們要pop掉舊bar時，計算他可以延伸的最遠距離，就可以$O(n)$得到解答。


\
這題會讓我特別有印象的原因是因為我花了很多時間在debug，因為這題在計算部分很容易出錯，因此我一直拿到WA，在寫完這題之後，我以後就會盡量把code複雜的地方打註解。

:::spoiler Code

//長條圖最大矩形 
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
#define AC cin.tie(0);ios_base::sync_with_stdio(0);
#define mp(a,b) make_pair(a,b)
#define F first
#define S second
using namespace std;

stack<pair<int,int>> stk; // .F : value / .S : index
vector<int> v;

signed main()
{
	AC
	int n; cin >> n;
	int ans = -1;
	v.resize(n+1);
	for(int i=1 ; i<=n ; i++) cin >> v[i]; 
	stk.push(mp(0,0)); // 讓後面比較好做 
	
	for(int i=1 ; i<=n ; i++) // 由左掃到右，紀錄 包含第i根柱子的向左最遠距離 
	{
		int now = v[i] , mx = i; 
		// now紀錄 當前值 
		// mx 紀錄 每當有長 bar 被刪除，更新的 index 
		
		while(stk.top().F > now) // 當新 bar <= 前 bar ， 前 bar便沒有用了 
		{
			int tans = stk.top().F * (i - stk.top().S);
			ans = max(ans , tans); // 被刪除的bar的 ans 
			mx = stk.top().S; // 更新index 
			stk.pop();
		}
		stk.push(mp(now , mx));	
	}
	
	while(stk.top().F != 0) // 把沒做完的做完 
	{
		int tans = stk.top().F * (n+1 - stk.top().S);
		ans = max(ans , tans);
		stk.pop();
	}
	cout << ans << endl;
}

:::

----

### 染色遊戲

Problem：[染色遊戲](https://neoj.sprout.tw/problem/46/)

這題來自於W3的flood fill範圍，我們可以用BFS暴力模擬RYB的擴散情況，難點在於，混色過程非常容易出錯，擴散的過程也要想辦法避免重複擴散，而我在這題上投入了超過4個小時，中途重寫一次才把他做出來。

:::spoiler Code

#include<bits/stdc++.h>
#define int long long
#define endl "\n"
#define AC cin.tie(0);ios_base::sync_with_stdio(0);
#define pb push_back
#define mp(a,b) make_pair(a,b)
#define F first
#define S second
#define INF 1e14
const int mod = 1e9+7;
using namespace std;


struct inf
{
	int x , y;
	int color;
	int level;
};
int xdrt[8] = {1,1,1,-1,-1,-1,0,0};
int ydrt[8] = {-1,0,1,-1,0,1,-1,1};
vector<vector<int>> v;
queue<inf> Q;
map<int,int> ans;
int ans_ , n;

int tgtoint(char c)
{
	if(c == 'R') return 2;
	if(c == 'Y') return 3;
	if(c == 'B') return 5;
	if(c == 'O') return 6;
	if(c == 'P') return 10;
	if(c == 'G') return 15;
	if(c == 'D') return 30;
}

void func(int tg)
{
	int now_level = 0;
	while(!Q.empty())
	{
		while(Q.front().level == now_level)
		{
			inf now = Q.front();
			Q.pop();
			for(int d=0 ; d<8 ; d++)
			{
				int me_x = now.x + xdrt[d];
				int me_y = now.y + ydrt[d];
				if(me_x >= n || me_x < 0 || me_y >= n || me_y < 0) continue;
				//cout << me_x << " " << me_y << " " << v[me_x][me_y] << endl;
				if (v[me_x][me_y] == now.color) continue;
				else if(v[me_x][me_y] == -1)
				{
					v[me_x][me_y] = now.color;
					ans[now.color]++;
				}
				else
				{
					ans[v[me_x][me_y]]--;
					if(v[me_x][me_y] % 2 != 0 && now.color % 2 == 0) v[me_x][me_y] *= 2;
					if(v[me_x][me_y] % 3 != 0 && now.color % 3 == 0) v[me_x][me_y] *= 3;
					if(v[me_x][me_y] % 5 != 0 && now.color % 5 == 0) v[me_x][me_y] *= 5;
					ans[v[me_x][me_y]]++;
				}
				Q.push({me_x , me_y , v[me_x][me_y] , now.level+1});
			}
		}
		now_level++;
		//cout << ans[tg] << " ";
		ans_ = max(ans_ , ans[tg]);
		
	}
}

signed main()
{
	int T;
	cin >> T;
	while(T--)
	{
		cin >> n;
		ans_ = 0;
		ans.clear();
		v.clear();
		v.resize(n,vector<int>(n , -1));
		while(!Q.empty()) Q.pop();
		
		for(int i=0 ; i<3 ; i++)
		{
			pair<int,int> Y,B,R;
			char c; cin >> c;
			if(c == 'R') cin >> R.F >> R.S , Q.push({R.F,R.S,2,0}) , ans[2]++ , v[R.F][R.S] = 2;
			if(c == 'Y') cin >> Y.F >> Y.S , Q.push({Y.F,Y.S,3,0}) , ans[3]++ , v[Y.F][Y.S] = 3;
			if(c == 'B') cin >> B.F >> B.S , Q.push({B.F,B.S,5,0}) , ans[5]++ , v[B.F][B.S] = 5;	
		}
		char tg;
		cin >> tg;
		func(tgtoint(tg));
		cout << ans_ << endl;
		
	}
}

:::

----

### Merge sort & 逆序數對

在高一上的自主學習中，我也以學習競程作為主題，
而當初有實作過三種簡單的 sort (bubble sort / selection sort / insertion sort)，
而學完devide and conquer以後，我終於有能力可以實作merge sort了。
在W6，除了習得merge sort外，還寫掉了一個經典例題「逆序數對」，逆序數對的概念幾乎都以merge sort的過程作延伸，只要在merge的過程，順便紀錄橫跨兩邊的逆序數對數量，就可以做出來了。

:::spoiler Code (Merge sort)

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

vector<int> v;

void merge_sort(int n , int index)
{
	if(n == 1) return;
	// devide
	int len1 = n/2; // len1 -> 多的那邊 
	int len2 = n - len1;
	int arr1[len1], arr2[len2];
	merge_sort(len1 , index);
	merge_sort(len2 , index+len1);
	for(int i=0 ; i<len1 ; i++) arr1[i] = v[index + i];
	for(int i=0 ; i<len2 ; i++) arr2[i] = v[index + len1 + i];
	
	int ptr1 = 0 , ptr2 = 0;
	for(int i=0 ; i<n ; i++)
	{
		if(ptr1 < len1)
		{
			if(ptr2 >= len2) v[i+index] = arr1[ptr1++];
			else if(arr1[ptr1] < arr2[ptr2]) v[i+index] = arr1[ptr1++];
			else v[i+index] = arr2[ptr2++];
		}
		else v[i+index] = arr2[ptr2++];
	}	
} 

signed main()
{
	int all ; cin >> all;
	v.resize(all);
	for(int i=0 ; i<all ; i++) cin >> v[i];
	merge_sort(all , 0);
	for(int i : v) cout << i << " ";
}

:::

---

### 參考資料

#### [Sprout 線上課程、作業](https://sprout.tw/algo2022/)
#### [Sprout online judge](https://neoj.sprout.tw/group/43/)