---
# System prepended metadata

title: CPE重點整理

---

### stringstream 讀字串裡的東西 :+1: 
- 用法 : 
    - 1 . 先讀字串 : `getline(cin,s)`
    - 2 . 定義一個stringstream : `stringstream ss(s)`
    - 3 . 把每一資料像cin一樣間隔空格讀出來 `ss>>a[i]`
- 例子 : 
```c++
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    
    while(cin >> n){
        cin.ignore();
        int a[10001] = {0}, i = 0;
        string s;
        getline(cin, s);    
        
        stringstream ss(s);
        
        while(ss >> a[i]){
            cout << a[i] << " ";
            i++;
        }
        cout << endl;
    }

    return 0;
}

```
### sort函式進階用法

1 . **用 `vector` 排序**
```c++
    vector<int> v = {5,2,9,1};
    sort(v.begin(), v.end());
```
2 . `compare function` 

- **核心定義** : 
```c++
//只能回傳true/false
 compare(a, b) == true --> a 在 b 前面
 compare(a, b) == false --> b 在 a 前面
```
```c++
//不能寫成 >= 或 <=
return a<=b; 
```
-  **小到大排列,大到小排列** : 
```c++ 
// 小到大
bool compare(int a, int b){
    return a>b;
}
``` 
```c++
// 大到小
bool compare(int a, int b){
     return a<b;
}
```
- **比較複雜條件** :+1: 

* 常遇到這種類型 : 
    * 先用「第一優先」排序
    * 若相同，用「第二優先」排序
    * 若還相同，用「第三優先」排序
```c++
bool compare(int a, int b){
if(第一條件不同) return 第一條件比較結果;
if(第二條件不同) return 第二條件比較結果;

return 第三條件比較結果;
}
```
```
//舉例
bool compare(int a, int b){
    int A = a % m, B = b % m;
    if(A != b) return A<B;
    
    bool OddA = a % 2 != 0;
    bool OddB = b % 2 != 0;
    
    if(OddA != OddB) return OddA;//1 0 --> 0 1
    
    if(OddA) return a>b;
    return a<b;
}
```

### vector的使用

- 定義 : 可以自動變大、變小的陣列 ， 不同於普通陣列(ex : int s[100])

#### 簡易用法
1 . **加入數字** : 
```c++
vector<int> s;

s.push_back(10);
s.push_back(20);
s.push_back(30);
```
- 陣列裡面就是 s[2] = {10, 20, 30};

2 . **看陣列長度** : 
```c++
cout<<s.size();
```

3 . **刪除最後一個**
```c++
cout<<s.pop_back();
```

4 . **清空**
```c++
s.clear();
```

##### 簡單範例
```c++
#include <bits/stdc++.h>
using namespace std;

int main()
{
    vector<int> s;   
    int n, m;

    cin >> n;            // 輸入 n 筆資料
    for(int i=0; i<n; i++){
        cin >> m;
        s.push_back(m);  // 放進 vector
    }

    for(int i=0; i<s.size(); i++){
        cout << s[i] << " ";
    }

    return 0;
}

```

#### 進階用法

1 . **vector排序(sort)**
- 升序(小->大)
```c++
sort(s.begin(), s.end());
```
或是
```c++
bool compare(int a, int b){
    reutrn a<b;
}
```
- 降序(大->小)
```c++
sort(s.begin(), s.end(), greater<int>());
```
或是
```c++
bool compare(int a, int b){
    return a>b;
}
```

2 . **找某個元素(find)** 

```c++

vector<int> s = {1, 2, 7}//找到
auto it = find(s.begin(), s.end(), 7);

if(it != s.end()){//find() 找不到東西就跑到最後 (end())，所以判斷要用 it != s.end()。
    cout << "找到" << endl;
}else{
    cout << "沒有" << endl;
}

```

3 . **刪除特定位置(erase)**
- 刪除某個值
```c++
s.erase(s.begin()+4);
```
- 刪除某一段
```c++
s.erase(s.begin()+2, s.begin()+4);
```

4 . **插入元素(insert)**
- 在第i個位置插入x
```c++
s.insert(s.begin()+2, 3);
```

5 . **二維vector(DP/地圖/棋盤)**
- 宣告二維vector
```c++
vector<vector(int)> s;
```
6 . 常見競程技巧

- 計算某數值出現次數
```c++
int sum = count(s.begin(), s.end(), 5);
```
- 反轉vector
```c++
reverse(s.begin(), s.end());
```
- 刪除重複元素
```
sort(s.begin(), s.end());
s.erase(unique(s.begin(), s.end()), s.end());
```

### pair的使用
- 定義 : 一個同時可以存兩個值的容器
- 容易搞混的地方 : pair 是基本單位，map 是用 pair 組成的容器。需要存單對值就用 pair，需要存多對查找方便就用 map。

1 . **pair基本語法**
```c++
    pair<int,int> p;  // 宣告一個 pair，裡面放兩個 int
    p.first = 10;     // 第一個值
    p.second = 20;    // 第二個值

    cout << p.first << " " << p.second << endl; // 輸出 10 20
```
2 . **pair裡面可以放不同型別**
```c++
pair<string, int> p;
p.first = "rain";
p.second = 20;

cout<<p.first<<" "<<p.second<<endl;
```
3 . **vector< pair >最常見的組合** :+1: 
- 好處 : 方便存兩個值一組的資料
    
```c++
 int main() {
    int n, score;
    cin >> n;
    vector<pair<int,int>> v;

    for(int i = 1; i <= n; i++){
        cin >> score;
        v.push_back({score, i}); // 第一個是分數，第二個是編號
    }

    // 按分數升序排序
    sort(v.begin(), v.end());

    for(int i = 0; i < v.size(); i++){
        cout << "編號 " << v[i].second << ", 分數 " << v[i].first << endl;
    }
} 
```

### 數學 GCD最大公因數/LCM最小公倍數/Primes質數 :+1: 
``` c++
//gcd
int gcd(int a, int b){
    while(b){
        int t = a%b;
        a = b;
        b = t;
    }
    return a;
}
```                                                         
```c++
//lcm
long long lcm(long long a, long long b){//12 8
    return a / gcd(a, b) * b;//
}
```
```c++
//Primes
bool isPrime(int x){
    for(int i=2; i*i<=x; i++){//17
        if(x % i == 0) return false;
    }
    return true;
}
```
* 進階 : 做質數表
```c++
bool prime[1000001] = true;
    void build_prime_table(){//true是質數 false不是質數
        prime[0] = false;
        prime[1] = false;
        
        for(int i=2; i*i<=1000000; i++){
            if(prime[i]){//5
                for(int j=i*i; j<=1000000; j+=i){//j=25
                    prime[j] = false;
                }
            }
        }
    }
```

### stack(後進先出) :+1: 
- **定義** : 是一種資料結構，先進去的最後出來，後進去的先出來( ex : 疊盤子)
    - `push(x)` : 放入一個資料
    - `pop()` : 移除頂端資料(最後一筆資料)
    - `top()` : 查看頂端資料(不拿走)
    - `empty()` : 判斷是否為空
- **用法** : 爆字串
```
//aabbccdd → 刪掉相鄰相同 → 全部消失
for(char c : s){
    if(!isempty() && st.top() == c){
        st.pop();
    }else st.push(c);
}
//stack 空 → Yes / stack 有剩 → No
```
```
//top的特性
st.push(3);   // stack: 3
st.push(5);   // stack: 3, 5
st.push(7);   // stack: 3, 5, 7 (7 最上)

cout << st.top();   // 顯示 7

```

### queue(佇列) 先進先出 
* 定義 : 是一種資料結構，先進去的先進來，像是排隊一樣
    - `push(x)` : 把x加到最後
    - `pop()` : 把最前面的拿掉
    - `front()` : 看最前面的人是誰
    - `back()` : 看最後面的人是誰
    - `empty()` : 是否為空
    - `size()` : 現在有幾個

```c++
//UVA 10935 – Throwing cards away
/*一個牌堆 1, 2, 3, ..., n
規則：

丟掉最上面的牌（queue.pop）

下一張放到下面（push(front), pop）*/
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    while(cin >> n && n){
        queue<int> q;

        for(int i=1; i<=n; i++){
            q.push(i);
        }

        cout << "Discarded cards: ";

        int first = 1;

        while(q.size() > 1){
            if(first == 1){
                cout << q.front();
                first = 0;
            }else{
                cout << ", " << q.front();
            }
            q.pop();

            q.push(q.front());
            q.pop();
        }

        cout << "\nRemaining card: " << q.front() << endl;
    }
}

```

### deque(Double-Ended Queue)雙端佇列 
* 說明 : queue的加強版
    - `push_back(x)` : 從後面加入
    - `push_front(x)` : 從前面加入
    - `pop_back()` : 從前面刪除
    - `pop_front()` : 從前面刪除
    - `front()` : 看最前面元素
    - `back()` : 看後面元素
    - `size()` : 看長度
    - `empty()` : 判斷是否為空的

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

int main(){
    deque<int> q;
    
    q.push_back(10);
    q.push_front(20); // 20 10
    q.push_back(30);  // 20 10 30

    cout << q.front() << endl; // 20
    cout << q.back() << endl;  // 30

    q.pop_front(); // 10 30
    q.pop_back();  // 10

    cout << q.front() << endl; // 10
}

```
### priority_queue(優先佇列)
* 定義 : 最大堆(max heap) ， 取出的值都是最大值
    - `push(x)` : 從後面加入
    - `pop()` : 移除最大值
    - `top()` : 查看最大值
    - `empty()` : 是否是空的
    - `size()` : 看長度

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

int main(){
    priority_queue<int> pq;

    pq.push(10);
    pq.push(5);
    pq.push(30);

    cout << pq.top() << endl; // 30 最大

    pq.pop();                // 移除 30
    cout << pq.top() << endl; // 10
}

```

### DP
##### 一維dp
* 外層`i` : 遍歷每一種硬幣 
* 內層`j` : 遍歷可以組成的錢數
* 核心公式 : `dp[j] = dp[j] + dp[j-coin[i])`
```c++
//一維dp舉例
#include <bits/stdc++.h>
using namespace std;

int main() {

    int coins[5] = {1, 5, 10, 25, 50}, n;
    int dp[30001]={0};
    dp[0]=1;
    for(int i=0; i<5; i++){
        for(int j=coins[i]; j<=30001; j++){
            dp[j] += dp[j-coins[i]];
        }
    }
        
    while(cin>>n){
        if(dp[n] == 1) cout << "There is only 1 way to produce " << n << " cents change." << "\n";
        else cout<<"There are "<<dp[n]<<" ways to produce "<<n<<" cents change."<<endl;
    }
    return 0;
}
```
##### 二維dp[i][j] 
* 定義 : 用表格記錄「子問題的答案」，避免重複計算。
* ex : 
- 🎒背包問題 : 
    - 維度1 : i = 第幾個物品
    - 維度2 : j = 目前容量
- 最常共同子序列(LCS) : 
    - 維度1 : 字串A的前i個字母
    - 維度2 : 字串B的前j個字母
- 區間DP
    - 維度1 : 左端點
    - 維度2 : 右端點
* **只要問題有2種範圍/狀態就是2D dp**
* 二維dp的通用模板 : 
```c++
建立dp[][]陣列
設定初始值
for i 從 i 到 n :
    for j 從 1 到 m :
        dp[i][j] = 用 dp[i-1][?], dp[?][j-1], dp[i-1][j-1] 推出答案是dp[n][m]
```
- 背包問題範例 : (每件物品只能拿一次，容量有限，要拿出最大價值)
    - n件物品
    - 每件物品有`重量w[i]` & `價值v[i]`
    - 背包容量`w`
```c++
dp[i][j] = 前 i 件物品，容量 j 時，能得到的最大價值
```
```c++
如果第 i 件物品的重量 w[i] > j :
dp[i][j] = dp[i-1][j]

如果裝得下 (w[i] <= j)：
不拿：dp[i-1][j]
拿： dp[i-1][j - w[i]] + v[i]

---> dp[i][j] = max( 不拿 , 拿 )
```
```c++
//範例
/*
3 5
2 3
3 4
4 5 ans(7)
*/
#include<bits/stdc++.h>
using namespace std;

int main(){
    int n, W;
    cin>>n>>W;
    
    vector<int> w(n+1), v(n+1);
    
    for(int i=1; i<=n; i++) cin>>w[i]>>v[i];
    
    vector<vector<int>> dp(n+1, vector<int>(W+1, 0));
    
    for(int i=1; i<=n; i++){
        for(int j=1; j<=W; j++){
            //不能拿這件(太重)
            dp[i][j] = dp[i-1][j];
            
            //可以拿
            if(j >= w[i]){
                dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]]+v[i]);
            }
        }
    }
    cout<<dp[n][W]<<enl;
    return 0;
}
```
- LCS(Longest Common Subswquence) 最長共同子序列
- 給兩個字串 : 
    - `A`長度`n`
    - `B`長度`m`
- 找到他們的共同子序列長度(不是連續，是subsequence)
```c++
dp[i][j] = A 的前 i 個字元和 B 的前 j 個字元的 LCS 長度
```
```c++
如果 A[i] == B[i]
dp[i][j] = dp[i-1][j-1] + 1
```
```c++
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
```
```c++
/*
ABCBDAB
BDCABA
ans(4)
共同子序列之一 : BCBA or BDAB
*/
#include <bits/stdc++.h>
using namesapce std;

int main(){
    string A, B;
    cin>>A>>B;
    
    int n = A.size();
    int m = B.size();
    
    vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
    
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(A[i-1] == B[j-1]){
                dp[i][j] = dp[i-1][j-1]+1;
            }else{
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
}
```
### Binary Search
* 以生活舉例 : 自己最少需要多少錢買到一套電競設備
```yaml=
    鍵盤 1500
    滑鼠 800
    椅子 3000
    螢幕 4000
    耳機 2000
```
- 如果有10000元，夠嗎?
    - 夠，但可以少一點。
- 如果有1000元，夠嗎?
    - 不夠，可以多一點。
- 不太可能0~10000元一個個慢慢試
- 所以我會猜一半 : 
    - 猜 5000 -> 夠
    - 猜 2500 -> 不夠
    - 猜 3750 -> 不夠
    - 猜 4375 -> 不夠
    - 猜 4687 -> 夠
-  **這就是Binary Search找答案的原理**

### Greedy(貪心法)
* 核心定義 : 能塞就塞，能放就放
* 舉個例子 : 你有一台10公斤的行
```yaml=
    7kg
    2kg
    6kg
    4kg
    5kg
```
* 問題 : 「行李箱最多 10kg 時，是否能全部塞完？如果不行，需要幾個箱子？」
- 箱子1 : 
    - 放 7kg --> OK
    - 再放 2kg --> 9kg
    - 再放 6kg --> 15kg 太大裝不下 --> 停下
- 箱子2 : 
    - 放 6kg --> OK
    - 再放 4kg --> 10kg
    - 再放 5kg --> 15kg 超過 --> 停
- 箱子3 : 
    - 放5 --> OK
* **每個箱子都塞到不能再塞，這就是Greedy**

```c++
//例子
#include <bits/stdc++.h>
using namespace std;

bool ok(int limit, int s[], int n, int k){
    int cnt=1, now=0;
    
    for(int i=0; i<n+1; i++){
        if(now+s[i] > limit){
            cnt++;
            now=0;
        }
        now += s[i];
    }
    return cnt <= k+1;
}



int main(){
    int n, k;
    
    while(cin>>n>>k){
        int s[10001]={0}, Max=0, sum=0;
        for(int i=0; i<n+1; i++){ 
            cin>>s[i];
            sum += s[i];
            Max = max(Max, s[i]);//每個箱子最大的容量(不能在更小了)
        }
        int left = Max, right = sum;
        
        while(left < right){
            int mid = (left + right) / 2;
            if(ok(mid, s, n, k)) right = mid;
            else left = mid+1;
        }
        cout<<left<<endl;
    }
    return 0;
}

```

### BFS (Breadth-First Search) 廣度優先搜尋
* 定義 : 將每一層的節點由左至右依序取出
![image](https://hackmd.io/_uploads/r1Ep7n6Z-e.png)
* 用廣度優先搜尋的方式走訪的步驟為:
    * 第1層 取出10
    * 第2層 取出8, 11
    * 第3層 取出5, 9 ,15
    * 第4層 取出2, 13, 19
* 通常會用queue

### DFS (Depth-First-Search) 深度優先搜尋
* 定義 : 走到底
* PreOrder 前序 : 根節點 → 左節點 → 右節點
![image](https://hackmd.io/_uploads/HJ9AVh6-Zl.png)
* InOrder 中序 : 左節點 → 根節點 →右節點
![image](https://hackmd.io/_uploads/Sy4uS26bWx.png)
* PostOrder 後序 : 左節點 → 右節點 → 根節點
* ![image](https://hackmd.io/_uploads/r1UKU3aZbx.png)
* 差異
![image](https://hackmd.io/_uploads/SJDoI36bWx.png)

* dfs範例程式碼
```c++
void dfs(int num){
    times++;                     // 我走過一個人了！
    
    sum[num] = true;            // 這個人「整體上」已經走過了
    check[num] = true;          // 這次走訪中也走過他
    
    if (!check[sent[num]])      // 如果他的下一個還沒走到
        dfs(sent[num]);         // 就繼續往下一個走
}

```



