# 宜宸 AP325 筆記

- 第 0 章

---

### 第 0 章

(1) I/O (輸入輸出) 速度 => cin/cout 比 scanf/printf 慢很多 (TLE)

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    // code here
}

背起來，放開頭，用了之後不能使用 `scanf`, `printf`。

(2)複雜度估算 = O(執行次數) -> 念 bigO，n 代表你輸入幾個數 (資料量)

複雜度就是在估算你的「程式執行時間」。

常見的複雜度 :
- $O(n)$
- $O(nlogn)$
- $O(n^2)$
- $O(2^n)$

原則 :

1. 不算常數，ex : O(5n) = O(3n) = O(n)
2. 兩個函數相加的 bigO 取較大的那個，$O(n^2)+O(n)=O(n^2)$
3. f(n) = O(n)，但你執行了 m 次 f(n)，複雜度就會是 $O(nm)$
4. 一般來說 bigO (複雜度) 是很悲觀的，都是認為 n 是趨於無限大的數，也就是估計一個 worst case。

---

### 第 2 章

#### 排序
- 由小排到大，由大排到小
- 二分搜尋法
- 「特定條件」來進行排序
- struct

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

// 建立一個資料型態叫 student
struct student {
    string name;
    string id;
    int grade;
};

int main() {
    student p[26];
    for(int i=0;i<26;i++) {
        cin >> p[i].name >> p[i].id >> p[i].grade;
    }
}

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

struct point {
    int x;
    int y;
};

int main() {
    int n;
    cin >> n;
    
    point p[n];
}

- sort
- `sort(start, end+1, compare);`
- 預設由小排到大，如果想由大排到小就要寫 compare function (`cmp`)。
- 若是 struct 類型想要排序，一定要傳入 compare function，才能知道這個 struct 想要怎麼排。

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

int main() {
    int n;
    cin >> n;
    
    int a[n];
    for(int i=0;i<n;i++) {
        cin >> a[i];
    }
    
    sort(a, a+n);
}

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

bool cmp(int x, int y) {
    return x > y;
}

int main() {
    int n;
    cin >> n;
    
    int a[n];
    for(int i=0;i<n;i++) cin >> a[i];
    
    sort(a, a+n, cmp);
    
    for(int i=0;i<n;i++) cout << a[i] << " ";
    cout << "\n";
    
    return 0;
}

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

struct point {
    int x;
    int y;
};

// 傳址
bool cmp(point &s, point &t) {
    return s.y > t.y;
}

int main() {
    int n;
    cin >> n;
    
    point p[n]; // 共有 n 個點，每個點都有 p[i].x, p[i].y;
    for(int i=0;i<n;i++) {
        cin >> p[i].x >> p[i].y;
    }
    
    sort(p, p+n, cmp);   // struct 需要 cmp 函式才知道自己該怎麼做排序
    
    for(int i=0;i<n;i++) {
        cout << p[i].x << " " << p[i].y << "\n";
    }
    
    return 0;
}

- 如果是「字串」進行排序，則按照「字典序」去做排序。

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

bool cmp(string x, string y) {
    return x > y;
}

int main() {
    string s[3];
    for(int i=0;i<3;i++) cin >> s[i];
    
    sort(s, s+3, cmp);
    
    for(int i=0;i<3;i++) cout << s[i] << "\n";
    
    return 0;
}

#### STL

(1) `pair<Type, Type> variable_name;`
- pair 有兩個元素 `first`, `second`。
- `<>` 裡面指的是 pair first 和 second 的 type。
- ex : `pair<int, int> p;`

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

/*
struct pair {
    Type first;
    Type second;
};
*/

bool cmp(pair<int, int> &s, pair<int, int> &t) {
    return s.second > t.second;
}

int main() {
    int n;
    cin >> n;
    
    pair<int, int> point[n];
    for(int i=0;i<n;i++) {
        cin >> point[i].first >> point[i].second;
    }
    
    sort(point, point+n, cmp);
    
    for(int i=0;i<n;i++) {
        cout << point[i].first << " " << point[i].second << "\n";
    }
    
    return 0;
}

(2) `vector<Type> variable_name;`

- 一個擁有動態大小的陣列。
- ex : `vector<int> vec;`
- `vec.push_back(n)` : 把 n 塞進 vec 這個 vector 裡面。
- `vec.size()` : 回傳 vec 裡面有幾個元素。
- 其他就跟陣列操作一樣 ex: `vec[i]`

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

int main() {
    int n;
    cin >> n;
    
    vector<int> vec;
    int tmp;
    for(int i=0;i<n;i++) {
        cin >> tmp;
        vec.push_back(tmp);
    }
    
    // ...
    sort(vec.begin(), vec.end());
    for(int i=0;i<vec.size();i++) {
        cout << vec[i] << " ";
    }
    
    int sum = 0;
    for(int i=0;i<vec.size();i++) {
        sum += vec[i];
    }
}

(3) `set<Type> variable_name;`

- 集合裡面沒有重複的數。
- `set<int> st;`
- `st.insert(n);` -> 把 n 丟進去集合裡面。
- 遍歷 (排序好的)

set<int> st;
for(auto it=st.begin();it != st.end(); it++) {
    cout << *it << " ";
}

- `st.clear()` -> 直接把集合清空。
- `st.erase(n)` -> 把 n 從集合裡面移除。
- `st.find(n)` -> 從集合裡面找到 n 並回傳。
- `st.size()` -> 集合裡面目前共有多少數。
- `st.count(n)` -> 集合裡 n 總共有幾個，在 set 中通常只有 0 跟 1，multiset 除外。

(4) `map<Key_Type, Value_Type> variable_name;`

- `map<string, int> mp;`
- `mp["kevin"] = 1;`
---

#### 二分搜尋

- 前提 : 二分搜尋只適用在「已**排序好**的陣列當中」。
- 名詞 :
- 左界 (left-side) : 搜尋標竿陣列左方的 index。 (小)
- 右界 (right-side) : 搜尋標竿陣列右方的 index。 (大)
- mid : 目前搜尋到的數字

index : 0  1  2  3  4
value : 11 22 44 67 121

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

int main() {
     int n;
     cin >> n;
     int a[n];
     for(int i=0;i<n;i++) cin >> a[i];
     
     int target;
     cin >> target;
     
     // 1. check 陣列是否排序好
     // 2. 初始化左界 / 右界
     int left = 0, right = n - 1;
     while(left <= right) {
         int mid = (left + right) / 2;
         if(a[mid] < target) {
             left = mid + 1;
         }
         else if(a[mid] > target) {
             right = mid - 1;
         }
         else {
             cout << target << "\n";
             break;
         }
     }
     
     return 0;
}

- `lower_bound()` : 用來找到第一個大於等於某個值的位置。
- `lower_bound(first, last, target);`
- 回傳「指標」(位置)

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

int main() {
     int a[10] = {1, 6, 13, 22, 23, 24, 51, 67, 99, 134};
     // int index = lower_bound(a, a+10, 23); 錯誤示範，不能用整數去接位置
     // auto 在 C++ 中可以自動識別回傳類型
     auto it = lower_bound(a, a+10, 23);    // 0x7ffc6f55d770
     
     // 使用 * 可以把該位置的值給取出來
     cout << *it << "\n";   // 23
     
     // 如果想知道 index
     cout << it - a << "\n";    // 4
     
     return 0;
}

- `upper_bound()` : 找到第一個大於某值的位置。
- `binary_search()` : 只會回傳是否有找到。

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

int main() {
     int a[10] = {1, 6, 13, 22, 23, 24, 51, 67, 99, 134};
     
     // binary_search 函數會回傳 bool
     // 1 -> true
     // 0 -> false
     bool isExisted = binary_search(a, a+10, 1000);
     
     cout << isExisted << "\n";
     
     return 0;
}

---

#### 快速冪

- 快速冪是如何快速計算 $x^y$ 的方法。
- 概念 : `(x * y) % p = (x % p) * (y % p)`
- 計算 $x^y$ 最直接的方法就是 $x$ 乘自己 $y$ 次，但要記得每次乘完都要取餘數 $(% p)$，不然算完的結果可能會 **overflow** (超過 `int` / `long long int` / ... 的範圍)。-- 方法一

int t = x;
for(int i=0;i<y;i++) {
    t = (t * x) % p;
}

- 方法一的效率太差 $O(n)$，如果 $y$ 是十億則迴圈要執行十億次，所以我們可以用「遞迴」來幫助我們把複雜度降到 $O(logn)$。
- 簡單來說就是 :
- 如果 $y$ 是奇數，則遞迴出 $y-1$ 次方的答案後再乘一次 $x$，意即 $f(y-1)*x$ (假設 f 是遞迴函數)。
- 如果 $y$ 是偶數，則求出 $y/2$ 次方後再自己乘自己，意即 $f(y/2)*f(y/2)$，終止條件是當 $y=0$ 時，回傳 $1$。


- 可以看例題 `P-2-3 快速冪`，範例 code :

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

long long exp(long long x, long long y, long long p) {
    if (y == 0) {
        return 1;
    }
    
    // 奇數
    if (y % 2 == 1) {
        return (exp(x, y-1, p) * x) % p;
    }
    
    // 偶數
    long long t = exp(x, y/2, p);
    return (t * t) % p;
}

int main() {
    // x^y % p
    long long x, y, p;
    cin >> x >> y >> p;
    
    long long ans = exp(x, y, p);
    
    cout << ans << "\n";
}

---

### 第 3 章

#### 佇列 (queue)

- 宣告 -> `queue<Type> queue_name`，`queue<int> Q`。
- 新增 -> `Q.push(data)`。
- 刪除 -> `Q.pop()`，把出口 (排第一個的東西排掉)，只是一個動作。
- 查看出口成員 -> `Q.front()`，回傳排第一個的 data。
- 檢查是否為空 -> `Q.empty()`，回傳 bool (true / false)。
- 查詢目前成員數 -> `Q.size()`。
- 遍歷 (traverse)

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

int main() {
    queue<int> Q;
    Q.push(1);
    Q.push(2);
    Q.push(3);
    
    vector<int> vec;
    while(!Q.empty()) {
        int tmp = Q.front();
        vec.push_back(tmp);
        Q.pop();
    }
}

#### 推疊 (stack)

- 宣告 -> `stack<int> st`。
- push -> `st.push(data)`，ex: `st.push(1)`。
- pop -> `st.pop()`，只是一個動作。
- top -> `st.top()`，回傳最上方的 data (最後 push 的)。
- 檢查是否為空 -> `st.empty()`。

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

int main() {
    stack<int> st;
    st.push(1);
    st.push(2);
    st.push(3);
    
    vector<int> vec;
    while(!st.empty()) {
        int tmp = st.top();
        vec.push_back(tmp);
        st.pop();
    }
}