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

資源統整

課表及導流

(點擊主題之超連結，會連結到該周課程的題目code)

次數	主題
1st 03/05	Data structure && Monotone queue
2nd 03/12	Binary tree && Complexity
3rd 03/19	Heap && Flood fill
4th 03/26	Enumerate && Binary search
5th 04/02	Greedy
6th 04/09	Divide and Conquer
7th 04/16	Dynamic Program 01
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

學習成果

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^{l o g_{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優化：矩陣優化，單調優化

\to

有限背包
位元dp
鄰接矩陣

\to

路徑數

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

Week 11 Random

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

手寫作業內容：Fenwick tree, lowbit

Week 12 Graph 1

課程內容：
Topological Sort

\to

determine DAG
Disjoint set

\to

Component
Minimum Spanning Tree

\to

Kruskal and Prim algorithm
Shortest Path

\to

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

延伸成果

除了上課教到的東西，我將感興趣的內容再延伸學習呈現，或是把一些我很喜歡的內容挑出來討論。

例如在Binary tree單元中學到如何建造二元樹，但會有歪斜的問題，因為我想要更加了解std::set是如何被做出來的，所以我就在有空的時候，上網找文章，試著自己做一顆AVL tree。

LaTex

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

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

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

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

Limitation -> Calculus

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

微積分學習歷程（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 樹是一種非常有效的二元搜尋樹，常被用於需要快速查詢和更新的場合。

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

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);
}

強歸納法

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

Problem

我想用歸納法證明它。從前學的歸納法是透過

n = 1

成立，設

n = k

存在，證明

n = k + 1

成立，於是我試著證明

n = k + 1

成立，卻怎麼也想不到解。
在我苦惱不已時，朋友幫我指點迷經，他告訴我，有一種東西叫做「強歸納法」，而我上網查了資料，得到：

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

名詞解釋（來自資芽Week 9 Hw）

P 問題 : 是由存在多項式複雜度求解演算法的問題形成的集合。
NP 問題 : 是由存在多項式複雜度驗證演算法的問題形成的集合。
NP-hard 問題 : 可以使得任意 NP 問題多項式時間歸約到的問題。
NP_complete 問題 : NP

\cap

NP-hard

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

Matrix

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

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++ 裡面可以寫幾何相關問題真的很酷。

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：長條圖最大矩形

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

O (n)

得到解答。

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

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：染色遊戲

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

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的過程，順便紀錄橫跨兩邊的逆序數對數量，就可以做出來了。

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 學習紀錄 – C++ 演算法學習

目錄

1. 學習成果

2. 延伸成果（主要部分）

資源統整

課表及導流

學習成果

Week 1 Data structure

Week 2 Binary tree && Complexity

Week 3 Heap && Flood fill

Week 4 Enumerate && Binary search

Week 5 Greedy

Week 6 Divide and Conquer

Week 7 Dynamic Program 01

Week 8 1st Certification exam

Week 9 Dynamic Program 02

Week 10 Dynamic Program 03

Week 11 Random

Week 12 Graph 1

Week 13 Geometry

Week 14 Segment tree

延伸成果

除了上課教到的東西，我將感興趣的內容再延伸學習呈現，或是把一些我很喜歡的內容挑出來討論。

例如在Binary tree單元中學到如何建造二元樹，但會有歪斜的問題，因為我想要更加了解std::set是如何被做出來的，所以我就在有空的時候，上網找文章，試著自己做一顆AVL tree。

LaTex

Limitation -> Calculus

AVL tree

強歸納法

P and NP problems

Matrix

Geometry

長條圖最大矩形

染色遊戲

Merge sort & 逆序數對

參考資料

Sprout 線上課程、作業

Sprout online judge

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

目錄

1. 學習成果

2. 延伸成果（主要部分）

資源統整

課表及導流

學習成果

Week 1 Data structure

Week 2 Binary tree && Complexity

Week 3 Heap && Flood fill

Week 4 Enumerate && Binary search

Week 5 Greedy

Week 6 Divide and Conquer

Week 7 Dynamic Program 01

Week 8 1st Certification exam

Week 9 Dynamic Program 02

Week 10 Dynamic Program 03

Week 11 Random

Week 12 Graph 1

Week 13 Geometry

Week 14 Segment tree

延伸成果

除了上課教到的東西，我將感興趣的內容再延伸學習呈現，或是把一些我很喜歡的內容挑出來討論。

例如在Binary tree單元中學到如何建造二元樹，但會有歪斜的問題，因為我想要更加了解std::set是如何被做出來的，所以我就在有空的時候，上網找文章，試著自己做一顆AVL tree。

LaTex

Limitation -> Calculus

AVL tree

強歸納法

P and NP problems

Matrix

Geometry

長條圖最大矩形

染色遊戲

Merge sort & 逆序數對

參考資料

Sprout 線上課程、作業

Sprout online judge

Read more

小測驗

行政幹訓（職責與歷屆習慣）

管理學討論問題與摘要 - 系學會長

第 1 討論聚 - SightPath 啟動