---
# System prepended metadata

title: 秘笈

---

# 秘笈

考前看一下，放輕鬆，等等一定都AC！

## 宣告
```cpp=
vector<vector<int>> v1(n,vector<int>(m,0)); // 二維vector宣告+初始化
// 其它型態：bool, pair<int,int>, char, string, double, long long
// 可用 typedef pair<pair<int,int>,int> side 簡化宣告，接下來使用side即可宣告
```

## 輸入
* 正常輸入 n 筆
```cpp=
int n;
cin >> n;
for(int i=0;i<n;i++){
    //cin >>
}
```

* 輸入直到0為止
```cpp=
int n;
while(cin >> n){
    if(n==0) break;
    
    // 正常操作
}
```

* 整行讀取，以逗號(或字元)分隔
```cpp=
string s;
getline(cin,s);
stringstream ss(s);
int n;
char c;
while(cin >> n >> c){
    // 正常操作
}
// 注意，若 n,c 數量不等，可以在字串尾端增加一個無用字元
// s+=','
// 這樣就可以順利讀取所有 n
// 舉例：1,2,3,4,5，照上方讀取只會得到1 2 3 4，5 因為沒有逗號所以while不成立
// 補上尾端逗號以後就變成 1,2,3,4,5,，就能順利讀取了
```
```cpp=
// 也可以直接做，對於逗號的部分，如果是其他字元有特殊用途(例如數學函式計算)可另做判斷
string s;
cin >> s;
for(int i=0;i<s.size();i++){
    if(s[i]==',') continue;
    
    // 正常操作
}
// isdigit()可以視情況使用，自帶判斷該字元是否為整數的功能，是 bool
```

## 型別轉換

* 字元轉整數
```cpp=
char c;
cin >> c;
int n=c-'0';
```

* 整數轉字元
```cpp=
int n;
cin >> n;
char c=n+'0';
```

* 字串轉整數
```cpp=
string s;
cin >> s;
int i = stoi(s);
```

* 整數轉字串
```cpp=
int x;
cin >> x;
string s = to_string(x);
```

## 常用STL

* 排序
```cpp=
// O(nlogn)
vector<pair<int,int>> v;
sort(v.begin(),v.end());
// 注意，若未指定排序，會依照第一個元素開始升冪排序，也就是 .first
// 自訂排序可以宣告副函式cmp
/*
  bool cmp(int a,int b){
      return a>b;
  }
  
  sort(v.begin(),v.end(),cmp);
*/ 
```

* 序列
```cpp=
// O(1)插入 & 取值
queue<int> q;
// 可用函式：q.push(),q.pop(),q.front(),q.empty(),q.size()
deque<int> dq;
// 可用函式：dq.push_back(),dq.push_front(),dq.pop_back(),dq.pop_front(),dq.front(),dq.back(),dq.empty(),dq.size()
```

* 最大最小堆
```cpp=
// 插入O(log n)，取值O(1)
priority_queue<int> pq1; // 最大堆
// 可用函式：pq.push(),pq.top(),pq.pop(),pq.empty(),pq.size()
pruoruty_queue<int,vector<int>,greater<int>> pq2; // 最小堆
// 也是可以把存進去的值加上負號，直接拿最大堆當最小堆用
```

* 堆疊
```cpp=
// O(1)插入 & 取值
stack<int> st;
// 可用函式：st.push(),q.pop(),st.top(),st.empty(),st.size()
```

* set
```cpp=
// O(log n)插入 & 取值
set<int> s;
// 可用函式：s.insert(),s.count(),s.find(),s.erase(),s.clear(),s.empty(),s.size()
/* 補充find,count用法：
    if(s.find(n)!=s.end()){
        // 判斷有無出現
    }
    //也可以寫成這樣
    if(count(n)){
        // 如果是set會去重，只出現0或1
    }
*/ 
unordered_set<int> us; // 無序
multiset<int> ms;      // 可重複
```

* map
```cpp=
// O(log n) 插入 & 取值
map<string, int> mp;
// 可用函式：mp[],mp.erase(),mp.find(),mp.count(),mp.clear(),mp.empty(),mp.size()

/* 常見寫法
    mp[key] = value;
    my[key]++; // 計數的寫法
    if(mp.find("key") != mp.end()){
        cout << mp["key"];
    }
*/
unordered_map<string, int> ump; // 無序
multimap<string, int> mmp;      // 可重複
```

## 圖論

* 密集圖
```cpp=
// 密集圖存點
int n,m; // 地圖大小n*m
cin >> n >> m;
vector<vector<int>> v(n,vector<int>(m));
for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
        cin >> v[i][j];
    }
}
```
```cpp=
// 密集圖BFS
int dx[4]={0,0,1,-1}; // 可以改8方向
int dy[4]={1,-1,0,0};
vector<vector<int>> v(n,vector<int>(m)); // 圖
vector<vector<bool>> vis(n,vector<bool>(m,false)); // 拜訪狀態
vector<vector<int>> dis(n,vector<int>(m)); // 最短距離(或者其他要記錄的東西)
queue<pair<int,int>> q;
q.push({0,0}); // 假設 (0,0) 為起點
vis[0][0]=true;
dis[0][0]=0;
while(!q.empty()){
    auto now=q.front();
    q.pop();
    int nowx=now.first;
    int nowy=now.second;

    for(int i=0;i<4;i++){
        int nx=nowx+dx[i],ny=nowy+dy[i];
        if(nx>=0 and  nx<n and ny>=0 and ny<m){ // 越界檢查
            if(!vis[nx][ny] and v[nx][ny]!=-1){ // 假設-1是牆無法通行
                q.push({nx,ny});
                vis[nx][ny]=true;
                dis[nx][ny]=dis[nowx][nowy]+1;
            }
        }
    }
}
cout << dis[n-1][m-1]; // 假設 (n-1,m-1) 為終點
```
```cpp=
// 密集圖DFS
int dx[4] = {0, 0, 1, -1}; // 可以改8方向
int dy[4] = {1, -1, 0, 0};
vector<vector<int>> v(n, vector<int>(m)); // 圖
vector<vector<bool>> vis(n, vector<bool>(m, false)); // 拜訪狀態
vector<vector<int>> dis(n, vector<int>(m)); // 最短距離(或其他要記錄的東西)

void dfs(int nowx, int nowy, int d) {
    vis[nowx][nowy] = true;
    dis[nowx][nowy] = d;
    for (int i = 0; i < 4; i++) {
        int nx = nowx + dx[i], ny = nowy + dy[i];
        if (nx >= 0 and nx < n and ny >= 0 and ny < m) { // 越界檢查
            if (!vis[nx][ny] and v[nx][ny] != -1) { // 假設 -1 是牆無法通行
                dfs(nx, ny, d + 1);
            }
        }
    }
}

dfs(0, 0, 0); // 假設 (0,0) 為起點
cout << dis[n-1][m-1]; // 假設 (n-1,m-1) 為終點
```

* 疏散圖
```cpp=
// 疏散圖存邊
int n,m; // n個點,m條邊
cin >> n >> m;
vector<vector<pair<int,int>>> v(n):
for(int i=0;i<m;i++){
    int x,y,z; // 連接兩點,權重
    cin >> x >> y >> z;
    v[x].push_back({y,z});
    v[y].push_back({x,z}); // 無向圖才需要反向存
}
```


```cpp=
// 疏散圖BFS
vector<vector<pair<int,int>>> v(n); // 圖(pair<鄰點,權重>)
vector<bool> vis(n, false); // 拜訪狀態
vector<int> dis(n, 1e9); // 最短距離(或者其他要記錄的東西)
queue<int> q;
q.push(0); // 假設 0 為起點
vis[0] = true;
dis[0] = 0;
while (!q.empty()) {
    int now = q.front();
    q.pop();

    for (auto it : v[now]) {  // it.first = 鄰點, it.second = 權重
        int nxt = it.first;
        if (!vis[nxt]) {
            q.push(nxt);
            vis[nxt] = true;
            dis[nxt] = dis[now] + it.second; // 無權圖距離 +1
        }
    }
}

cout << dis[n-1]; // 假設 n-1 為終點
```
```cpp=
// 疏散圖DFS
vector<vector<pair<int,int>>> v(n); // 圖 (pair<鄰點,權重>)
vector<bool> vis(n, false);         // 拜訪狀態
vector<int> dis(n, 1e9);            // 最短距離(或者其他要記錄的東西)

void dfs(int now, int d) {
    vis[now] = true;
    dis[now] = min(dis[now], d);
    for (auto it : v[now]) { // it.first = 鄰點, it.second = 權重
        int nxt = it.first;
        int w = it.second;   // 權重，可為 1 代表無權圖
        if (!vis[nxt]) {
            dfs(nxt, d + w);
        }
    }
}

dfs(0, 0); // 假設 0 為起點
cout << dis[n-1]; // 假設 n-1 為終點

```

## 進階圖論
```cpp=
// 拓樸排序（Kahn算法）
vector<vector<int>> g(n); // 圖
vector<int> indeg(n, 0);  // 入度
queue<int> q;
vector<int> topo;         // 結果序列

// 建圖後：g[u].push_back(v); indeg[v]++;

// 初始化：將所有入度為0的點入隊
for (int i = 0; i < n; i++)
    if (indeg[i] == 0) q.push(i);

// BFS 依序處理
while (!q.empty()) {
    int u = q.front(); q.pop();
    topo.push_back(u);
    for (int v : g[u]) {
        indeg[v]--;
        if (indeg[v] == 0) q.push(v);
    }
}

// 若 topo.size() < n → 圖中有環
for (int x : topo) cout << x << " ";
```
尤拉路徑：恰有 0 或 2 個奇度數頂點
尤拉迴路：所有點度數皆為偶數
```cpp=
// 無向圖 尤拉路徑 (Hierholzer演算法)
#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<vector<pair<int,int>>> g;
vector<bool> used;
vector<int> path;

void dfs(int u){
    for(auto [v,id] : g[u]){
        if(used[id]) continue;
        used[id] = true;
        dfs(v);
    }
    path.push_back(u);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    g.assign(n, {});
    used.assign(m, false);

    for(int i=0;i<m;i++){
        int u,v;
        cin >> u >> v;
        g[u].push_back({v,i});
        g[v].push_back({u,i});
    }

    // 找起點（若有兩個奇度點，從其中一個開始）
    int start = 0;
    int odd = 0;
    for(int i=0;i<n;i++){
        if(g[i].size() % 2 == 1){
            odd++;
            start = i;
        }
    }
    if(odd != 0 && odd != 2){
        cout << "No Euler Path\n";
        return 0;
    }

    dfs(start);
    reverse(path.begin(), path.end());

    if((int)path.size() != m+1){
        cout << "Graph not connected or edges left\n";
        return 0;
    }

    cout << "Euler Path:\n";
    for(int v : path) cout << v << " ";
    cout << "\n";
}

```
```cpp=
// 簡單環（無向圖）
#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<vector<int>> g;
vector<int> path;
vector<bool> vis;
set<vector<int>> cycles; // 用 set 避免重複環

void dfs(int u, int parent) {
    vis[u] = true;
    path.push_back(u);

    for (int v : g[u]) {
        if (v == parent) continue; // 不走回父節點

        auto it = find(path.begin(), path.end(), v);
        if (it != path.end()) {
            // 找到環
            vector<int> cycle(it, path.end());
            // 讓環的起點最小，避免重複
            rotate(cycle.begin(), min_element(cycle.begin(), cycle.end()), cycle.end());
            cycles.insert(cycle);
        } else if (!vis[v]) {
            dfs(v, u);
        }
    }

    path.pop_back();
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    g.assign(n, {});
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    for (int i = 0; i < n; i++) {
        vis.assign(n, false);
        path.clear();
        dfs(i, -1);
    }

    cout << "Simple cycles found:\n";
    for (auto &cyc : cycles) {
        for (int x : cyc) cout << x << " ";
        cout << cyc[0] << "\n"; // 回到起點
    }
}
```
```cpp=
// Tarjan 找橋演算法（無向圖）
#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<vector<pair<int,int>>> g;
vector<int> tin, low;
vector<bool> vis;
int timer = 0;

void dfs(int u, int p_edge) {
    vis[u] = true;
    tin[u] = low[u] = ++timer;

    for (auto [v, id] : g[u]) {
        if (id == p_edge) continue; // 不走回來的那條邊

        if (vis[v]) {
            // 反向邊（往祖先連）
            low[u] = min(low[u], tin[v]);
        } else {
            dfs(v, id);
            low[u] = min(low[u], low[v]);

            if (low[v] > tin[u]) {
                cout << "Bridge found: " << u << " - " << v << "\n";
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    g.assign(n, {});
    tin.assign(n, -1);
    low.assign(n, -1);
    vis.assign(n, false);

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back({b, i});
        g[b].push_back({a, i});
    }

    for (int i = 0; i < n; i++)
        if (!vis[i])
            dfs(i, -1);
}
```
```cpp=
// Tarjan SCC（有向圖）
#include <bits/stdc++.h>
using namespace std;

int n, m, timer = 0, scc_count = 0;
vector<vector<int>> g;
vector<int> tin, low, scc_id;
vector<bool> in_stack;
stack<int> stk;

void dfs(int u) {
    tin[u] = low[u] = ++timer;
    stk.push(u);
    in_stack[u] = true;

    for (int v : g[u]) {
        if (tin[v] == 0) {
            dfs(v);
            low[u] = min(low[u], low[v]);
        } else if (in_stack[v]) {
            // 回邊 → 更新 low[u]
            low[u] = min(low[u], tin[v]);
        }
    }

    // 若是 SCC 根
    if (low[u] == tin[u]) {
        cout << "SCC #" << ++scc_count << ": ";
        while (1) {
            int v = stk.top(); stk.pop();
            in_stack[v] = false;
            cout << v << " ";
            scc_id[v] = scc_count;
            if (v == u) break;
        }
        cout << "\n";
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    g.assign(n + 1, {});
    tin.assign(n + 1, 0);
    low.assign(n + 1, 0);
    scc_id.assign(n + 1, 0);
    in_stack.assign(n + 1, false);

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b); // 有向邊
    }

    for (int i = 1; i <= n; i++)
        if (tin[i] == 0)
            dfs(i);
}

```
## 最短路徑演算法
```cpp=
// Dijkstra
#include <bits/stdc++.h>
using namespace std;

struct Edge { int to; long long w; };
const long long INF = 1e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, s;
    cin >> n >> m >> s;
    vector<vector<Edge>> g(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v; long long w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        // 若是無向圖再加這行：
        // g[v].push_back({u, w});
    }

    vector<long long> dist(n + 1, INF);
    priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;

    dist[s] = 0;
    pq.push({0, s});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d != dist[u]) continue;
        for (auto [v, w] : g[u]) {
            if (dist[v] > d + w) {
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
    }

    for (int i = 1; i <= n; i++)
        cout << (dist[i] == INF ? -1 : dist[i]) << " ";
}
```
```cpp=
// Bellman-Ford（允許負邊）
#include <bits/stdc++.h>
using namespace std;
struct Edge { int u, v; long long w; };
const long long INF = 1e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, s;
    cin >> n >> m >> s;
    vector<Edge> edges(m);
    for (int i = 0; i < m; i++) cin >> edges[i].u >> edges[i].v >> edges[i].w;

    vector<long long> dist(n + 1, INF);
    dist[s] = 0;

    for (int i = 1; i < n; i++)
        for (auto [u, v, w] : edges)
            if (dist[u] != INF && dist[v] > dist[u] + w)
                dist[v] = dist[u] + w;

    // 負環檢查
    bool neg = false;
    for (auto [u, v, w] : edges)
        if (dist[u] != INF && dist[v] > dist[u] + w)
            neg = true;

    if (neg) cout << "Negative cycle detected\n";
    else
        for (int i = 1; i <= n; i++)
            cout << (dist[i] == INF ? -1 : dist[i]) << " ";
}
```
```cpp=
// Floyd-Warshall
// O(n^3)
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e15;
long long d[505][505];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            d[i][j] = (i == j ? 0 : INF);

    for (int i = 0; i < m; i++) {
        int u, v; long long w;
        cin >> u >> v >> w;
        d[u][v] = min(d[u][v], w);
        // 若是無向圖再加：
        // d[v][u] = min(d[v][u], w);
    }

    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            cout << (d[i][j] == INF ? -1 : d[i][j]) << " ";
        cout << '\n';
    }
}
```
## 樹論

```cpp=
// 樹上BFS
vector<vector<int>> tree(n);
vector<int> dis(n, -1);
queue<int> q;
q.push(0);
dis[0] = 0;

while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : tree[u]) {
        if (dis[v] == -1) {
            dis[v] = dis[u] + 1;
            q.push(v);
        }
    }
}
```

```cpp=
// 樹上DFS
vector<vector<int>> tree(n);
vector<bool> vis(n, false);

void dfs(int u, int p) { // p 為父節點
    vis[u] = true;
    for (int v : tree[u]) {
        if (v == p) continue;
        dfs(v, u);
    }
}
dfs(0, -1);
```

從任意點 A 出發，找到距離最遠的點 B
從 B 出發，再找最遠的點 C
B–C 的距離即為直徑
```cpp=
// 樹直徑 兩次 BFS
vector<vector<int>> tree(n);
vector<int> dis(n);

auto bfs = [&](int s) {
    fill(dis.begin(), dis.end(), -1);
    queue<int> q;
    q.push(s);
    dis[s] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : tree[u]) {
            if (dis[v] == -1) {
                dis[v] = dis[u] + 1;
                q.push(v);
            }
        }
    }
};

bfs(0);
int A = max_element(dis.begin(), dis.end()) - dis.begin();
bfs(A);
int diameter = *max_element(dis.begin(), dis.end());
cout << diameter;
```

```cpp=
// LCA 二分跳躍
const int LOG = 20;
vector<vector<int>> tree(n);
vector<vector<int>> up(n, vector<int>(LOG)); // up[u][k] = u 的第 2^k 層祖先
vector<int> depth(n);

void dfs(int u, int p) {
    up[u][0] = p;
    for (int k = 1; k < LOG; k++)
        up[u][k] = up[up[u][k-1]][k-1];
    for (int v : tree[u]) {
        if (v == p) continue;
        depth[v] = depth[u] + 1;
        dfs(v, u);
    }
}

int lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);
    // 拉高 a
    int diff = depth[a] - depth[b];
    for (int k = 0; k < LOG; k++)
        if (diff >> k & 1)
            a = up[a][k];
    if (a == b) return a;
    // 同步往上跳
    for (int k = LOG-1; k >= 0; k--) {
        if (up[a][k] != up[b][k]) {
            a = up[a][k];
            b = up[b][k];
        }
    }
    return up[a][0];
}
```

## 數論
```cpp=
long long gcd(long long a, long long b) {
    while (b) {
        long long t = a % b;
        a = b;
        b = t;
    }
    return a >= 0 ? a : -a;
}

long long lcm(long long a, long long b) {
    if (a == 0 || b == 0) return 0;
    return a / mygcd(a, b) * b;
}
```
```cpp=
bool isPrime(long long n) {
    if (n < 2) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (long long i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    }
    return true;
}
```
```cpp=
// 解方程式交點(兩點式)
#include <bits/stdc++.h>
using namespace std;

const double EPS = 1e-9;

struct Point {
    double x, y;
};

// 將兩點式 (x1,y1),(x2,y2) 轉為一般式 Ax + By = C
void twoPointToGeneral(double x1, double y1, double x2, double y2,
                       double &A, double &B, double &C) {
    A = y2 - y1;          // Δy
    B = x1 - x2;          // -Δx
    C = A * x1 + B * y1;  // 套入一點求 C
}

// 求兩條線的交點
pair<bool, Point> line_intersection(Point p1, Point p2, Point p3, Point p4) {
    double A1, B1, C1, A2, B2, C2;
    twoPointToGeneral(p1.x, p1.y, p2.x, p2.y, A1, B1, C1);
    twoPointToGeneral(p3.x, p3.y, p4.x, p4.y, A2, B2, C2);

    double det = A1 * B2 - A2 * B1;
    if (fabs(det) < EPS) return {false, {0, 0}}; // 平行或重合

    double x = (C1 * B2 - C2 * B1) / det;
    double y = (A1 * C2 - A2 * C1) / det;
    return {true, {x, y}};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    Point p1, p2, p3, p4;
    cin >> p1.x >> p1.y >> p2.x >> p2.y;
    cin >> p3.x >> p3.y >> p4.x >> p4.y;

    auto [ok, P] = line_intersection(p1, p2, p3, p4);
    if (ok)
        cout << fixed << setprecision(6) << P.x << " " << P.y << "\n";
    else
        cout << "no intersection\n";
}

```
```cpp=
// 解方程式交點(直線方程式)
#include <bits/stdc++.h>
using namespace std;

const double EPS = 1e-9;

pair<bool, pair<double,double>> line_intersection(
    long long A, long long B, long long C,
    long long D, long long E, long long F) {

    double det = A * E - B * D;
    if (fabs(det) < EPS) return {false, {0, 0}}; // 平行或重合
    double x = (C * E - B * F) / det;
    double y = (A * F - C * D) / det;
    return {true, {x, y}};
}

int main() {
    long long A,B,C,D,E,F;
    cin >> A >> B >> C >> D >> E >> F;
    auto [ok, p] = line_intersection(A,B,C,D,E,F);
    if (ok) cout << fixed << setprecision(6) << p.first << " " << p.second;
    else cout << "no intersection";
}

```

## DP
```cpp=
// 背包問題
#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 = 0; 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];
}
```
```cpp=
// LCS
#include <bits/stdc++.h>
using namespace std;

int main() {
    string A, B;
    cin >> A >> B;
    int n = A.size(), m = B.size();

    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

    // 填 DP 表
    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]);
        }
    }

    // 反向追溯 LCS 字串
    string lcs = "";
    int i = n, j = m;
    while (i > 0 && j > 0) {
        if (A[i - 1] == B[j - 1]) {
            lcs += A[i - 1];
            i--; j--;
        } else if (dp[i - 1][j] >= dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }

    reverse(lcs.begin(), lcs.end());

    cout << "LCS length = " << dp[n][m] << "\n";
    cout << "LCS string = " << lcs;
}
```
```cpp=
// LIS
#include <bits/stdc++.h>
using namespace std;

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

    vector<int> dp(n, 1), pre(n, -1); // pre[i] 記錄 dp[i] 來源位置
    int ans = 1, pos = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                pre[i] = j;
            }
        }
        if (dp[i] > ans) {
            ans = dp[i];
            pos = i;
        }
    }

    // 反向尋找 LIS 序列
    vector<int> lis;
    for (int i = pos; i != -1; i = pre[i])
        lis.push_back(a[i]);
    reverse(lis.begin(), lis.end());

    cout << "LIS length = " << ans << "\n";
    cout << "LIS sequence = ";
    for (int x : lis) cout << x << " ";
}
```
```cpp=
// LIS(僅長度)
#include<bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> a(n); // 原序列
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    vector<int> b; // LIS每個位置的最小值
    for(int i=0;i<n;i++){
        if(b.empty() or b.back()<a[i]){ // 空序列or現在這個數比LIS最後一位還大
            b.push_back(a[i]); // 插入到LIS最後方
        }
        else{
            *lower_bound(b.begin(),b.end(),a[i])=a[i];
            // 使用二分搜找到第一個大於a[i]的數字，將其替換成更小的a[i]。
        }
    }
    cout << b.size(); // 輸出LIS長度
    return 0;
}
```
```cpp=
// 最少硬幣數
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    long long n, target;
    cin >> n >> target;
    vector<long long> coin(n);
    for (int i = 0; i < n; i++) cin >> coin[i];

    const long long INF = 1e18;
    vector<long long> dp(target + 1, INF);
    dp[0] = 0; // 0 元不用硬幣

    for (int i = 0; i < n; i++) {
        for (int j = coin[i]; j <= target; j++) {
            dp[j] = min(dp[j], dp[j - coin[i]] + 1);
        }
    }

    if (dp[target] == INF) cout << -1; // 無法湊出
    else cout << dp[target];
}
```
```cpp=
// 硬幣組合數
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    long long n, target;
    cin >> n >> target;
    vector<long long> coin(n);
    for (int i = 0; i < n; i++) cin >> coin[i];

    vector<long long> dp(target + 1, 0);
    dp[0] = 1; // 只有一種方式湊出 0 元

    for (int i = 0; i < n; i++) {
        for (int j = coin[i]; j <= target; j++) {
            dp[j] += dp[j - coin[i]];
        }
    }

    cout << dp[target];
}
```
```cpp=
// 前綴和，建表O(n)，查詢O(1)
vector<int> prefix(n);
prefix[0] = a[0];
for (int i = 1; i < n; ++i) {
    prefix[i] = prefix[i-1] + a[i];
}
// 範例：若 a = {5, 2, 4, 1, 3}
// 則 prefix = {5, 7, 11, 12, 15}
// 查 a = {5,2,4,1,3} 中 [1,3] 的和：2+4+1 = 7
int sumLR = (L > 0 ? prefix[R] - prefix[L-1] : prefix[R]);
// sumLR = prefix[3] - prefix[0] = 12 - 5 = 7
```
```cpp=
// 後綴和
vector<int> suffix(n);
suffix[n-1] = a[n-1];
for (int i = n-2; i >= 0; --i) {
    suffix[i] = suffix[i+1] + a[i];
}
// 範例：若 a = {5, 2, 4, 1, 3}
// 則 suffix = {15, 10, 8, 4, 3}
// 查 a = {5,2,4,1,3} 中 [1,3] 的和：2+4+1 = 7
int sumLR_suffix = (R+1 < n ? suffix[L] - suffix[R+1] : suffix[L]);
// = suffix[1] - suffix[4] = 10 - 3 = 7
```
```cpp=
// 快速冪
long long quick_pow(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1)  // 奇數先提出一個base
            result = (result * base) % mod;
        base = (base * base) % mod;  // base 平方
        exp /= 2;  // 指數砍半
    }
    return result;
}
```


## 分治
```cpp=
// 二分搜O(nlogn)
#include <bits/stdc++.h>
using namespace std;

int binarySearch(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2; // 若不會溢位可使用(left + right) / 2
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1; // 找不到
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, target;
    cin >> n;               // 陣列大小
    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i]; // 輸入陣列
    cin >> target;          // 目標值

    int pos = binarySearch(arr, target);
    if (pos != -1) cout << "Found at index " << pos << "\n";
    else cout << "Not found\n";
}
```
```cpp=
// 函式庫二分搜
auto it = lower_bound(arr.begin(), arr.end(), target);
if (it != arr.end())
    cout << "lower_bound = " << *it << "\n";
else
    cout << "No element >= " << target << "\n";
    
auto it2 = upper_bound(arr.begin(), arr.end(), target);
if (it2 != arr.end())
    cout << "upper_bound = " << *it2 << "\n";
else
    cout << "No element > " << target << "\n";
```
```cpp=
// 逆序數對
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll merge_count(vector<ll>& a, vector<ll>& tmp, int left, int right) {
    if (left >= right) return 0; // 只有一個元素，沒有反序對
    int mid = (left + right) / 2;
    // 遞迴計算左半與右半的反序對數
    ll cnt = merge_count(a, tmp, left, mid) + merge_count(a, tmp, mid + 1, right);

    int i = left, j = mid + 1, k = left;
    while (i <= mid && j <= right) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else {
            tmp[k++] = a[j++];
            cnt += (ll)(mid - i + 1); // 左邊剩下的元素都比 a[j] 大，形成反序對
        }
    }
    while (i <= mid) tmp[k++] = a[i++];   // 把左邊剩餘元素補上
    while (j <= right) tmp[k++] = a[j++]; // 把右邊剩餘元素補上
    for (int t = left; t <= right; ++t) a[t] = tmp[t]; // 回寫合併結果
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; 
    if (!(cin >> n)) return 0;
    vector<ll> a(n), tmp(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    cout << merge_count(a, tmp, 0, n - 1) << endl;
    return 0;
}
```

## 掃描線演算法
```cpp=
// 矩陣重疊O(nlogn)
#include <bits/stdc++.h>

using namespace std;

struct Rect {
    int x1, y1, x2, y2;
    // 左下角（x1,y1）、右上角（x2,y2）
};

struct Event {
    int x, y1, y2, id, type; 
    // type = +1 (enter), -1 (exit)
    bool operator<(const Event& other) const {
        return x < other.x; // 依照 x 小到大排序
    }
};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N; // N 個矩形
    cin >> N;
    vector<Rect> rects(N);
    for (int i = 0; i < N; i++) {
        cin >> rects[i].x1 >> rects[i].y1 >> rects[i].x2 >> rects[i].y2;
    }

    // 儲存事件
    vector<Event> events;
    for (int i = 0; i < N; i++) {
        auto [x1,y1,x2,y2] = rects[i];
        events.push_back({x1, y1, y2, i, +1}); // 左邊界 在 x1
        events.push_back({x2, y1, y2, i, -1}); // 右邊界 在 x2
    }
    sort(events.begin(), events.end()); // 排序事件

    set<vector<int>> colorSets; // 存顏色組合
    set<int> activeSet;         // 當前活躍矩形
    int prevX = events[0].x; // 上一個事件，也就是左區間
    int idx = 0;
    
    // 由左而右掃描事件
    while (idx < (int)events.size()) {
        int x = events[idx].x;
        
        // 由上而下掃描活躍區間的矩陣，嘗試更新重疊組合
        if (x > prevX && !activeSet.empty()) {
            for (int y = 0; y < 200; y++) {
                vector<int> cover;
                for (int id : activeSet) {
                    if (rects[id].y1 <= y && y < rects[id].y2) {
                        cover.push_back(id);
                    }
                }
                if (!cover.empty()) {
                    sort(cover.begin(), cover.end()); // 排列方便 set 去重
                    colorSets.insert(cover);
                }
            }
        }

        // 維護活躍區間的矩陣（一次把當前 x 的所有事件處理完再往右走）
        while (idx < (int)events.size() && events[idx].x == x) {
            auto e = events[idx];
            if (e.type == +1) {
                activeSet.insert(e.id); // 加入
            } else {
                activeSet.erase(e.id);  // 移除
            }
            idx++; // 下一個事件
        }
        prevX = x; // 維護左區間
    }

    cout << colorSets.size() << endl;
    return 0;
}
```
## 貪心
```cpp=
// 找零問題
// 把面額從大到小排序，對每個面額取能取的最多數量，扣除金額後繼續，直到找零完成。
#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int m;
    long long V;
    cin >> m >> V;
    vector<long long> c(m);
    for(int i=0;i<m;i++){
        cin >> c[i];
    }
    sort(c.rbegin(), c.rend()); // 大到小
    long long remain = V;
    long long total = 0;
    for(int i=0;i<m && remain>0;i++){
        long long use = remain / c[i]; // 這個面額要用幾枚
        total += use;
        remain -= c[i] * use;
    }

    cout << total;
    return 0;
}
```
```cpp=
// 活動選擇
// 按照結束時間小到大排序，每次選擇目前結束時間最早且與已選活動不衝突的活動。
#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    vector<pair<long long,long long>> a(n);
    for(int i = 0; i < n; i++)
        cin >> a[i].first >> a[i].second;

    // 按結束時間排序
    sort(a.begin(), a.end(), [](auto &x, auto &y){
        if(x.second != y.second) return x.second < y.second;
        return x.first < y.first;
    });

    long long last = -1;
    int count = 0;

    for(auto &[s, f] : a){
        if(s >= last){
            count++;
            last = f;
        }
    }

    cout << count;
    return 0;
}
```
```cpp=
// 最小合併成本
// 每次取兩條最短繩合併（最小堆），把它們的和放回堆，累加成本。
#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    priority_queue<long long, vector<long long>, greater<long long>> pq;

    // 讀入繩子長度，放入最小堆
    for(int i = 0; i < n; i++) {
        long long l;
        cin >> l;
        pq.push(l);
    }

    long long total_cost = 0;

    // 每次合併兩條最短的繩子
    while(pq.size() > 1) {
        long long a = pq.top(); pq.pop();
        long long b = pq.top(); pq.pop();
        long long cost = a + b;
        total_cost += cost;
        pq.push(cost);  // 將合併後的繩子放回堆
    }

    cout << total_cost;
    return 0;
}
```
## 並查集
```cpp=
// f(now): 查詢現在這位玩家所屬公會的代表（公會會長）
// 同時做「路徑壓縮」，讓玩家以後能更快找到自己的會長
int f(int now) {
    if (p[now] == now) { 
        // 如果自己就是自己的會長（代表），直接回傳
        return now;
    } else {
        // 否則，往上找到會長，並把自己直接連到會長（壓縮路徑）
        return p[now] = f(p[now]);
    }
}

// 初始化：一開始每位玩家都創自己的公會（自己是自己的會長）
for (int i = 0; i < n; i++) {
    p[i] = i;
}

// 進行 m 次公會合併操作
for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b; // 讀入要合併的兩位玩家

    a = f(a); // 找出 a 所屬的公會會長
    b = f(b); // 找出 b 所屬的公會會長

    if (a != b) {
        // 如果他們不在同一個公會，就把 a 的公會併入 b 的公會
        p[a] = b;
    }
}
```
```cpp=
// 最小生成樹
#include<bits/stdc++.h>

using namespace std;

vector<int> p;

// 並查集
int f(int now){
    if(p[now]==now) return now;
    else{
        p[now]=f(p[now]);
        return p[now];
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m;
    typedef pair<int,pair<int,int>> node; // (A到B邊的權重,A點,B點)
    while(cin >> n >> m){
        int need=n-1; // n個節點的樹應該會有n-1條邊
        vector<node> v;
        p.resize(n);
        for(int i=0;i<m;i++){
            int a,b,c;
            cin >> a >> b >> c;
            v.push_back({c,{a,b}});
            v.push_back({c,{b,a}});
        }
        sort(v.begin(),v.end()); // 從邊長權重最小開始考慮
        // 並查集預設，每個節點都是單獨的集合
        for(int i=0;i<n;i++){
            p[i]=i;
        }
        long long sum=0;
        for(auto h : v){
            int x=f(h.second.first);
            int y=f(h.second.second);
            // 不可繞成環
            if(x==y){
                continue;
            }
            else{
                p[x]=y;
                need--;
                sum+=h.first;
            }
        }
        if(need==0){
            cout << sum << endl;
        }
        else{
            cout << "-1" << endl; // 無法生成MST，依題意輸出
        }
    }

    return 0;
}
```