# 程式學習資源
# 學習資源與題單
## 學習資源:
https://hackmd.io/@LittlePants/Hyw_rueGK (新手村)
[https://yuihuang.com/about](https://yuihuang.com/about/) (竹女黃惟甚麼都有的blog)
[https://hackmd.io/@sa072686/cp/%2Fa-](https://hackmd.io/@sa072686/cp/%2Fa-xt96VKTAqBmzpmXjkU_Q(%E7%AB%B6%E7%A8%8B%E5%9F%BA%E7%A4%8E)) (完整的語法教學&演算法教學)
https://www.csie.ntu.edu.tw/~b98902112/cpp_and_algo/ (基礎語法&演算法)
https://sites.google.com/site/pcshic/zi-xun-pei-xun (板中教材)
[https://hackmd.io/@CLKO/B18yT_i5Z?type=view](https://hackmd.io/@CLKO/B18yT_i5Z?type=view(%E5%AF%A6%E9%A9%97%E8%B3%87%E6%BA%90))
https://hackmd.io/@nehs-iced-7th/Hk9_m5KH_/https%3A%2F%2Fhackmd.io%2F%40nehs-iced-7th%2FSkut4WffY (實驗高中教材)
https://shiyu0318.github.io/2023/02/Sort-Algorithm/
(一堆排序演算法)
[xt96VKTAqBmzpmXjkU_Q](https://hackmd.io/@sa072686/cp/%2Fa-xt96VKTAqBmzpmXjkU_Q(%E7%AB%B6%E7%A8%8B%E5%9F%BA%E7%A4%8E)) (競程基礎)
https://cp.wiwiho.me/
https://hackmd.io/@pr3pony/HysEHoYe8 (競程較難)
:::success
我正在看
https://github.com/orgs/HHSH-CYSH-WGSH-HSNU-Summer-Camp/repositories (github)
https://docs.google.com/spreadsheets/d/1vc8jznRk1LOc2ksLs3xvhtngfv4tB4XKsMmL-kpM5lA/edit?usp=sharing (題單)
CSES Sorting & Searching
Codeforces EDU Binary Search + Two Pointer
Introductory problems
https://www.youtube.com/playlist?list=PL_815psSzw1FATzqwJdWaWJHGcH4F6DUz (競程較難)
:::
https://hackmd.io/@alanlai/Byh58hzIY/%2FJdtIMHaSR7GVzveIXOkkIg (競程進階技巧)
https://hackmd.io/@hackerifyouwant/BJQll0Kad (各種程式 EX:資安 機器學習)
https://gunjyo0817.github.io/2020/11/07/2020-SCIST-Security-Note-Web/ (資安)
## 題單:
### APCS考古第一題:
i428 - 巴士站牌
https://zerojudge.tw/ShowProblem?problemid=i428
h081 - 程式交易
https://zerojudge.tw/ShowProblem?problemid=h081
f605 - 購買力
https://zerojudge.tw/ShowProblem?problemid=f605
g275-七言對聯
https://zerojudge.tw/ShowProblem?problemid=g275
e286-籃球比賽
https://zerojudge.tw/ShowProblem?problemid=e286
h026-猜拳
https://zerojudge.tw/ShowProblem?problemid=h026
j605-程式考試
https://zerojudge.tw/ShowProblem?problemid=j605
c290-秘密差
https://zerojudge.tw/ShowProblem?problemid=c290
i399.-數字遊戲
https://zerojudge.tw/ShowProblem?problemid=i399
b964-成績指標
https://zerojudge.tw/ShowProblem?problemid=b964
g595-修補圍籬
https://zerojudge.tw/ShowProblem?problemid=g595
f312-人力分配
https://zerojudge.tw/ShowProblem?problemid=f312
c294-三角形辨別
https://zerojudge.tw/ShowProblem?problemid=c294
# vector 應用與一維矩陣
## 一維
當提到 C++ 中的向量（vector）時，它是標準模板庫（STL）中的一個容器，用於在連續的記憶體位置上儲存元素，並提供了方便的方法來操作這些元素、更進階的矩陣格式，可以完成矩陣沒辦法達到的新增元素等等……..其內建有許多特別功能與函式庫，是初學者要學的重要技巧之一。
以下是一個基本的 C++ 向量的使用示例和一些相關的操作：
首先:要先引入標頭檔<vector> <algorithm>(sort排序)
一開始可直接先引入萬用標頭檔<bits/stdc++.h>
```cpp
#include <vector>
```
可以把他想成一維陣列，其宣告為vector<型態>名子
```cpp
vector<int>a
```
會相等於int a[10][10]
但vector不需要先宣告其大小(解題陣列題目時自由許多)
固定存入資料:矩陣名={1,2,3,4,5}
```cpp
#include <bits/stdc++.h>
using namespace std;
int main(){
vector<int>a;
a={2,3,4};
for(int i=0;i<3;++i){
cout<<a[i]<<" ";
}
return 0;
}
```
添加元素至vector(矩陣無法做到的事)
名.push_back(元素)
```cpp
#include <bits/stdc++.h>
using namespace std;
int main(){
vector<int>a;
for(int i=0;i<3;++i){
int temp;
cin>>temp;
a.push_back(temp);
}
return 0;
}
```
sort 排序
sort(v.begin(), v.end());<algorithm>
```cpp
#include<bits/stdc++.h>
using namespace std;
int main() {
int ar[] = {4, 5, 8, 3, 7, 1, 2, 6, 10, 9};
sort(arr, arr+10);
for (int i = 0; i < 10; i++) {
cout << a[i] << " ";
}
cout << std<<endl;
return 0;
}
```
輸出如下:
```jsx
2 3 4 5 6 7 8 9 10
```
降序排列:
```cpp
#include<bits/stdc++.h>
using namespace std;
int main() {
int a[] = {4, 5, 8, 3, 7, 1, 2, 6, 10, 9};
sort(arr, arr+10, std::greater<int>());
for (int i = 0; i < 10; i++) {
cout << a[i] << " ";
}
cout << std<<endl;
return 0;
}
```
輸出如下:
```cpp
10 9 8 7 6 5 4 3 2 1
```
排序字串 sort string (升序)
```cpp
#include<bits/stdc++.h>
int main() {
string s = "eacdb";
sort(s.begin(), s.end(), std::less<char>());
for (char c : s) {
cout << c << " ";
}
cout << std<<endl;
return 0;
}
```
輸出如下:
```cpp
a b c d e
```
排序 struct
```cpp
#include<bits/stdc++.h>
struct student {
std::string name;
int score;
};
bool mycompare(student s1, student s2){
return s1.score > s2.score;
}
int main() {
student st[4];
st[0].name = "bob";
st[0].score = 70;
st[1].name = "cindy";
st[1].score = 66;
st[2].name = "alice";
st[2].score = 77;
st[3].name = "alice";
st[3].score = 76;
std::sort(st, st+4, mycompare);
std::cout << "sort struct (decreasing):" << std::endl;
for (student s : st) {
std::cout << s.name << " " << s.score << std::endl;
}
std::cout << std::endl;
return 0;
}
```
輸出:
```cpp
alice 77
alice 76
bob 70
cindy 66
```
排序陣列的某部份
只想排列陣列前五項可以這樣做
```cpp
int arr[] = {4, 5, 8, 3, 7, 1, 2, 6, 10, 9};
std::sort(arr, arr+5);
```
輸出如下:
```cpp
3 4 5 7 8 1 2 6 10 9
```
如果是用 vector 的話，就變成這樣寫，
```cpp
std::vector<int> arr = {4, 5, 8, 3, 7, 1, 2, 6, 10, 9};
std::sort(arr.begin(), arr.begin()+5);
```
如果你想排序第3筆到第5筆數值，其他數值不動，可以這樣寫，
(排序從std::sort第一個參數開始，直到(小於)第二個參數之前)
```cpp
int arr[] = {4, 5, 8, 3, 7, 1, 2, 6, 10, 9};
std::sort(arr+2, arr+5);
```
### 題目:
zerojudge i399：（數字遊戲）
https://zerojudge.tw/ShowProblem?problemid=i399
```cpp
#include <bits/stdc++.h>
using namespace std;
int main(){
int a,b,c;
int ans=0;
cin>>a>>b>>c;
vector<int>v;
v.push_back(a);
v.push_back(b);
v.push_back(c);
if(a==b&&b==c){
ans=3;
}
else if(a==b||b==c||a==c){
ans=2;
}
else{
ans=1;
}
sort(v.begin(),v.end());
cout<<ans<<" ";
for(int i=2;i>=0;--i){
if(ans==3){
cout<<v[i];
break;
}
else if(ans==2){
if(v[i]==v[i-1]){
cout<<v[i]<<" "<<v[i-2];
break;
}
else if(v[i]!=v[i-1]){
cout<<v[i]<<" "<<v[i-1];
break;
}
}
else{
cout<<v[i]<<" ";
}
}
return 0;
}
```
zerojudgei428：（巴士站牌）
https://zerojudge.tw/ShowProblem?problemid=i428
```cpp
#include <bits/stdc++.h>
using namespace std;
int main()
{
int m;
int b=-1,s=10000;
vector<int>xx;
vector<int>yy;
cin>>m;
for(int i=0;i<m;++i){
int x,y;
cin>>x;
cin>>y;
xx.push_back(x);
yy.push_back(y);
}
for(int i=0;i<m-1;++i){
if(abs(xx[i+1]-xx[i])+abs(yy[i+1]-yy[i])>b){
b=abs(xx[i+1]-xx[i])+abs(yy[i+1]-yy[i]);
}
if(abs(xx[i+1]-xx[i])+abs(yy[i+1]-yy[i])<s){
s=abs(xx[i+1]-xx[i])+abs(yy[i+1]-yy[i]);
}
}
cout<<b<<" "<<s;
return 0;
}
```
c290-秘密差
https://zerojudge.tw/ShowProblem?problemid=c290
思維:這題是要算出偶數數字總和與基數數字總和
想法:用Ceil函式取首位數字再利用取餘數把剩餘的數取出來
但後來解了很久都解不出來
才發現題目輸入的限制位數＞1000
這是連long long interger都裝不下所以後來才知道要用字串的發想來解
可以用.length()的函數來算是幾位數
在判斷是不是二的倍數來區分偶數位相加和奇數位相加
再用ascii code *
讓位數－‘0’的動作來讓字元變數字
字串處理還要多加油！
```cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
string n;
cin>>n;
int so=0,se=0;
for(int i=0;i<n.size();++i){
if(i%2==0){
so=so+n[i]-'0';
}
else{
se=se+n[i]-'0';
}
}
cout <<abs(so-se);
return 0;
}
```
c294-三角形辨別
https://zerojudge.tw/ShowProblem?problemid=c294
```cpp
#include <iostream>
#include <vector>
using namespace std;
int main(){
int a, b, c;
cin >> a >> b >> c;
int max, mid, min;
if(a >= b){
max = a;
min = b;
}else{
max = b;
min = a;
}
if(c >= max){
mid = max;
max = c;
}else if(c < min){
mid = min;
min = c;
}else{
mid = c;
}
cout << min << " " << mid << " " << max << endl;
if(min + mid <= max){
cout << "No";
}else if(min*min + mid*mid == max*max){
cout << "Right";
}else if(min*min + mid*mid < max*max){
cout << "Obtuse";
}else{
cout << "Acute";
}
return 0;
}
```
**f312. [1. 人力分配](https://zerojudge.tw/ShowProblem?problemid=f312)**
```cpp
#include <iostream>
#include <vector>
using namespace std;
int main(){
int a1,b1,c1,a2,b2,c2,n;
int max;
cin >> a1 >> b1 >> c1 >> a2 >> b2 >> c2 >> n;
for(int x2=0; x2<=n; ++x2){
if(x2 == 0)
max = (a1+a2)*(x2*x2)+(b2-2*n*a1-b1)*x2+(a1*(n*n)+b1*n+c1+c2);
else{
int temp = (a1+a2)*(x2*x2)+(b2-2*n*a1-b1)*x2+(a1*(n*n)+b1*n+c1+c2);
if(temp >= max)
max = temp;
}
}
cout << max;
}f605. 1. 購買力
```
**f605. [1. 購買力](https://zerojudge.tw/ShowProblem?problemid=f605)**
```cpp
#include <iostream>
using namespace std;
int main(){
// f605 購買力 2021-01
int total = 0;
int total_price = 0;
int row,target;
cin >> row >> target;
for(int i = 0; i < row; ++i){
int min, max;
int a, b, c;
cin >> a >> b >> c;
if(a >= b){
max = a;
min = b;
}else{
min = a;
max = b;
}
if(c > max)
max = c;
else if(c < min)
min = c;
if(max - min >= target){
total += 1;
total_price += (a + b + c)/3;
}
}
cout << total << " " << total_price;
}
```
**h026. [202001_1 猜拳](https://zerojudge.tw/ShowProblem?problemid=h026)**
```cpp
#include <iostream>
#include <vector>
using namespace std;
int main(){
// h026 猜拳 2020-01
int F, N;
int tie = 0;
cin >> F >> N;
vector<int> v;
for(int i = 0; i < N; ++i){
int temp;
cin >> temp;
v.push_back(temp);
}
for(int i = 0; i < N; ++i){
if(v[i] != F){
if(F == 0){
if(v[i] == 2)
cout << F << " : Won at round " << i+1;
else if(v[i] == 5)
cout << F << " : Lost at round " << i+1;
break;
}else if(F == 2){
if(v[i] == 5)
cout << F << " : Won at round " << i+1;
else if(v[i] == 0)
cout << F << " : Lost at round " << i+1;
break;
}else if(F == 5){
if(v[i] == 0)
cout << F << " : Won at round " << i+1;
else if(v[i] == 2)
cout << F << " : Lost at round " << i+1;
break;
}
}else{
if(i == N - 1){
cout << F << " : Drew at round " << N;
}
else{
cout << F << " ";
tie += 1;
if(tie == 2){
if(v[i] == 0)
F = 5;
else if(v[i] == 2)
F = 0;
else if(v[i] == 5)
F = 2;
tie = 0;
}
}
}
}
}
```
**b964. [第 1 題 成績指標](https://zerojudge.tw/ShowProblem?problemid=b964)**
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n ;
bool isBest = false;
bool isWorst = false;
int best, worst;
cin >> n;
vector<int> scores;
for(int i = 0; i < n; ++i){
int temp;
cin >> temp;
scores.push_back(temp);
}
sort(scores.begin(), scores.end());
for(int i = 0; i < n; ++i){
if(i != n-1)
cout << scores[i] << " ";
else
cout << scores[i];
}
cout << "\n" ;
if(scores[n-1] < 60){
isWorst = true;
best = scores[n-1];
}else if(scores[0] >= 60){
isBest = true;
worst = scores[0];
}else{
for(int i = 0; i < n; ++i){
if(scores[i] >= 60 && i > 0){
worst = scores[i];
best = scores[i-1];
break;
}
}
}
if(isBest){
cout << "best case\n";
cout << worst;
}else if(isWorst){
cout << best << "\n";
cout << "worst case";
}else{
cout << best << "\n";
cout << worst << "\n";
}
return 0;
}
```
# 二維矩陣
前置複習
```cpp
vector<int> ivec(10);// 宣告1個vector，裡面有10個int空間。
vector<int> ivec[10];// 宣告10個vector，每一個都可以存int。
```
二維陣列
```cpp
#include<bits/stdc++.h>
using namespace std;
int main() {
// Init
vector<vector<int>> matrix {
{1, 1, 1, 1},
{2, 2, 2, 2},
{3, 3, 3, 3}
};
// Print
for(int i=0;i<3;++i){
for(int j=0;j<4;++j){
cout<<val<<" ";
}
cout<<endl;
}
return 0;
}
非vector宣告方式
```cpp
#include<bits/stdc++.h>
using namespace std;
int main(){
int a[100][100];//宣告二維矩陣a有100*100的空間
for(int i=0;i<100;++i){
for(int j=0;j<100;++j){
cin>>a[i][j]//利用巢狀迴輸入二維矩陣
}
}
for(int i=0;i<100;++i){
for(int j=0;j<100;++j){
cout>>a[i][j];//利用巢狀迴輸出二維矩陣
}
}
}
```
### 題目：
zerojudgeb965：（矩陣轉換）
重點:
1. a[10][10]設全域變數讓函式去改他
2. 轉換與翻轉的演算法(本題最關鍵)
3. 旋轉的話讓他轉前要讓r c互換
4. 旋轉的函式讀取可以<10,<10
5. 他是給你旋轉後的你要用倒著轉來還原
6. 因為不知道r c確切數值，輸出可以用if( j == C - 1)來判斷是否換行
```cpp
#include <bits/stdc++.h>
using namespace std;
void showVector2d(vector<vector<int>> &vt){
for(int i = 0 ; i < vt.size(); ++i){
for(int j = 0; j < vt[0].size(); ++j){
cout << vt[i][j] << " ";
}
cout << "\n";
}
}
void flip(vector<vector<int>> &vt){
int r = vt.size();
int c = vt[0].size();
vector<vector<int>> res(r, vector<int>(c, 0));
for(int i = 0; i < r; ++i){
for(int j = 0; j < c; ++j){
res[r-1-i][j] = vt[i][j];
}
}
vt = res;
}
void rotate(vector<vector<int>> &vt){
int r = vt.size();
int c = vt[0].size();
int new_r = c;
int new_c = r;
vector<vector<int>> res(new_r, vector<int>(new_c, 0));
for(int i = 0; i < r; ++i){
for(int j = 0; j < c; ++j){
res[c-1-j][i]= vt[i][j];
}
}
vt = res;
}
int main()
{
int R, C, M;
while(cin >> R >> C >> M){
vector<vector<int>> ans;
vector<int> vM;
for(int i = 0; i < R; ++i){
vector<int> vtemp;
for(int j = 0; j < C; ++j){
int temp;
cin >> temp;
vtemp.push_back(temp);
}
ans.push_back(vtemp);
}
for(int i = 0; i < M; ++i){
int temp;
cin >> temp;
vM.push_back(temp);
}
for(int i = vM.size()-1; i > -1; --i){
if(vM[i] == 0){
rotate(ans);
}else if(vM[i] == 1){
flip(ans);
}
}
int ans_r = ans.size();
int ans_c = ans[0].size();
cout << ans_r << " " << ans_c <<endl;
for(int i = 0; i < ans_r; ++i){
for(int j = 0; j < ans_c ; ++j){
if(j == ans_c -1){
cout << ans[i][j];
}else{
cout << ans[i][j] << " ";
}
}
cout << "\n";
}
}
return 0;
}
```
zerojudgeh027：（矩陣總和）
```cpp
#include<bits/stdc++.h>
using namespace std;
int main() {
int s,t,n,m,r;
int su=0,ans1=0,totle=0,totle2=0,sm=9999;
cin>>s>>t>>n>>m>>r;
int a[100][100];
int b[100][100];
for(int i=0;i<s;++i){
for(int j=0;j<t;++j){
cin>>a[i][j];
totle=totle+a[i][j];
}
}
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
cin>>b[i][j];
}
}
for(int i=0;i<n-s+1;++i){
for(int j=0;j<m-t+1;++j){
for(int k=0;k<s;++k){
for(int l=0;l<t;++l){
if(b[k+i][l+j]!=a[k][l]){
su++;
}
totle2=totle2+b[k+i][l+j];
}
}
if(su<=r){
ans1++;
if(abs(totle2-totle)<=sm){
sm=abs(totle2-totle);
}
}
totle2=0;
su=0;
}
}
if(sm==9999){
cout<<ans1<<endl<<"-1";
}
else{
cout<<ans1<<endl<<sm;
}
return 0;
}
```
# 冒泡排序法(Bubble sort)
氣泡排序（Bubble Sort）
氣泡排序是一種簡單的排序演算法，它的原理是依序比較相鄰的兩個元素，如果前一個元素大於後一個元素，就交換它們的位置，重複進行直到排序完成。因為排序過程中較大的元素像氣泡一樣慢慢浮到數列的右端，所以叫氣泡排序。
實作步驟
定義一個氣泡排序函數，傳入參數分別為 待排序的數列 arr[] 和 數列長度 n。
使用兩層循環進行排序，外層循環表示排序的輪數，內層循環表示每輪比較的次數。
如果前一個元素大於後一個元素，則使用 swap() 交換它們的位置。
在主函數中宣告一個待排序的數列，並計算數列。
### 實例:
```cpp
#include<bits/stdc++.h>
using namespace std;
void bubblesort(vector<int> &vt){
for(int i=0;i<vt.size()-1;++i){
for(int j=0;j<vt.size()-1;++j){
if(vt[j]>vt[j+1]){
int temp;
v[j]=temp;
v[j+i]=temp;
}
}
for(int k=0;k<vt.size();++k){
cout<<vt[k]<<" "<<endl;
}
}
}
int main(){
vector<int>vt[1,2,3,2,1];
bubblesort(vt);
}
```
### 題目:zerojudge ****i399. 1. 數字遊戲****
https://zerojudge.tw/ShowProblem?problemid=i399
```cpp
#include <iostream>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int a, b, c;
cin >> a >> b >> c;
// Bubble sort
if (a < b) swap(a, b);
if (b < c) swap(b, c);
if (a < b) swap(a, b);
if (a == b && b == c)
cout << 3 << ' ' << a << endl;
else if (a == b || b == c)
cout << 2 << ' ' << a << ' ' << c << endl;
else
cout << 1 << ' ' << a << ' ' << b << ' ' << c << endl;
return 0;
}
```
# 二分搜(Binary Search)
二分搜尋法（Binary Search）是一種常用的搜尋演算法，主要用於在已排序的陣列或清單中快速尋找目標元素。它的工作原理是將目標值與陣列的中間元素進行比較，如果相等，則找到了目標元素；如果目標值小於中間元素，則在陣列的前半部分繼續搜尋；如果目標值大於中間元素，則在陣列的後半部分繼續搜尋。通過逐步將搜尋範圍縮小一半，最終可以找到目標元素或確定目標元素不存在於陣列中。
### 步驟:
1. 初始化左邊界 **`left`** 為陣列的起始索引，右邊界 **`right`** 為陣列的結束索引。
2. 當 **`left`** 小於等於 **`right`** 時，執行以下步驟：
a. 計算中間元素的索引 **`mid`**，可以使用 **`mid = (left + right) // 2`**。
b. 比較目標值與中間元素：
- 如果目標值等於中間元素，表示找到了目標元素，返回中間元素的索引。
- 如果目標值小於中間元素，說明目標元素在陣列的前半部分，更新右邊界 **`right = mid - 1`**。
- 如果目標值大於中間元素，說明目標元素在陣列的後半部分，更新左邊界 **`left = mid + 1`**。
3. 如果迴圈結束仍未找到目標元素，表示目標元素不存在於陣列中，返回一個特定的值（如 -1）。
### 基本模板:
```cpp
while (le <= ri) { // 區間 [le, ri]
mid = le + (ri-le)/2; // (le + ri)/2 避免overflow的寫法
if (a[mid] == key) return mid;
else if (a[mid] < key) le = mid+1;
else ri = mid – 1;
}
```
### 與二分搜類似的技巧:雙指針
### 題目:**344. Reverse String**
https://leetcode.com/problems/reverse-string/
```cpp
class Solution {
public:
void reverseString(vector<char>& s) {
int l=0,r=s.size()-1;
while(l<=r){
char temp=s[l];
s[l]=s[r];
s[r]=temp;
++l;
--r;
}
}
};
```
### Leetcode 557
https://leetcode.com/problems/reverse-words-in-a-string-iii/
```cpp
class Solution {
public:
string reverseWords(string s) {
int l=0,r=0;
while(l<s.size()){
}
}
};
```
# 樹(tree)
## Pass by Value
```cpp
void swap(int a, int b) {
int tmp = a;
a = b;
b = tmp;
}
```
# struct(結構)
甚麼是struct?
把很多變數包在一起
宣告結構把它當作一個型態
結構中所包含的變數稱為屬性
```cpp
struct Person { //定義一個叫person的struct
char name[100];
int age;
float height;
//其中有name age height 作為屬性
};
Person student; //宣告型別為Person的變數student
studenPass by Value / Referencet.age =18;
cout<<student.age <<endl;//取用student 的屬性age
```
<aside>
💡 在Person這個大結構中包含了name age height 等變數
</aside>
### 範例:
```cpp
#include <iostream>
using namespace std;
struct Circle {
int x;
int y;
int r;
Circle(int a, int b, int c) {
x = a;
y = b;
r = c;
}
};
int main() {
Circle cl(3, 5, 2);
Circle* pcl = new Circle(3, 5, 2);
Circle* pc2 = new Circle(-2, -3, 5);
cout << "First Circle point: (" << cl.x << ", " << cl.y << ") radius: " << cl.r << endl;
cout << "First Circle point: (" << pcl->x << ", " << pcl->y << ") radius: " << pcl->r << endl;
cout << "Second Circle point: (" << pc2->x << ", " << pc2->y << ") radius: " << pc2->r << endl;
delete pcl;
delete pc2;
return 0;
}
```
# ****class****
與struct主要不同之處→有限制存取(誰可以使用)
public ->內外子
private ->內
protected ->內子
沒寫 ->默認private
### 結構簡介
```cpp
class Shop{
int pos_x;
int pos_y;
bool type;
int nrtTncome;
//變數成員
void say_hi(){
cout<<"hi"<<endl;
}
bool get_type(){
return type;
}
//成員函式
};
```
可否把member function 放外面?->要加前綴→(name)::
### 範例:
```cpp
#include <iostream>
using namespace std;
class Circle {
public:
int x;
int y;
int r;
Circle(int a, int b, int c) {
x = a;
y = b;
r = c;
}
};
int main() {
Circle cl(3, 5, 2);
Circle* pcl = new Circle(3, 5, 2);
Circle* pc2 = new Circle(-2, -3, 5);
cout << "First Circle point: (" << cl.x << ", " << cl.y << ") radius: " << cl.r << endl;
cout << "First Circle point: (" << pcl->x << ", " << pcl->y << ") radius: " << pcl->r << endl;
cout << "Second Circle point: (" << pc2->x << ", " << pc2->y << ") radius: " << pc2->r << endl;
delete pcl;
delete pc2;
return 0;
}
```
# BInary Tree
```cpp
#include <iostream>
using namespace std;
class TreeNode {
public:
int val;
TreeNode* leftNode;
TreeNode* rightNode;
TreeNode(int x) {
val = x;
leftNode = nullptr;
rightNode = nullptr;
}
};
int main() {
TreeNode* tree = new TreeNode(3);
tree->leftNode = new TreeNode(2);
tree->leftNode->leftNode = new TreeNode(5);
tree->leftNode->rightNode = new TreeNode(7);
tree->rightNode = new TreeNode(1);
tree->rightNode->leftNode = new TreeNode(6);
tree->rightNode->rightNode = new TreeNode(8);
// Rest of your code...
return 0;
}
```
## Traversal:
### 定義:
l 一個節點最多2個Children
l 只有一個Root
l Root到Leaf只能有一條路徑
### Pre-Order Traversal (前序)
順序:中 左 右
D L R
前序遍歷（Pre-Order Traversal）按照以下順序訪問節點：當前節點、左子樹、右子樹。具體而言，前序遍歷首先訪問根節點，然後遞歸地對左子樹進行前序遍歷，最後遞歸地對右子樹進行前序遍歷。
前序遍歷常見的應用場景：
1. 構建二元樹的拷貝：通過前序遍歷可以獲取二元樹的結構信息，可以用於構建二元樹的拷貝。
2. 表達式轉換：前序遍歷可用於將中綴表達式轉換為前綴或後綴表達式。
3. 表達式求值：前序遍歷可用於計算前綴或後綴表達式的值。
4. 樹的序列化和反序列化：通過前序遍歷可以將一棵樹序列化為字符串，或者將字符串反序列化為一棵樹。
### In-Order Traversal (中序)
順序:左 中 右
L D R
中序遍歷（In-Order Traversal）按照以下順序訪問節點：左子樹、當前節點、右子樹。
中序遍歷可能有用的場景：
1. 按排序順序檢索節點：中序遍歷可以按升序訪問二元搜索樹中的節點，因此對於按排序順序檢索節點非常有用。
2. 表達式求值：中序遍歷可用於計算算術表達式，其中操作數和運算符在二元表達式樹的節點中表示。
3. 構建表達式：中序遍歷可用於從二元表達式樹的節點構建原始表達式。
4. 查找第k小或第k大的元素：中序遍歷可用於高效地查找二元搜索樹中第k小或第k大的元素。
```cpp
#include <iostream>
#include <vector>
using namespace std;
class TreeNode {
public:
int val;
TreeNode* leftNode;
TreeNode* rightNode;
TreeNode(int x) {
val = x;
leftNode = nullptr;
rightNode = nullptr;
}
};
void inOrderTraversal(TreeNode* root, vector<int>& vt) {
if (!root) {
return;
}
inOrderTraversal(root->leftNode, vt);
vt.push_back(root->val);
inOrderTraversal(root->rightNode, vt);
}
int main() {
TreeNode* tree = new TreeNode(3);
tree->leftNode = new TreeNode(2);
tree->leftNode->leftNode = new TreeNode(5);
tree->leftNode->rightNode = new TreeNode(7);
tree->rightNode = new TreeNode(1);
tree->rightNode->leftNode = new TreeNode(6);
tree->rightNode->rightNode = new TreeNode(8);
vector<int> vt;
inOrderTraversal(tree, vt);
for(unsigned int i = 0; i < vt.size(); ++i) {
cout << vt[i] << " ";
}
delete tree;
return 0;
}
```
### Post-Order Traversal (後序)
順序:左 右 中
L R D
後序遍歷（Post-Order Traversal）按照以下順序訪問節點：左子樹、右子樹、當前節點。具體而言，後序遍歷先遞歸地對左子樹進行後序遍歷，然後遞歸地對右子樹進行後序遍歷，最後訪問當前節點。
後序遍歷常見的應用場景：
1. 釋放二元樹的內存：通過後序遍歷，可以先釋放左子樹和右子樹的內存，再釋放當前節點的內存，用於有效地釋放二元樹的內存。
2. 表達式求值：後序遍歷可用於計算後綴表達式的值。
3. 表達式轉換：後序遍歷可用於將中綴表達式轉換為後綴表達式。
4. 構建二元樹的拷貝：通過後序遍歷可以獲取二元樹的結構信息，可以用於構建二元樹的拷貝。
### 題目:
Leetcode 94. Binary Tree Inorder Traversal
https://leetcode.com/problems/binary-tree-inorder-traversal/
```cpp
class Solution {
public:
void inorder(TreeNode* root,vector<int> &vt) {
if(!root) return;
inorder(root->left, vt);
vt.push_back(root->val);
inorder(root->right,vt);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
inorder(root,ans);
return ans;
}
};
```
Leetcode 144. Binary Tree Preorder Travers
https://leetcode.com/problems/binary-tree-preorder-traversal/
```cpp
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int>preorder;
stack<TreeNode*>st;
if(root == NULL){return preorder; }
st.push(root);
while(!st.empty()){
TreeNode* top = st.top();
st.pop();
preorder.push_back(top->val);
if(top->right!= NULL){
st.push(top->right);
}
if(top->left!= NULL){
st.push(top->left);
}
}
return preorder;
}
};
```
Leetcode 145. Binary Tree Postorder Traversal
https://leetcode.com/problems/binary-tree-postorder-traversal/
```cpp
class Solution {
public:
vector<int>res;
vector<int> postorderTraversal(TreeNode* root) {
if(root != NULL)
{
postorderTraversal(root->left);
postorderTraversal(root->right);
res.push_back(root->val);
}
return res;
}
};
```
Leetcode 100. Same Tree
https://leetcode.com/problems/same-tree/
```cpp
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if(p == NULL || q == NULL) return p == q;
return
(p->val == q->val) &&
isSameTree(p->left, q->left) &&
isSameTree(p->right, q->right);
}
};
```
101. Symmetric Tree
https://leetcode.com/problems/symmetric-tree/description/
```cpp
class Solution {
public:
bool isEqual(TreeNode* left, TreeNode* right) {
if (!left && !right)
return true;
if (!left || !right || left->val != right->val)
return false;
return isEqual(left->left, right->right) && isEqual(left->right, right->left);
}
bool isSymmetric(TreeNode* root) {
return isEqual(root->left, root->right);
}
};
```
104：Maximum Depth of Binary23https://leetcode.com/problems/maximum-depth-of-binary-tree/description/
```cpp
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == nullptr)
return 0;
int leftHeight = maxDepth(root -> left);
int rightHeight = maxDepth(root -> right);
return max(leftHeight, rightHeight) + 1;
}
};
```
# Queue**佇列**
**#include <queue>**
跟排隊一樣
先到的先出隊伍
FIFO (First In First Out)52x
### 指令介紹:
```cpp
queue<T> q; // 宣告一個存T的queue
q.push(x); // 把x放進queue
q.front(); // 回傳queue最前方的元素
q.pop(); // 移除queue最前方的元素
q.size(); // 回傳queue中有幾個元素
q.empty(); // 回傳queue是不是空的
```
### 範例:
```cpp
queue<int> q;
for(int i = 1 ; i <= 5; i++)
q.push(i); // 1 2 3 4 5
cout << q.front(); // 1
q.pop(); // 2 3 4 5
q.pop(); // 3 4 5
cout << q.front(); // 3
cout << q.size(); // 3
cout << q.empty(); // 0 (false)
```
# Graph(BFS)
## Graph = Nodes + Edges
## BFS (Bread-First Search):
C++ 中的 BFS（Breadth-First Search，廣度優先搜尋）是一種用於圖形或樹狀結構的搜尋演算法。BFS 以廣度優先的方式逐層擴展搜索，從起始節點開始，先訪問與起始節點直接相鄰的節點，然後再逐層訪問更遠的節點。
BFS 的特點是，它從起始節點開始逐層擴展，確保先訪問較近的節點，然後再訪問較遠的節點。這使得 BFS 可以用於許多應用，例如尋找最短路徑、連通性檢查、圖形遍歷等。
- 【用途】在樹(tree)或圖(graph)上找出從特定起點出發，抵達指定終點的最短距離(shortest path)。
- 【觀念】利用 queue 資料先進先出的特性來確保「先被搜尋到的頂點，會先成為下一個搜尋起點」。
- 【實作】以 queue 方式實現。
### BFS 演算法的基本步驟：
1. 建立一個佇列（queue）和一個標記（visited）陣列或向量來追蹤已訪問的節點。
2. 將起始節點放入佇列中，並將其標記為已訪問。
3. 進入迴圈，直到佇列為空。在每個迭代中，從佇列中取出一個節點。
4. 訪問該節點，並將與之相鄰且尚未訪問過的節點放入佇列中，同時將其標記為已訪問。
5. 重複步驟 3-4，直到佇列為空，表示已經完成了所有可能的訪問。
```cpp
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
vector<int> adj[8];
vector<bool> visit(8, false);
adjList.push_back(4);
adjList.push_back(6);
adjList.push_back(0);
adjList.push_back(1);
adjList.push_back(2);
adjList.push_back(6);
queue<int> q;
q.push(3);
visit[3] = true;
while (!q.empty()) {
int cur = q.front();
cout << cur << " ";
for (int i =0;i<adj[cur].size();++i) {
if (!visit[i]) {
visit[i] = true;
q.push(i);
}
}
q.pop();
}
cout << endl;
return 0;
}
```
## 題目:
### ****d767. 血緣關係****
https://zerojudge.tw/ShowProblem?problemid=d767
```cpp
#include<bits/stdc++.h>
using namespace std;
int main(){
int num;
cin>>num;
vector<int> adj[num];
vector<int> parent;
int root;
for(int i=0;i<num;++i){
parent.push_back(-1);
}
for(int i=0;i<num-1;++i){
int a,b;
cin>>a>>b;
adj[a].push_back(b);
parent[b]=a;
}
for(int i=0;i<num;++i){
if(parent[i]==-1){
root=i;
}
}
queue<int> q;
q.push(root);
while(!q.empty()){
int cur =q.front();
cout<<cur<<" ";
for(int i=0;i<adj[cur].size();++i){
q.push(adj[cur][i]);
}
q.pop();
}
}
```
### 103：Binary Tree Zigzag Level Order Traversal
https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
```cpp
class Solution {
public:
int level=0;
queue<TreeNode*>tobetraversed;
void Traverse(vector<vector<int>>&ans)
{
int thisiteration=tobetraversed.size();
vector<int>values;
while(thisiteration--)
{
if(tobetraversed.front()==NULL)
{
tobetraversed.pop();
continue;
}
if(tobetraversed.front()->left!=NULL)
{
tobetraversed.push(tobetraversed.front()->left);
}
if(tobetraversed.front()->right!=NULL)
{
tobetraversed.push(tobetraversed.front()->right);
}
values.push_back(tobetraversed.front()->val);
tobetraversed.pop();
}
if(level%2==1)
{
reverse(values.begin(),values.end());
}
level++;
ans.push_back(values);
if(tobetraversed.size()!=0)
{
Traverse(ans);
}
return;
}
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>>ans;
if(root==NULL)
{
return ans;
}
tobetraversed.push(root);
Traverse(ans);
return ans;
}
};
```
**102. Binary Tree Level Order Traversal**
https://leetcode.com/problems/binary-tree-level-order-traversal/
```cpp
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> q;
vector<vector<int>>v;
if(!root)
return {};
q.push(root);
while(!q.empty()){
vector<int>a;
int size=q.size();
while(size--){
TreeNode* curr=q.front();
q.pop();
a.push_back(curr->val);
if(curr->left)
q.push(curr->left);
if(curr->right)
q.push(curr->right);
}
v.push_back(a);
}
return v;
}
};
```
Leecode 111：Minimum Depth of Binary
https://leetcode.com/problems/minimum-depth-of-binary-tree/description/
```cpp
class Solution {
public:
int minDepth(TreeNode* root) {
if(root == NULL){
return 0;
}
if(root->left == NULL && root->right == NULL){
return 1;
}
else if( root->left != NULL && root->right == NULL){
return minDepth(root->left) + 1;
}
else if( root->left == NULL && root->right != NULL ){
return minDepth(root->right) + 1;
}
else{
return min(minDepth(root->left),minDepth(root->right)) + 1;
}
}
}
```
515. Find Largest Value in Each Tree Row
https://leetcode.com/problems/find-largest-value-in-each-tree-row/description/
```cpp
class Solution {
public:
vector<int> largestValues(TreeNode* root) {
if(!root) return {};
vector<int> ans;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()) {
int n = q.size();
int mx = INT_MIN;
while(n--) {
TreeNode* temp = q.front(); q.pop();
mx = max(mx, temp -> val);
if(temp -> left) q.push(temp -> left);
if(temp -> right) q.push(temp -> right);
}
ans.push_back(mx);
}
return ans;
}
};
```
Leecode **589. N-ary Tree Preorder Traversal**
https://leetcode.com/problems/n-ary-tree-preorder-traversal/description/
```cpp
class Solution {
public:
vector<int> preorder(Node* root) {
if(!root){return {};}
vector<int>ans;
stack<Node*>s;
s.push(root);
while(!s.empty()){
root=s.top();
s.pop();
ans.push_back(root->val);
for(int i=root->children.size()-1; i>=0; i--){
if(root->children[i]){s.push(root->children[i]);}
}
}
return ans;
}
};
```
Graph(DFS)
## Graph = Nodes + Edges
## DFS(Depth-First Search):
C++ 中的 DFS（Depth-First Search，深度優先搜尋）是一種用於圖形或樹狀結構的搜尋演算法。DFS 以深度優先的方式進行遍歷，從起始節點開始，一直沿著某一個分支遞歸地遍歷，直到達到最深的節點，然後回溯到上一層，繼續遍歷其他分支。
DFS 的特點是，它沿著某一個分支一直遞歸到最深的節點，然後再回溯到上一層。這使得 DFS 可以用於許多應用，例如尋找特定節點、圖形連通性檢查、拓撲排序等。
- 【用途】用來遍歷樹(tree)或圖(graph)的演算法。
- 【觀念】由圖的某一點開始搜尋，先探尋鄰接邊(edge)上未搜尋的一點，並儘可能往深處搜索，直到最後，再回溯(backtracking)到前一個節點，持續拜訪未搜尋的節點，直到到達目標節點或已經遍歷所有節點。
- 【實作】以遞迴(recursion)方式實現。
-
### DFS 演算法的基本步驟：
1. 建立一個標記（visited）陣列或向量來追蹤已訪問的節點。
2. 從起始節點開始，訪問該節點並將其標記為已訪問。
3. 遞迴地對該節點的鄰接節點進行 DFS 遍歷，對每個尚未訪問過的鄰接節點重複此步驟。
4. 重複步驟 2-3，直到遍歷完所有可能的節點。
### 題目:
Leecode 111：Minimum Depth of Binary
https://leetcode.com/problems/minimum-depth-of-binary-tree/description/
```cpp
int minDepth(TreeNode* root) {
if (!root)
return 0;
if (root->left && root->right)
return min(minDepth(root->left), minDepth(root->right))+1;
return max(minDepth(root->left), minDepth(root->right))+1;
}
```
515. Find Largest Value in Each Tree Row
https://leetcode.com/problems/find-largest-value-in-each-tree-row/description/
```cpp
class Solution {
public:
void dfs(TreeNode* root, int level, vector<int> &ans) {
if(!root) return;
if(level == ans.size()) ans.push_back(root -> val);
ans[level] = max(ans[level], root -> val);
dfs(root -> left, level + 1, ans);
dfs(root -> right, level + 1, ans);
}
vector<int> largestValues(TreeNode* root) {
vector<int> ans;
dfs(root, 0, ans);
return ans;
}
};
```
Leecode **589. N-ary Tree Preorder Traversal**
https://leetcode.com/problems/n-ary-tree-preorder-traversal/description/
```cpp
class Solution {
public:
void chk(Node* root, vector<int>&ans){
if(!root){return;}
ans.push_back(root->val);
for(auto it: root->children){
chk(it, ans);
}
}
vector<int> preorder(Node* root) {
vector<int>ans;
chk(root, ans);
return ans;
}
};
```
# 字串處理
## s.substr(i, len)
從第 i 個位置開始數len個
return type : string
string s1 = “123456789”;
string s2 = s1.substr(3, 5); // s2會變成 “45678”
****i400. 2. 字串解碼****
https://zerojudge.tw/ShowProblem?problemid=i400
(40%)
```cpp
#include<bits/stdc++.h>
using namespace std;
int main(){
char a[100][100]={};
int n,m;
cin>>n>>m;
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
cin>>a[i][j];
}
}
string s;
string t="";
cin>>s;
int c=0;
for(int i=m-1;i>=0;--i){
if(a[0][i]=='1'){
t+=s[i];
c++;
}
else if(a[0][i]=='0'){
t=s[i]+t;
}
}
if(c%2==1){
if(m%2==1){
string left =t.substr(0,m/2);
string right=t.substr(m/2+1,m/2);
s= right+t[m/2]+left;
}
else{
string left =t.substr(0,m/2);
string right=t.substr(m/2,m/2);
s= right+left;
}
}
cout<<s;
}
```
(100%)
```cpp
#include<bits/stdc++.h>
using namespace std;
int main(){
char a[100][100]={};
int n,m;
cin>>n>>m;
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
cin>>a[i][j];
}
}
string s;
string t="";
cin>>s;
for(int j=n-1;j>=0;--j){
int c=0;
for(int i=m-1;i>=0;--i){
if(a[j][i]=='1'){
t+=s[i];
c++;
}
else if(a[j][i]=='0'){
t=s[i]+t;
}
}
if(c%2==1){
if(m%2==1){
string left =t.substr(0,m/2);
string right=t.substr(m/2+1,m/2);
t= right+t[m/2]+left;
}
else{
string left =t.substr(0,m/2);
string right=t.substr(m/2,m/2);
t= right+left;
}
}
s=t;
t="";
}
cout<<s;
}
```
****j606. 2. 造字程式****
https://zerojudge.tw/ShowProblem?problemid=j606
```cpp
#include <bits/stdc++.h>
using namespace std;
int main()
{
int K, Q, R;
cin >> K >> Q >> R;
vector<vector<int>> vt(Q, vector<int>(K, 0));
vector<vector<char>> ans(Q+1, vector<char>(K, 0));
for(int i = 0; i < K; ++i){
cin >> ans[0][i];
}
for(int i = 0; i < Q; ++i){
for(int j = 0; j < K; ++j){
cin >> vt[i][j];
}
}
for(int i = 0; i < Q; ++i){
for(int j = 0; j < K; ++j){
ans[i+1][vt[i][j]-1] = ans[i][j];
}
}
for(int j = 0; j < R; ++j){
for(int i = 1; i < Q+1; ++i){
cout << ans[i][j];
}
cout << "\n";
}
return 0;
}
```
# Greedy
``` =c++
#include <bits/stdc++.h>
using namespace std;
bool coo(pair<int, int> m1, pair<int, int> m2) {
return m1.second > m2.second;
}
int main() {
while (true) {
int n;
cin >> n;
if (n == 0) {
break; // 當 n = 0 時結束迴圈
}
vector<pair<int, int>> v(n);
for (int i = 0; i < n; ++i) {
int cookTime, eatTime;
cin >> cookTime >> eatTime;
v[i] = make_pair(cookTime, eatTime);
}
sort(v.begin(), v.end(), coo);
int totalTime = 0;
int last = 0;
for (int i = 0; i < n; ++i) {
totalTime += v[i].first;
last = max(last, totalTime + v[i].second);
}
cout << last << endl;
}
return 0;
}
```
# 貪心(greedy)
## 貪心是甚麼?
貪心演算法的基礎是指凡事都先選擇最佳路徑，而每次都選擇最佳解最後的結果也剛好是最佳解。
### 簡單例子:
今天，你走進一間便利商店，你總共買了總價錢為新台幣 456 元的商品，不過你手邊剛
好沒有足夠的零錢，只有一張 1000 元紙鈔。請問店員最少要拿多少鈔票與硬幣才能完成找錢?
```cpp
我們先計算出要找的錢為 1000 − 456 = 544 元
接著，應該會直接拿取 1 張 500、4 個 10 元、以及 4 個 1 元
所以只要拿 8 個就好，而這也是最小的答案
```
```cpp
#include<bits/stdc++.h>
using namespace std;
int main(){
int a;
cin>>a;
int n=0;
n=1000-a;
int d500=0;
int d100=0;
int d50=0;
int d10=0;
int d5=0;
int d1=0;
while(n>0){
d500=n/500;
n=n%500;
d100=n/100;
n=n%100;
d50=n/50;
n=n%50;
d10=n/10;
n=n%10;
d5=n/5;
n=n%5;
d1=n/1;
n=n%1;
}
int ans=d500+d100;
int ans2=d50+d10+d5+d1;
cout<<ans<<" "<<ans2;
}
```
- 結論
- 在剛剛那個題目中，我們做了什麼?
我們很直覺的認為，只要一路選擇最大面額，就可以選到最少的零錢了!
事實上，上面在做的事情其實就是貪心演算法!
我們照著這樣子的策略，每次都拿可以拿的最大面額，最終得到最小的答案
這個就被我們稱為「貪心」
### 每次都會是最好的嗎?
假設今天某國其
硬幣面額為1 7 9
今天要湊出15元可
一貪心法從大往小找的邏輯可能會是9 1*6
單真正最少的硬幣配對方式卻會是7*2 1
- 貪心真的是對的嗎?
從上面那個例子，我們可以知道，靠著直覺走，貪心的做法並不會每次皆是正確的
那我們又為什麼需要使用這樣子的方式呢?
貪心演算法雖然不見得是正確的，但通常比起一般的作法來得更有效率
在本堂課的最後，會教大家一些證明演算法正確性的方式
### 貪心的步驟
1. 觀察
- 觀察題目的情境，看看有什麼是我們策略是我們可以照著做的，並試著猜測看看
此步驟通常是最關鍵的一步，在簡單的題目中，貪心策略通常滿直覺的
找找看有沒有排序 queue set 等
找找看有沒有特殊關係(倍數)(大到小)(交換)
2. 嘗試
觀察完題目後，得到了我們猜測的策略。我們可以試著想想各種不同的情況或測 資，試著去尋找是否有能使該策略產生錯誤答案的可能性
試試random case 手生case edge case
3. 驗證
- 實際的使用數學證明，嚴謹的去證明該算法的正確性
此步驟十分重要，但是在比賽中，許多人會省略這個步驟，直接 Proof By AC
不過建議大家，即使在比賽中猜測出了正確做法，還是可以自己練習證明看看
## 例題:
活動安排問題 https://cses.fi/problemset/task/1629
最經典的貪心法題目:
題目給你一些電影播放時段長度並要你找出在時間內不重複的最多電影數量
```cpp
#include<bits/stdc++.h>
using namespace std;
bool compareMovies(pair<int, int> movie1, pair<int, int> movie2) {
return movie1.second < movie2.second;
}
int main() {
int n;
cin >> n;
vector<pair<int, int>> movies(n);
for (int i = 0; i < n; i++) {
int start, end;
cin >> start >> end;
movies[i] = (start, end);
}
sort(movies.begin(), movies.end(), compareMovies);
int count = 0;
int lastEndTime = -1;
for (int i = 0; i < n; i++) {
if (movies[i].first >= lastEndTime) {
count++;
lastEndTime = movies[i].second;
}
}
cout << count << endl;
return 0;
}
```
資料:
5 貪心法 (Greedy)
「面對一個問題,不斷地使用同一個策略做事。」
貪心法可以很單純,也可以很懸,這裡提到所謂的「策略」也有可能會是很不直觀的做
法。
常常某些題目會讓人很直覺的想使用貪心的策略,等到中途才發現自己完全走錯了路,所
以通常我們在寫貪心的時候,會特別去注意這個做法是否是對的,可惜的是這是需要花時
間練習的。
5.1 證明貪心的思路
如果你提出了一個貪心做法,卻又很不確定他是不是對的,你可以朝以下幾個方向去思
考:
1. 試圖構造出反例,發現他不存在。
2. 如果存在更佳解的答案比你做出來的還好,那這組解一定可以再做得更好,進而達到
反證出更佳解不存在。
3. 使用遞迴證法:1. 證明基底是對的。2. 假設小問題是好的。3. 你一定可以用最好的方
法來將問題簡化成剛才假設是好的小問題。
4. 好麻煩喔,感覺寫起來也不慢就寫完丟上去看會不會錯吧。
剛開始看可能都會滿頭霧水不知道怎麼證明,所以可能都會用第四種做法 (?),多練習題
目,漸漸就會了解這些東西了。
5.2 一些嘗試貪心的例子
5. (0/1 背包問題) 每次拿將 CP 值(價值除以重量)最高的物品塞進包包。
6. (給你 n 個線段。請問最多能取出幾個線段,內部互不重疊。) 將線段依右端點排序,
從最左邊的線段開始取。如果有重疊就不取,沒有重疊就取。
7. (給你一個面額,請你用最少的零錢湊出之) 如果錢幣面額滿足任意兩個面額都恰有一
方整除另一方,則每次都選盡量大的面額扣掉再重複執行下去。
8. (給你一個面額,請你用最少的零錢湊出之) 如果錢幣面額沒有限制,則每次都選盡量
大的面額扣掉再重複執行下去。
這四個例子最後的結果是 XOOX,讀者可以自己嘗試驗證看看。
IX
板中資培-2 基礎演算法 1
5.3 題外話-- Weighted Matroid
這東西似乎不是很實用,但他是一個貪心法相關的模塊。大致上就是在說,如果你有辦法
把一個問題歸約到他身上,就一定存在一個固定且有效的貪心法可以得出最佳解。
有興趣的話可以自己上網搜尋,不過中文好像沒什麼資源就是。
5.4 習題
1. (TIOJ 1072) 有 N 個人各點了一道菜,每道菜各有需要的烹煮時間跟吃完時間,每個
時間只能同時煮一道菜。訂定一個煮菜順序使得從第一道菜開始煮到最後一個人把菜
吃完所過的時間的最小值。
2. (2009 TOI 入營考 pC/ZJ b231) 有 N 本書,每本書都有所需要的印刷時間和裝訂時間。
你可以同時裝訂任意多本書,但同一時間只能印刷至多一本書。每本書需要先印完再
裝訂。請問你至少要花多久才能將所有書都印刷裝訂完畢。
3. (TIOJ 1441) 請你適當地刪除一些數字,使得整個序列呈現大小大小... 小大小大的排
列方式。
4. (ZJ d418) 給你一個大於等於 0 的整數 N,請你你找到最小的自然數 Q,使得在 Q 中
所有數字位數的乘積等於 N。
5. (TIOJ 2009) 現在總共有 n 個介於 1 到 9 的正整數,每次調整密碼鎖上的數字時,必
須一次讓其中連續的 k 個數字加上 1(9 會循環回 1)。試問最少要調整幾次,才能調整
成另一個給定的序列,又或者是無解?
6. (APCS P4/ZJ c471) 有一堆物品堆成一疊,取出一個物品使用一次的代價是他上方的
所有物品的重量和。給定物品的重量和預計取用次數,請找出一種排列使得代價和最
小。
###### tags: `C/C++程式語# 貪心(greedy)
## 貪心是甚麼?
貪心演算法的基礎是指凡事都先選擇最佳路徑，而每次都選擇最佳解最後的結果也剛好是最佳解。
### 簡單例子:
今天，你走進一間便利商店，你總共買了總價錢為新台幣 456 元的商品，不過你手邊剛
好沒有足夠的零錢，只有一張 1000 元紙鈔。請問店員最少要拿多少鈔票與硬幣才能完成找錢?
```cpp
我們先計算出要找的錢為 1000 − 456 = 544 元
接著，應該會直接拿取 1 張 500、4 個 10 元、以及 4 個 1 元
所以只要拿 8 個就好，而這也是最小的答案
```
```cpp
#include<bits/stdc++.h>
using namespace std;
int main(){
int a;
cin>>a;
int n=0;
n=1000-a;
int d500=0;
int d100=0;
int d50=0;
int d10=0;
int d5=0;
int d1=0;
while(n>0){
d500=n/500;
n=n%500;
d100=n/100;
n=n%100;
d50=n/50;
n=n%50;
d10=n/10;
n=n%10;
d5=n/5;
n=n%5;
d1=n/1;
n=n%1;
}
int ans=d500+d100;
int ans2=d50+d10+d5+d1;
cout<<ans<<" "<<ans2;
}
```
- 結論
- 在剛剛那個題目中，我們做了什麼?
我們很直覺的認為，只要一路選擇最大面額，就可以選到最少的零錢了!
事實上，上面在做的事情其實就是貪心演算法!
我們照著這樣子的策略，每次都拿可以拿的最大面額，最終得到最小的答案
這個就被我們稱為「貪心」
### 每次都會是最好的嗎?
假設今天某國其
硬幣面額為1 7 9
今天要湊出15元可
一貪心法從大往小找的邏輯可能會是9 1*6
單真正最少的硬幣配對方式卻會是7*2 1
- 貪心真的是對的嗎?
從上面那個例子，我們可以知道，靠著直覺走，貪心的做法並不會每次皆是正確的
那我們又為什麼需要使用這樣子的方式呢?
貪心演算法雖然不見得是正確的，但通常比起一般的作法來得更有效率
在本堂課的最後，會教大家一些證明演算法正確性的方式
### 貪心的步驟
1. 觀察
- 觀察題目的情境，看看有什麼是我們策略是我們可以照著做的，並試著猜測看看
此步驟通常是最關鍵的一步，在簡單的題目中，貪心策略通常滿直覺的
找找看有沒有排序 queue set 等
找找看有沒有特殊關係(倍數)(大到小)(交換)
2. 嘗試
觀察完題目後，得到了我們猜測的策略。我們可以試著想想各種不同的情況或測 資，試著去尋找是否有能使該策略產生錯誤答案的可能性
試試random case 手生case edge case
3. 驗證
- 實際的使用數學證明，嚴謹的去證明該算法的正確性
此步驟十分重要，但是在比賽中，許多人會省略這個步驟，直接 Proof By AC
不過建議大家，即使在比賽中猜測出了正確做法，還是可以自己練習證明看看
## 例題:
活動安排問題 https://cses.fi/problemset/task/1629
最經典的貪心法題目:
題目給你一些電影播放時段長度並要你找出在時間內不重複的最多電影數量
```cpp
#include<bits/stdc++.h>
using namespace std;
bool compareMovies(pair<int, int> movie1, pair<int, int> movie2) {
return movie1.second < movie2.second;
}
int main() {
int n;
cin >> n;
vector<pair<int, int>> movies(n);
for (int i = 0; i < n; i++) {
int start, end;
cin >> start >> end;
movies[i] = (start, end);
}
sort(movies.begin(), movies.end(), compareMovies);
int count = 0;
int lastEndTime = -1;
for (int i = 0; i < n; i++) {
if (movies[i].first >= lastEndTime) {
count++;
lastEndTime = movies[i].second;
}
}
cout << count << endl;
return 0;
}
```
資料:
5 貪心法 (Greedy)
「面對一個問題,不斷地使用同一個策略做事。」
貪心法可以很單純,也可以很懸,這裡提到所謂的「策略」也有可能會是很不直觀的做
法。
常常某些題目會讓人很直覺的想使用貪心的策略,等到中途才發現自己完全走錯了路,所
以通常我們在寫貪心的時候,會特別去注意這個做法是否是對的,可惜的是這是需要花時
間練習的。
5.1 證明貪心的思路
如果你提出了一個貪心做法,卻又很不確定他是不是對的,你可以朝以下幾個方向去思
考:
1. 試圖構造出反例,發現他不存在。
2. 如果存在更佳解的答案比你做出來的還好,那這組解一定可以再做得更好,進而達到
反證出更佳解不存在。
3. 使用遞迴證法:1. 證明基底是對的。2. 假設小問題是好的。3. 你一定可以用最好的方
法來將問題簡化成剛才假設是好的小問題。
4. 好麻煩喔,感覺寫起來也不慢就寫完丟上去看會不會錯吧。
剛開始看可能都會滿頭霧水不知道怎麼證明,所以可能都會用第四種做法 (?),多練習題
目,漸漸就會了解這些東西了。
5.2 一些嘗試貪心的例子
5. (0/1 背包問題) 每次拿將 CP 值(價值除以重量)最高的物品塞進包包。
6. (給你 n 個線段。請問最多能取出幾個線段,內部互不重疊。) 將線段依右端點排序,
從最左邊的線段開始取。如果有重疊就不取,沒有重疊就取。
7. (給你一個面額,請你用最少的零錢湊出之) 如果錢幣面額滿足任意兩個面額都恰有一
方整除另一方,則每次都選盡量大的面額扣掉再重複執行下去。
8. (給你一個面額,請你用最少的零錢湊出之) 如果錢幣面額沒有限制,則每次都選盡量
大的面額扣掉再重複執行下去。
這四個例子最後的結果是 XOOX,讀者可以自己嘗試驗證看看。
IX
板中資培-2 基礎演算法 1
5.3 題外話-- Weighted Matroid
這東西似乎不是很實用,但他是一個貪心法相關的模塊。大致上就是在說,如果你有辦法
把一個問題歸約到他身上,就一定存在一個固定且有效的貪心法可以得出最佳解。
有興趣的話可以自己上網搜尋,不過中文好像沒什麼資源就是。
5.4 習題
1. (TIOJ 1072) 有 N 個人各點了一道菜,每道菜各有需要的烹煮時間跟吃完時間,每個
時間只能同時煮一道菜。訂定一個煮菜順序使得從第一道菜開始煮到最後一個人把菜
吃完所過的時間的最小值。
2. (2009 TOI 入營考 pC/ZJ b231) 有 N 本書,每本書都有所需要的印刷時間和裝訂時間。
你可以同時裝訂任意多本書,但同一時間只能印刷至多一本書。每本書需要先印完再
裝訂。請問你至少要花多久才能將所有書都印刷裝訂完畢。
3. (TIOJ 1441) 請你適當地刪除一些數字,使得整個序列呈現大小大小... 小大小大的排
列方式。
4. (ZJ d418) 給你一個大於等於 0 的整數 N,請你你找到最小的自然數 Q,使得在 Q 中
所有數字位數的乘積等於 N。
5. (TIOJ 2009) 現在總共有 n 個介於 1 到 9 的正整數,每次調整密碼鎖上的數字時,必
須一次讓其中連續的 k 個數字加上 1(9 會循環回 1)。試問最少要調整幾次,才能調整
成另一個給定的序列,又或者是無解?
6. (APCS P4/ZJ c471) 有一堆物品堆成一疊,取出一個物品使用一次的代價是他上方的
所有物品的重量和。給定物品的重量和預計取用次數,請找出一種排列使得代價和最
小。言觀念` `基本程式概念` `競程筆記` `c++` `C++`
Sign in with Wallet
Connect another wallet