CESE 自學筆記
===
**背景音樂**
保持耐心斬破困難完成一切------>避免爆氣
{%youtube DXT9dF-WK-I %}
{%youtube QrJn8MJHfDE %}
# 一、 Introductory Problems
:::spoiler 1. Weird Algorithm
### (1) 題目

[題目連結](https://cses.fi/problemset/task/1068)

### (2) 思考方向

### (3) 解答

#include <iostream>
using namespace std;
 
int main(int argc, char *argv[]){
	long long int n;
	cin >> n;
	cout << n << " ";
	while(n!=1){
		if(n%2==1){
			n = n*3+1;
		}
		else{
			n/=2;
		}
		cout << n << " ";
	}
	cout << endl;
	return 0;
}

:::
:::spoiler 2. Missing Number
### (1) 題目

[題目連結](https://cses.fi/problemset/task/1083)

### (2) 思考方向

### (3) 解答

#include <iostream>
using namespace std;
 
int main(int argc, char *argv[]){
	int n, number, total=0;
	cin >> n;
	bool arr[n];
	for(int i=0;i<n;i++){
		arr[i] = false;
	}
	while(total<n-1){
		cin >> number;
		arr[number-1]=true;
		total++;
	}
	for(int i=0;i<n;i++){
		if(arr[i]==false){
			cout << i+1 << endl;
			break;
		}
	}
	return 0;
}

:::
:::spoiler 3. Repetitions
### (1) 題目

[題目連結](https://cses.fi/problemset/task/1069)

### (2) 思考方向

### (3) 解答

#include <iostream>
#include <string>
#include <cstring>
#define ARRAYLENGTHS 1000000
using namespace std;
 
int main(int argc, char *argv[]){
	long long int length, total, i, j, k, max=0;
	string input;
	cin >> input;
	length = input.length();
	for(i=0;i<length-max;i++){
		if(input[i]==input[i+max]){
			j=1;
			while(input[i]==input[i+j]&&i+j<length){
				j++;
			}
			if(j>max){
				max = j;
			}
		}
	}
	cout << max << endl;
	return 0;
}

:::
:::spoiler 4. Increasing Array
### (1) 題目

[題目連結](https://cses.fi/problemset/task/1094)

### (2) 思考方向
* 陣列差的計算
### (3) 解答

#include <iostream>
#include <string>
#define ARRAYLENGTHS 1000000
using namespace std;

int main(int argc, char *argv[]){
	int n;
	cin >> n;
	long long int arr[n], time=0;
	for(int i=0;i<n;i++){
		cin >> arr[i];
		if(i>0){
			if(arr[i]<arr[i-1]){
				cout << arr[i-1]-arr[i] << endl;
				time += arr[i-1]-arr[i];
				arr[i] = arr[i-1];
			}
		}
	}
	cout << time << endl;
	return 0;
} 

:::
:::spoiler 5. Permutations
### (1) 題目

[題目連結](https://cses.fi/problemset/task/1070)

### (2) 思考方向
* 先偶數再奇數
* 注意是否差都是大於 1
### (3) 解答

#include <iostream>
#include <string>
#define ARRAYLENGTHS 1000000
using namespace std;

int main(int argc, char *argv[]){
	int n, gap, total=0;
	cin >> n;
	if(n>3||n==1){
		if(n%2==1){
			for(int i=n-1;i>0;i-=2){
				cout << i << " ";
			}
			for(int i=n;i>0;i-=2){
				cout << i << " ";
			}
		}
		else if(n==4){
			cout << 2 << " " << 4 << " " << 1 << " " << 3 << endl;
		}
		else{
			for(int i=n;i>0;i-=2){
				cout << i << " ";
			}
			for(int i=n-1;i>0;i-=2){
				cout << i << " ";
			}
		}
		cout << endl;
	}
	else{
		cout << "NO SOLUTION\n";
	}
	return 0;
} 

:::
:::spoiler 6. Number Spiral
### (1) 題目

[題目連結](https://cses.fi/problemset/task/1071)

### (2) 思考方向
* 用計算的方式
* 

### (3) 解答

#include <iostream>
#define ARRAYLENGTHS 1000000
using namespace std;

int main(int argc, char *argv[]){
	long long int t, x, y, ans;
	cin >> t;
	while(t--){
		cin >> x >> y;
		if((x>y&&x%2==1)||(x<y&&y%2==0)){
			if(x>y){
				ans = x*x-2*x+1+y;
			}
			else{
				ans = y*y-2*y+1+x;
			}
		}
		else{
			if(x>y){
				ans = x*x-y+1;
			}
			else{
				ans = y*y-x+1;
			}
		}
		cout << ans << endl;
	}
	return 0;
} 

:::
:::spoiler 7. Two Knights
### (1) 題目

[題目連結](https://cses.fi/problemset/task/1072)

### (2) 思考方向
* 觀念解析
{%youtube RlpM5N-ttcU%}
* 排列組合
* 騎士只能攻擊 L 型

### (3) 解答

#include <iostream>
using namespace std;

int main(int argc, char *argv[]){
	long long int ans, n;
	cin >> n;
	for(long long int i=1;i<=n;i++){
		ans = (i*i*(i*i-1))/2-4*(i-1)*(i-2);
		cout << ans << endl; 
	}
	return 0;
} 

:::
:::spoiler 8. Two Sets
### (1) 題目

[題目連結](https://cses.fi/problemset/task/1092)

### (2) 思考方向
* 觀念解析
{%youtube OtZ81ydc3WA %}
* 分類: 總和、個數

### (3) 解答

#include <iostream>
using namespace std;

int main(int argc, char *argv[]){
	long long int n, sum, count;
	cin >> n;
	sum = (n*(n+1))/2;
	//	分辨是否可分解 
	if(sum%2==0){
		bool arr[n];
		for(int i=0;i<n;i++){
			arr[i] = false;
		}
		cout << "YES\n";
		//	分辨個數 
		if(n%2==1){
			count = n/2+1;
			//	分類 
			for(long long int i=1;i<=n/4+1;i++){
				arr[i-1] = true;
				arr[n-i-1] = true;
			}
			//	印出	
			cout << count << endl;
			for(long long int i=0;i<n;i++){
				if(arr[i]){
					cout << i+1 << " "; 
				}
			}
			cout << endl << count-1 << endl;
			for(long long int i=0;i<n;i++){
				if(!arr[i]){
					cout << i+1 << " "; 
				}
			}
		}
		else{
			count = n/2;
			//	分類 
			for(int i=1;i<=n/4;i++){
				arr[i-1] = true;
				arr[n-i] = true;
			}
			//	印出 
			cout << count << endl;
			for(int i=0;i<n;i++){
				if(arr[i]){
					cout << i+1 << " "; 
				}
			}
			cout << endl << count << endl;
			for(int i=0;i<n;i++){
				if(!arr[i]){
					cout << i+1 << " "; 
				}
			}
			cout << endl;
		}
	}
	else{
		cout << "NO\n";
	}
	return 0;
} 

:::
:::spoiler 9. Bit String
### (1) 題目

[題目連結](https://cses.fi/problemset/task/1617)

### (2) 思考方向
* 觀念解析
{%youtube Qda1zjbca1A %}
* mod 要分開 mod ，不然值會爆掉

### (3) 解答

#include <iostream>
#define mod 1000000007
using namespace std;

int main(int argc, char *argv[]){
	long long int n, ans=1;
	cin >> n;
	for(int i=0;i<n;i++){
		ans *= 2;
		ans %=mod;
	}
	cout << ans << endl;
	return 0;
} 

:::
:::spoiler 10. Trailing Zeros
### (1) 題目

[題目連結](https://cses.fi/problemset/task/1618)

### (2) 思考方向
* 觀念解析
{%youtube LB1pl32O3hA %}

### (3) 解答

#include <iostream>
using namespace std;

int main(int argc, char *argv[]){
	long long int n, ans=0;
	cin >> n;
	for(long long int i=5;i<=n;i+=5){
		int temp=i;
		while(temp%5==0){
			ans++;
			temp/=5;
		}
	}
	cout << ans << endl;
	return 0;
} 

:::
:::spoiler 11. Coin Piles
### (1) 題目

[題目連結](https://cses.fi/problemset/task/1754)

### (2) 思考方向
* 觀念解析
{%youtube gtqJJlvRpw8 %}

### (3) 解答

#include <iostream>
using namespace std;

int main(int argc, char *argv[]){
	long long int t, A, B, time;
	cin >> t;
	while(t--){
		cin >> A >> B;
		time = (A+B)/3;
		if((A+B)%3==0&&A>=time&&B>=time){
			cout << "YES\n";
		}
		else{
			cout << "NO\n";
		}
	}
	return 0;
} 

:::
:::spoiler 12. Palindrome Reorder
### (1) 題目

[題目連結](https://cses.fi/problemset/task/1755)

### (2) 思考方向
* 觀念解析
{%youtube 4HiugIWutCE %}
* 重新排列換字元

### (3) 解答

#include <iostream>
#include <string>
using namespace std;

int main(int argc, char *argv[]){
	long long int n;
	bool flag=true;
	char temp;
	string s;
	cin >> s;
	n = s.length();
	long long int arr[26]={};
		//	重新排列
		for(int i=0;2*i<=n&&flag;i++){
			if(s[i]!=s[n-1-i]){
				int j;
				for(j=n-2-i;j>i;j--){
//					cout << "(" << i << "," << j << "," << n-1-i << ")" << endl;
					if(s[i]==s[j]){
						temp = s[n-1-i];
						s[n-1-i] = s[j];
						s[j] = temp;
						break;
					}
					else if(s[n-1-i]==s[j]){
						temp = s[i];
						s[i] = s[j];
						s[j] = temp;
						break;
					}
				}
				if(j==i){
					flag = false;
				}
			}
		} 
		//	印出 
		if(!flag){
			cout << "NO SOLUTION\n";
//			cout << s << endl;
		}
		else{
			cout << s << endl;
		}
	return 0;
}

:::
:::spoiler 13. Gray Code
### (1) 題目
[題目連結](https://cses.fi/problemset/task/2205)

### (2) 思考方向
* 觀念解析
{%youtube zYa1B9nfr64 %}

### (3) 解答

#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
using namespace std;

long long int ans=0;
void conduct(long long int n);

int main(int argc, char *argv[]){
	long long int n;
	cin >> n;
	conduct(n);
	return 0;
} 

void conduct(long long int n){
	for(long long int i=0; i<(1<<n);i++){
		long long int val = i^(i>>1);
//		long long int temp = (i>>1);
		
		bitset<32> arr(val);
		string ans = arr.to_string();
//		cout << "(" << val << ")" << endl;
//		for(int j = n-1; j>=0 ;j--){
//			cout << ((i>>j)&1);
//		}
//		cout << endl;
//		for(int j = n-1; j>=0 ;j--){
//			cout << ((temp>>j)&1);
//		}
//		cout << endl;
		for(int j = 32-n; j<32 ;j++){
			cout << ans[j];
		}
		
		cout << endl;
	}
}

:::
:::spoiler 14. Tower of Hanoi
### (1) 題目
[題目連結](https://cses.fi/problemset/task/2165/)

### (2) 思考方向
* 觀念解析
{%youtube pugseXz0gEk %}

### (3) 解答

#include <iostream>
using namespace std;

void Hanoi(int, int, int, int);

int main(int argc, char *argv[]){
	int n;
	cin >> n;
	cout << (2<<(n-1))-1 << endl;
	Hanoi(n,1,2,3);
	return 0;
}

void Hanoi(int n, int left, int middle, int right){
	if(n==1){
		cout << left << " " << right << endl;
		return;
	}
	else{
		Hanoi(n-1,left,right,middle);
		cout << left << " " << right << endl;
		Hanoi(n-1,middle,left,right);
	}
}

:::
:::spoiler 15. Creating Strings
### (1) 題目

[題目連結](https://cses.fi/problemset/task/1622)

### (2) 思考方向
* 觀念解析
{%youtube M_lo8MkFMOI %}
* Vector 用法

### (3) 解答

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

int main(int argc, char *argv[]){
	int n, total;
	string input;
	cin >> input;
	n = input.length();
	sort(input.begin(),input.end());
	vector<string> ans;
	do{
		ans.push_back(input);
	}while(next_permutation(input.begin(),input.end()));
	cout << ans.size() << endl;
	for(auto x : ans){
		cout << x << endl;
	}
	return 0;
}

:::
:::spoiler 16. Apple Division
### (1) 題目

[題目連結](https://cses.fi/problemset/task/1623/)

### (2) 思考方向
* 觀念解析
{%youtube Jrt4FntJIyM %}
* 利用位元做排列組合
==i 用bit去思考做1與0的分類，j則是把所有1加總後看差==

### (3) 解答

#include <iostream>
#include <cmath>
#include <vector>
#include <climits>
using namespace std;

int main(int argc, char *argv[]){
	int n;
	long long int total=0, ans=LLONG_MAX;
	cin >> n;
	vector<long long int> arr(n);
	for(int i=0;i<n;i++){
		cin >> arr[i];
		total += arr[i];
	}
	for(long long int i=0;i<(1<<n);i++){
		long long int s = 0;
		for(long long int j=0;j<n;j++){
			if(i&(1<<j)){
				s += arr[j];
			}
		}
		cout << endl;
		long long int cur = abs((total-s)-s);
		ans = min(ans,cur);
	}
	cout << ans << endl;
	return 0;
}

:::
:::spoiler 17. Chessboard and Queens
### (1) 題目

[題目連結](https://cses.fi/problemset/task/1624)

### (2) 思考方向
* 觀念解析
{%youtube dm70QwzBsMc %}
* 行、列、對角的刪去法
* ==Depth-first search==

### (3) 解答

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
using namespace std;

bool rightdiagram[30];
bool leftdiagram[30];
bool column[8];
bool table[8][8];
bool situation[8][8];
long long int ans=0;
char arr[8][8];

void solved(int);

int main(int argc, char *argv[]){
	for(int i=0;i<8;i++){
		for(int j=0;j<8;j++){
			cin >> arr[i][j];
			if(arr[i][j]=='*'){
				situation[i][j] = true;
			}
		}
	}
	solved(0);
	cout << ans << endl;
	return 0;
}

void solved(int queen){
	if(queen==8){
		ans++;
		return;
	}
	else{
		
		for(int curcolumn=0;curcolumn<8;curcolumn++){
			if(situation[queen][curcolumn]==false&&column[curcolumn]==false&&leftdiagram[queen+curcolumn]==false&&rightdiagram[queen-curcolumn+7]==false){
				table[queen][curcolumn]=column[curcolumn]=leftdiagram[queen+curcolumn]=rightdiagram[queen-curcolumn+7]=true;
				solved(queen+1);
				table[queen][curcolumn]=column[curcolumn]=leftdiagram[queen+curcolumn]=rightdiagram[queen-curcolumn+7]=false;
			}
		}
		return;
	}
}

:::
:::spoiler 18. Digit Queries
### (1) 題目

[題目連結](https://cses.fi/problemset/task/2431)

### (2) 思考方向
* 觀念解析
{%youtube QAcH8qD9Pe0 %}

### (3) 解答

:::
:::spoiler 19. Grid Paths
### (1) 題目

[題目連結]()

### (2) 思考方向
* 觀念解析
{%youtube %}

### (3) 解答

:::
# 二、 Sorting and Searching
:::spoiler 1. Distinct Numbers
### (1) 題目

[題目連結]()

### (2) 思考方向
* 觀念解析
{%youtube %}

### (3) 解答

:::
:::spoiler 2. Apartments
### (1) 題目

[題目連結]()

### (2) 思考方向
* 觀念解析
{%youtube %}

### (3) 解答

:::
:::spoiler 3. Ferris Wheel
### (1) 題目

[題目連結]()

### (2) 思考方向
* 觀念解析
{%youtube %}

### (3) 解答

:::
:::spoiler 4. Concert Tickets
### (1) 題目

[題目連結]()

### (2) 思考方向
* 觀念解析
{%youtube %}

### (3) 解答

:::
:::spoiler 5. Restaurant Customers
### (1) 題目

[題目連結]()

### (2) 思考方向
* 觀念解析
{%youtube %}

### (3) 解答

:::
:::spoiler 6. Movie Festival
### (1) 題目

[題目連結]()

### (2) 思考方向
* 觀念解析
{%youtube %}

### (3) 解答

:::
:::spoiler 7. Sum of Two Values
### (1) 題目

[題目連結]()

### (2) 思考方向
* 觀念解析
{%youtube %}

### (3) 解答

:::
:::spoiler 8. Maximum Subarray Sum
### (1) 題目

[題目連結]()

### (2) 思考方向
* 觀念解析
{%youtube %}

### (3) 解答

:::
:::spoiler 9. Stick Lengths
### (1) 題目

[題目連結]()

### (2) 思考方向
* 觀念解析
{%youtube %}

### (3) 解答

:::
:::spoiler 10. Missing Coin Sum
### (1) 題目

[題目連結]()

### (2) 思考方向
* 觀念解析
{%youtube %}

### (3) 解答

:::
:::spoiler 11. Collecting Numbers
### (1) 題目

[題目連結]()

### (2) 思考方向
* 觀念解析
{%youtube %}

### (3) 解答

:::
:::spoiler 12. Collecting Numbers II
### (1) 題目

[題目連結]()

### (2) 思考方向
* 觀念解析
{%youtube %}

### (3) 解答

:::
:::spoiler 13. Playlist
### (1) 題目

[題目連結]()

### (2) 思考方向
* 觀念解析
{%youtube %}

### (3) 解答

:::
:::spoiler 14. Towers
### (1) 題目

[題目連結]()

### (2) 思考方向
* 觀念解析
{%youtube %}

### (3) 解答

:::
:::spoiler 15. Traffic Lights
### (1) 題目

[題目連結]()

### (2) 思考方向
* 觀念解析
{%youtube %}

### (3) 解答

:::
:::spoiler 16. Josephus Problem I
### (1) 題目

[題目連結]()

### (2) 思考方向
* 觀念解析
{%youtube %}

### (3) 解答

:::
:::spoiler 17. Joesphus Problem II
### (1) 題目

[題目連結]()

### (2) 思考方向
* 觀念解析
{%youtube %}

### (3) 解答

:::
:::spoiler 18. Nested Ranges Check
### (1) 題目

[題目連結]()

### (2) 思考方向
* 觀念解析
{%youtube %}

### (3) 解答

:::
:::spoiler 19. Nested Ranges Count
### (1) 題目

[題目連結]()

### (2) 思考方向
* 觀念解析
{%youtube %}

### (3) 解答

:::
:::spoiler 20. Room Allocation
### (1) 題目

[題目連結]()

### (2) 思考方向
* 觀念解析
{%youtube %}

### (3) 解答

:::
:::spoiler 21. Factory Machines
### (1) 題目

[題目連結]()

### (2) 思考方向
* 觀念解析
{%youtube %}

### (3) 解答

:::
:::spoiler 22. Tasks and Deadlines
### (1) 題目

[題目連結]()

### (2) 思考方向
* 觀念解析
{%youtube %}

### (3) 解答

:::
:::spoiler 23. Reading Books
### (1) 題目

[題目連結]()

### (2) 思考方向
* 觀念解析
{%youtube %}

### (3) 解答

:::
:::spoiler 24. Sum of Three Values
### (1) 題目

[題目連結]()

### (2) 思考方向
* 觀念解析
{%youtube %}

### (3) 解答

:::
:::spoiler 25. Sum of Four Values
### (1) 題目

[題目連結]()

### (2) 思考方向
* 觀念解析
{%youtube %}

### (3) 解答

:::
:::spoiler 26. Nearest Smaller Values
### (1) 題目

[題目連結]()

### (2) 思考方向
* 觀念解析
{%youtube %}

### (3) 解答

:::
:::spoiler 27. Subarray Sums I
### (1) 題目

[題目連結]()

### (2) 思考方向
* 觀念解析
{%youtube %}

### (3) 解答

:::
:::spoiler 28. Subarray Sums II
### (1) 題目

[題目連結]()

### (2) 思考方向
* 觀念解析
{%youtube %}

### (3) 解答

:::
:::spoiler 29. Subarray Divisibility
### (1) 題目

[題目連結]()

### (2) 思考方向
* 觀念解析
{%youtube %}

### (3) 解答

:::
:::spoiler 30. Subarray Distinct Values
### (1) 題目

[題目連結]()

### (2) 思考方向
* 觀念解析
{%youtube %}

### (3) 解答

:::
:::spoiler 31. Array Division
### (1) 題目

[題目連結]()

### (2) 思考方向
* 觀念解析
{%youtube %}

### (3) 解答

:::
:::spoiler 32. Sliding Window Median
### (1) 題目

[題目連結]()

### (2) 思考方向
* 觀念解析
{%youtube %}

### (3) 解答

:::
:::spoiler 33. Sliding Window Cost
### (1) 題目

[題目連結]()

### (2) 思考方向
* 觀念解析
{%youtube %}

### (3) 解答

:::
:::spoiler 34. Movie Festival II
### (1) 題目

[題目連結]()

### (2) 思考方向
* 觀念解析
{%youtube %}

### (3) 解答

:::
:::spoiler 35. Maximum Subarray Sum II
### (1) 題目

[題目連結]()

### (2) 思考方向
* 觀念解析
{%youtube %}

### (3) 解答

:::
# 三、 Dynamic Programming
# 四、 Graph Algorithms
# 五、 Range Queries
# 六、 Tree Algorithms
# 七、 Mathematics
# 八、 String Algorithms
# 九、 Geometry
# 十、 Advanced Techniques
# 十一、 Additional Problems