UVa 程式解題通用技巧總整理

目前共有 16 個章節：橫跨基本讀檔技巧、資料結構、演算法、字串處理、動態規劃以及各種進階主題
本篇文章適合： 想要刷 UVa / 線上 OJ 的同學。後面章節的觀念也能用在 科技業 / 外商 的程式面試題上
主要程式語言： C++。部分題目如果 Python 剛好有更簡潔的寫法也會附上！

1. 輸入處理

UVa 題目的輸入格式千變萬化，掌握以下幾種模式幾乎能應付所有情況。

1.1 讀到 EOF

許多 UVa 題目不會告訴你有幾筆測資，而是「讀到檔案結束為止」。

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
using namespace std;

int main() {
    int a, b;
    // cin >> a >> b 回傳的是 cin 本身，
    // 讀取失敗（如 EOF）時會轉型成 false
    while (cin >> a >> b) {
        cout << a + b << endl;
    }
    return 0;
}

Python 對應寫法（當輸入很複雜、用 sys.stdin 更方便時）

1
2
3
4
import sys
for line in sys.stdin:
    a, b = map(int, line.split())
    print(a + b)

1.2 每次讀一整行

當輸入是「一行一筆資料」，或一行裡有空格時，要用 getline 而非 cin >>。

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <string>
using namespace std;

int main() {
    string line;
    while (getline(cin, line)) {
        // 對整行做處理
        cout << "讀到：" << line << endl;
    }
    return 0;
}

1.3 切割字串（以特定字元分隔）

當一行裡的資料以特定字元（如 /、\、,）分隔時，用 stringstream + getline 是最乾淨的做法。

範例： 切割路徑 WINNT\SYSTEM32\CONFIG

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
using namespace std;

int main() {
    string path = "WINNT\\SYSTEM32\\CONFIG";
    //                    ^^ 在 C++ 字串中，\\ 代表一個真正的反斜線 \

    stringstream ss(path);   // 把字串放進串流
    string token;
    vector<string> parts;

    // getline(來源串流, 存入變數, 遇到此字元就切開)
    while (getline(ss, token, '\\')) {
        parts.push_back(token);
    }

    for (string s : parts) {
        cout << s << endl;
    }
    // 輸出：
    // WINNT
    // SYSTEM32
    // CONFIG
    return 0;
}

同樣的技巧，換成切 CSV（逗號分隔）：

1
2
3
4
5
6
7
8
9
string row = "Alice,90,85,78";
stringstream ss(row);
string cell;
vector<string> cols;

while (getline(ss, cell, ',')) {
    cols.push_back(cell);
}
// cols = {"Alice", "90", "85", "78"}

Python 對應寫法（Python 的 split 內建就很強）

1
2
3
path = r"WINNT\SYSTEM32\CONFIG"   # r"..." 讓反斜線不被跳脫
parts = path.split("\\")
# ['WINNT', 'SYSTEM32', 'CONFIG']

1.4 混合 cin 與 getline 的陷阱

用 cin >> n 讀完數字後，換行符號還留在緩衝區。若緊接著用 getline，會讀到一個空行！

1
2
3
4
5
6
7
8
9
int n;
cin >> n;
cin.ignore();   // ← 這行很重要！吃掉殘留的換行
// 現在才能正確 getline
string line;
for (int i = 0; i < n; i++) {
    getline(cin, line);
    // ...
}

1.5 讀到特定終止值（sentinel）

不告訴你有幾筆，而是遇到特定值（如 0、-1、0 0）才停止。

1
2
3
4
5
6
7
8
9
10
int n;
while (cin >> n && n != 0) {
    // 處理
}

// 兩個數字，遇到 0 0 停止
int a, b;
while (cin >> a >> b && !(a == 0 && b == 0)) {
    // 處理
}

1.6. 多組測資，組間有空行

1
2
3
4
5
6
7
8
9
10
11
12
13
string line;
vector<string> group;
while (getline(cin, line)) {
    if (line.empty()) {
        // 處理 group
        group.clear();
    } else {
        group.push_back(line);
    }
}
if (!group.empty()) {
    // 處理最後一組（結尾可能沒有空行）
}

2. 數字與字串轉換

需求 C++ 寫法 說明
字串 → int stoi(s) C++11 起可用
字串 → long long stoll(s)
字串 → double stod(s)
int → 字串 to_string(n) C++11 起可用
字串 → int（舊式） atoi(s.c_str()) 相容舊編譯器

用 stringstream 做更彈性的轉換：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <sstream>
using namespace std;

// int → string
string intToStr(int n) {
    stringstream ss;
    ss << n;
    return ss.str();
}

// string → int
int strToInt(string s) {
    int n;
    stringstream ss(s);
    ss >> n;
    return n;
}

3. 常見資料結構速查

vector（動態陣列）

1
2
3
4
5
6
vector<int> v;
v.push_back(10);       // 加到尾端
v.pop_back();          // 移除尾端
v.size();              // 元素個數
sort(v.begin(), v.end());           // 升序排序
sort(v.begin(), v.end(), greater<int>());  // 降序排序

map（鍵值對，自動排序）

1
2
3
4
5
6
7
8
map<string, int> freq;
freq["apple"]++;
freq["banana"] = 5;

// 走訪所有 key-value
for (auto& [key, val] : freq) {
    cout << key << ": " << val << endl;
}

set（不重複集合，自動排序）

1
2
3
4
5
6
7
set<int> s;
s.insert(3);
s.insert(1);
s.insert(3);   // 重複，不會加入
// s = {1, 3}

if (s.count(3)) cout << "3 在集合中" << endl;

stack / queue

1
2
3
4
5
6
7
8
9
10
11
// Stack（後進先出）
stack<int> stk;
stk.push(1);
stk.top();    // 看頂端
stk.pop();    // 移除頂端

// Queue（先進先出）
queue<int> q;
q.push(1);
q.front();    // 看隊首
q.pop();      // 移除隊首

4. 常見演算法樣板

最大公因數（GCD）/ 最小公倍數（LCM）

1
2
3
4
5
6
7
8
9
10
11
#include <algorithm>  // C++17 前
// C++17 起可用 #include <numeric>

// 輾轉相除法
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int lcm(int a, int b) {
    return a / gcd(a, b) * b;   // 先除再乘，避免溢位
}

判斷質數

1
2
3
4
5
6
7
bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; (long long)i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

埃拉托斯特尼篩法（大量質數判斷）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const int MAXN = 1000001;
bool is_prime[MAXN];

void sieve() {
    fill(is_prime, is_prime + MAXN, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; (long long)i * i < MAXN; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j < MAXN; j += i) {
                is_prime[j] = false;
            }
        }
    }
}

二分搜尋

1
2
3
4
5
6
7
8
// 在已排序的 vector 中找值
vector<int> v = {1, 3, 5, 7, 9};

// lower_bound：第一個 >= target 的位置
auto it = lower_bound(v.begin(), v.end(), 5);
if (it != v.end() && *it == 5) {
    cout << "找到了，index = " << (it - v.begin()) << endl;
}

5. 輸出格式技巧

固定小數點位數

1
2
3
#include <iomanip>
cout << fixed << setprecision(2) << 3.14159;
// 輸出：3.14

補零（如輸出 007）

1
2
cout << setw(3) << setfill('0') << 7;
// 輸出：007

每組答案之間空一行（最後一組不空）

1
2
3
4
5
6
7
int T;
cin >> T;
for (int i = 0; i < T; i++) {
    // ... 解題 ...
    cout << ans << endl;
    if (i < T - 1) cout << endl;  // 最後一組不印空行
}

printf 風格（有時比 cout 更直覺）

1
2
3
printf("%d %d\n", a, b);
printf("%.2f\n", 3.14159);   // 輸出 3.14
printf("%05d\n", 42);        // 輸出 00042

6. 效能注意事項

加速 cin / cout

在不混用 scanf/printf 的前提下，加這兩行可大幅加速 I/O：

1
2
3
4
5
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // ... 其餘程式碼
}

⚠️ 加了這兩行之後，就不能再混用 scanf / printf，否則輸出順序會亂掉。

複雜度提醒

資料量 n 可接受的複雜度
n ≤ 10⁶ O(n) 或 O(n log n)
n ≤ 10⁴ O(n²) 勉強可以
n ≤ 500 O(n³) 可以
n ≤ 20 O(2ⁿ) 暴力枚舉（回溯）

整數溢位

int 最大約 2.1 × 10⁹，若計算中間值可能超過，改用 long long（最大約 9.2 × 10¹⁸）：

1
long long ans = (long long)a * b;  // 相乘前先轉型，避免溢位

7. 排序進階技巧

7.1 自訂排序規則

sort 的第三個參數可以是一個回傳 bool 的比較函式，代表「a 應該排在 b 前面嗎？」

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> v = {5, 2, 8, 1, 9};

// 升序（預設）
sort(v.begin(), v.end());

// 降序
sort(v.begin(), v.end(), [](int a, int b) {
    return a > b;
});

// 依絕對值升序
sort(v.begin(), v.end(), [](int a, int b) {
    return abs(a) < abs(b);
});

⚠️ 比較函式必須是嚴格弱序：若 a == b，必須回傳 false，否則會 UB（undefined behavior）。

7.2 結構體排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct Student {
    string name;
    int score;
    int id;
};

vector<Student> students = {
    {"Alice", 90, 3},
    {"Bob",   90, 1},
    {"Carol", 85, 2}
};

// 先按分數降序，分數相同按 id 升序
sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
    if (a.score != b.score) return a.score > b.score;
    return a.id < b.id;
});
// 結果：Bob(90,1), Alice(90,3), Carol(85,2)

Python 對應寫法（Python 的多鍵排序特別乾淨）

1
students.sort(key=lambda s: (-s.score, s.id))

8. 字串處理

8.1 常用字串操作速查

1
2
3
4
5
6
7
8
9
10
11
12
13
string s = "Hello, World!";

s.length();          // 13，字串長度
s.size();            // 同上，兩者通用
s.substr(7, 5);      // "World"，從 index 7 取 5 個字元
s.find("World");     // 7，回傳第一次出現的 index
s.find("xyz");       // string::npos，找不到時的回傳值
s.replace(7, 5, "C++");  // "Hello, C++!"
s.empty();           // false，是否為空字串

// 大小寫轉換（需要 #include <cctype>）
for (char& c : s) c = tolower(c);  // 全部轉小寫
for (char& c : s) c = toupper(c);  // 全部轉大寫

找不到時要判斷 npos：

1
2
3
4
size_t pos = s.find("World");
if (pos != string::npos) {
    cout << "找到了，位置：" << pos << endl;
}

8.2 字元判斷與轉換

#include <cctype> 提供一系列字元判斷函式，在處理字串題時非常好用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <cctype>

char c = 'A';

isalpha(c);   // 是否為英文字母（a-z 或 A-Z）
isdigit(c);   // 是否為數字（0-9）
isalnum(c);   // 是否為字母或數字
isspace(c);   // 是否為空白（空格、tab、換行…）
isupper(c);   // 是否為大寫字母
islower(c);   // 是否為小寫字母

toupper(c);   // 轉大寫，'a' → 'A'
tolower(c);   // 轉小寫，'A' → 'a'

// 數字字元 → 實際數值
int digit = c - '0';   // '7' → 7

// 實際數值 → 數字字元
char ch = '0' + 7;     // 7 → '7'

8.3 字串搜尋：KMP 演算法

當需要在一個長字串（text）中找一個模式（pattern）出現了幾次，暴力 O(n×m) 可能 TLE，KMP 可以做到 O(n+m)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <string>
#include <vector>
using namespace std;

// 建立 failure function（前綴函式）
vector<int> buildKMP(const string& pattern) {
    int m = pattern.size();
    vector<int> fail(m, 0);
    for (int i = 1; i < m; i++) {
        int j = fail[i - 1];
        while (j > 0 && pattern[i] != pattern[j]) j = fail[j - 1];
        if (pattern[i] == pattern[j]) j++;
        fail[i] = j;
    }
    return fail;
}

// 回傳 pattern 在 text 中所有出現的起始 index
vector<int> kmpSearch(const string& text, const string& pattern) {
    vector<int> fail = buildKMP(pattern);
    vector<int> result;
    int n = text.size(), m = pattern.size(), j = 0;
    for (int i = 0; i < n; i++) {
        while (j > 0 && text[i] != pattern[j]) j = fail[j - 1];
        if (text[i] == pattern[j]) j++;
        if (j == m) {
            result.push_back(i - m + 1);  // 找到一個匹配
            j = fail[j - 1];
        }
    }
    return result;
}

int main() {
    string text    = "ababcababcabc";
    string pattern = "ababc";
    vector<int> positions = kmpSearch(text, pattern);
    for (int pos : positions) {
        cout << "在 index " << pos << " 找到" << endl;
    }
    // 輸出：在 index 0 找到  /  在 index 5 找到
    return 0;
}

9. 動態規劃（DP）

9.1 DP 思考框架

解 DP 題時，按以下步驟思考：

  1. 定義狀態：dp[i] 或 dp[i][j] 代表什麼？
  2. 寫出轉移式：dp[i] 如何從之前的狀態推導？
  3. 決定初始值：邊界條件是什麼？
  4. 決定填表順序：由小到大？由上到下？
  5. 確認答案位置：最終要回傳哪個 dp 值？

9.2 經典一維 DP：最長遞增子序列（LIS）

問題： 給一個數列，找最長的嚴格遞增子序列長度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// O(n²) 版本（n ≤ 5000 時夠用）
int LIS(vector<int>& a) {
    int n = a.size();
    vector<int> dp(n, 1);  // dp[i]：以 a[i] 結尾的 LIS 長度

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    return *max_element(dp.begin(), dp.end());
}
1
2
3
4
5
6
7
8
9
10
11
// O(n log n) 版本（n ≤ 10⁵ 時必須用這個）
#include <algorithm>
int LIS_fast(vector<int>& a) {
    vector<int> tails;  // tails[i]：長度為 i+1 的遞增子序列，結尾最小值
    for (int x : a) {
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) tails.push_back(x);
        else *it = x;
    }
    return tails.size();
}

9.3 經典二維 DP：最長共同子序列（LCS）

問題： 給兩個字串 A、B，找它們最長的共同子序列長度（子序列不需連續）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int LCS(string& a, string& b) {
    int n = a.size(), m = b.size();
    // dp[i][j]：a 的前 i 個字元 與 b 的前 j 個字元的 LCS 長度
    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]);  // 取較大的
            }
        }
    }
    return dp[n][m];
}

9.4 背包問題

0/1 背包： 每件物品只能選一次，在重量限制 W 內最大化價值。

1
2
3
4
5
6
7
8
9
10
11
12
13
// dp[w]：背包容量恰好為 w 時，能裝的最大價值
int knapsack(vector<int>& weight, vector<int>& value, int W) {
    int n = weight.size();
    vector<int> dp(W + 1, 0);

    for (int i = 0; i < n; i++) {
        // 從右向左更新，確保每件物品只用一次
        for (int w = W; w >= weight[i]; w--) {
            dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
        }
    }
    return dp[W];
}

完全背包： 每件物品可以選無限次。

1
2
3
4
5
6
7
8
9
10
11
12
int unboundedKnapsack(vector<int>& weight, vector<int>& value, int W) {
    int n = weight.size();
    vector<int> dp(W + 1, 0);

    for (int i = 0; i < n; i++) {
        // 從左向右更新，讓同一物品可以重複使用
        for (int w = weight[i]; w <= W; w++) {
            dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
        }
    }
    return dp[W];
}

0/1 vs 完全背包，只差在一個方向：

  • 0/1 背包：內層迴圈從右向左（w = W → weight[i]）
  • 完全背包：內層迴圈從左向右（w = weight[i] → W）

10. 圖論基礎

10.1 圖的表示方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const int MAXV = 1001;

// 方法一：相鄰矩陣（適合稠密圖，V ≤ 1000）
int adjMatrix[MAXV][MAXV];

// 方法二：相鄰串列（適合稀疏圖，大多數 OJ 題用這個）
// pair<int,int> = {鄰居節點, 邊的權重}
vector<pair<int,int>> adjList[MAXV];

// 加一條 u → v 權重為 w 的邊
void addEdge(int u, int v, int w) {
    adjList[u].push_back({v, w});
    adjList[v].push_back({u, w});  // 無向圖要加這行
}

10.2 BFS（廣度優先搜尋）

適用： 無權重圖的最短路徑、層數遍歷、連通性判斷。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <queue>
#include <vector>
using namespace std;

vector<pair<int,int>> adjList[MAXV];

// 回傳從 start 到各節點的最短距離（-1 表示不可達）
vector<int> bfs(int start, int V) {
    vector<int> dist(V + 1, -1);
    queue<int> q;

    dist[start] = 0;
    q.push(start);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto [v, w] : adjList[u]) {
            if (dist[v] == -1) {          // 還沒走過
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    return dist;
}

二維格子地圖的 BFS（迷宮最短路）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int dx[] = {0, 0, 1, -1};  // 上下左右四個方向
int dy[] = {1, -1, 0, 0};

int bfsMaze(vector<string>& grid, int sr, int sc, int er, int ec) {
    int R = grid.size(), C = grid[0].size();
    vector<vector<int>> dist(R, vector<int>(C, -1));
    queue<pair<int,int>> q;

    dist[sr][sc] = 0;
    q.push({sr, sc});

    while (!q.empty()) {
        auto [r, c] = q.front(); q.pop();
        if (r == er && c == ec) return dist[r][c];
        for (int d = 0; d < 4; d++) {
            int nr = r + dx[d], nc = c + dy[d];
            if (nr >= 0 && nr < R && nc >= 0 && nc < C
                && grid[nr][nc] != '#'          // '#' 是牆
                && dist[nr][nc] == -1) {
                dist[nr][nc] = dist[r][c] + 1;
                q.push({nr, nc});
            }
        }
    }
    return -1;  // 無法到達
}

10.3 DFS（深度優先搜尋）

適用： 連通分量計算、拓撲排序、判斷環、回溯搜尋。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
vector<pair<int,int>> adjList[MAXV];
bool visited[MAXV];

void dfs(int u) {
    visited[u] = true;
    // 對 u 做你想做的事...
    for (auto [v, w] : adjList[u]) {
        if (!visited[v]) {
            dfs(v);
        }
    }
}

// 計算連通分量數量
int countComponents(int V) {
    fill(visited, visited + V + 1, false);
    int count = 0;
    for (int i = 1; i <= V; i++) {
        if (!visited[i]) {
            dfs(i);
            count++;
        }
    }
    return count;
}

10.4 最短路徑：Dijkstra

適用： 有權重（且權重為非負）的圖，單源最短路。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <queue>
#include <vector>
#include <climits>
using namespace std;

vector<pair<int,int>> adjList[MAXV];  // {鄰居, 邊權}

vector<int> dijkstra(int start, int V) {
    vector<int> dist(V + 1, INT_MAX);
    // priority_queue 預設是最大堆，用 greater<> 變成最小堆
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;

    dist[start] = 0;
    pq.push({0, start});  // {距離, 節點}

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();

        if (d > dist[u]) continue;  // 已找到更短路，跳過

        for (auto [v, w] : adjList[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

10.5 Union-Find（並查集）

適用： 判斷兩個節點是否連通、合併集合、計算連通分量。比 DFS 在動態合併時更有效率。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
struct UnionFind {
    vector<int> parent, rank;

    UnionFind(int n) : parent(n), rank(n, 0) {
        iota(parent.begin(), parent.end(), 0);  // parent[i] = i
    }

    // 找根節點（路徑壓縮）
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }

    // 合併兩個集合（按 rank 合併）
    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;  // 已在同一集合
        if (rank[x] < rank[y]) swap(x, y);
        parent[y] = x;
        if (rank[x] == rank[y]) rank[x]++;
        return true;
    }

    bool connected(int x, int y) {
        return find(x) == find(y);
    }
};

// 使用範例
int main() {
    UnionFind uf(6);   // 節點 0~5
    uf.unite(0, 1);
    uf.unite(1, 2);
    cout << uf.connected(0, 2) << endl;  // 1（連通）
    cout << uf.connected(0, 3) << endl;  // 0（不連通）
}

11. 回溯法（Backtracking）

回溯法是一種「試了不行就退回去」的搜尋策略，適合枚舉所有可能的題目。

11.1 全排列

問題： 列出 1~n 的所有排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <vector>
using namespace std;

void permute(vector<int>& arr, int start) {
    if (start == arr.size()) {
        for (int x : arr) cout << x << " ";
        cout << endl;
        return;
    }
    for (int i = start; i < arr.size(); i++) {
        swap(arr[start], arr[i]);   // 選擇
        permute(arr, start + 1);    // 繼續往下
        swap(arr[start], arr[i]);   // 撤銷選擇（回溯）
    }
}

int main() {
    vector<int> arr = {1, 2, 3};
    permute(arr, 0);
    // 輸出 1 2 3 / 1 3 2 / 2 1 3 / 2 3 1 / 3 2 1 / 3 1 2
}

C++ 內建全排列（簡單版）：

1
2
3
4
5
6
7
#include <algorithm>
vector<int> arr = {1, 2, 3};
sort(arr.begin(), arr.end());  // 必須先排序！
do {
    for (int x : arr) cout << x << " ";
    cout << endl;
} while (next_permutation(arr.begin(), arr.end()));

11.2 組合枚舉

問題： 從 n 個數中選 k 個，列出所有組合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void combine(int n, int k, int start, vector<int>& current) {
    if (current.size() == k) {
        for (int x : current) cout << x << " ";
        cout << endl;
        return;
    }
    for (int i = start; i <= n; i++) {
        current.push_back(i);             // 選擇 i
        combine(n, k, i + 1, current);    // 下一個從 i+1 開始（不重複）
        current.pop_back();               // 撤銷選擇（回溯）
    }
}

int main() {
    vector<int> current;
    combine(4, 2, 1, current);
    // 輸出：1 2 / 1 3 / 1 4 / 2 3 / 2 4 / 3 4
}

回溯法通用骨架：

1
2
3
4
5
6
7
8
9
10
11
void backtrack(狀態) {
    if (達到終止條件) {
        記錄/輸出結果;
        return;
    }
    for (每一個可能的選擇) {
        做選擇;
        backtrack(新狀態);
        撤銷選擇;  // ← 這是回溯的關鍵！
    }
}

12. 貪心演算法（Greedy）

貪心的核心概念是：每一步都選當下最好的選擇，且不回頭。它不一定適用所有題目，但適用時往往比 DP 快很多。

12.1 判斷貪心是否適用

貪心通常適用的情境：

  • 題目有「最大化/最小化某個量」的要求
  • 局部最優解能推導出全局最優解
  • 可以證明「換一個選擇不會更好」

常見反例（貪心不適用）：0/1 背包（選最高性價比物品未必最優），此時要用 DP。

12.2 活動選擇問題（區間排程）

問題： 給 n 個活動，每個活動有開始時間和結束時間，同一時間只能參加一個活動，最多能參加幾個？

貪心策略：永遠選結束時間最早的活動。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <algorithm>
#include <vector>
using namespace std;

int maxActivities(vector<pair<int,int>>& activities) {
    // 按結束時間排序
    sort(activities.begin(), activities.end(), [](auto& a, auto& b) {
        return a.second < b.second;
    });

    int count = 1;
    int lastEnd = activities[0].second;

    for (int i = 1; i < activities.size(); i++) {
        if (activities[i].first >= lastEnd) {  // 開始時間 >= 上一個活動的結束時間
            count++;
            lastEnd = activities[i].second;
        }
    }
    return count;
}

12.3 最少硬幣問題（找零）

問題： 給定硬幣面額（通常為標準幣制，如 1, 5, 10, 25），湊出指定金額最少需要幾枚？

⚠️ 此題用貪心的前提是「標準幣制」。若硬幣面額任意（如 1, 3, 4），貪心可能不是最優解，需改用 DP。

1
2
3
4
5
6
7
8
9
10
int minCoins(vector<int>& coins, int amount) {
    // 必須先由大到小排序
    sort(coins.begin(), coins.end(), greater<int>());
    int count = 0;
    for (int coin : coins) {
        count += amount / coin;
        amount %= coin;
    }
    return (amount == 0) ? count : -1;  // -1 表示無法湊出
}

12.4 區間覆蓋（最少區間數）

問題： 給 n 個區間，最少需要幾個區間才能覆蓋 [L, R]？

貪心策略：每次從能覆蓋當前起點的區間中，選右端點最遠的那個。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int minIntervals(vector<pair<int,int>>& intervals, int L, int R) {
    sort(intervals.begin(), intervals.end());  // 按左端點排序

    int count = 0, curEnd = L, i = 0, n = intervals.size();
    while (curEnd < R) {
        int farthest = curEnd;
        // 找所有左端點 <= curEnd 的區間中，右端點最遠的
        while (i < n && intervals[i].first <= curEnd) {
            farthest = max(farthest, intervals[i].second);
            i++;
        }
        if (farthest == curEnd) return -1;  // 無法繼續延伸，覆蓋失敗
        curEnd = farthest;
        count++;
    }
    return count;
}

13. 數學技巧

13.1 進位轉換

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <string>
#include <algorithm>
using namespace std;

// 10 進位整數 → 任意進位字串
string toBase(int n, int base) {
    if (n == 0) return "0";
    string result = "";
    bool negative = (n < 0);
    if (negative) n = -n;
    while (n > 0) {
        int rem = n % base;
        result += (rem < 10) ? ('0' + rem) : ('A' + rem - 10);
        n /= base;
    }
    if (negative) result += '-';
    reverse(result.begin(), result.end());
    return result;
}

// 任意進位字串 → 10 進位整數
int fromBase(const string& s, int base) {
    int result = 0;
    for (char c : s) {
        int digit = isdigit(c) ? (c - '0') : (toupper(c) - 'A' + 10);
        result = result * base + digit;
    }
    return result;
}

Python 對應寫法（一行搞定）

1
2
3
4
5
bin(10)   # '0b1010'（十進位 → 二進位）
oct(10)   # '0o12'  （十進位 → 八進位）
hex(255)  # '0xff'  （十進位 → 十六進位）
int('1010', 2)   # 10（二進位 → 十進位）
int('ff', 16)    # 255（十六進位 → 十進位）

13.2 快速冪（大數次方取模）

直接計算 a^b 會溢位，且 b 可能極大。快速冪用分治法，在 O(log b) 內算出 a^b % mod。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 計算 (base^exp) % mod
long long powMod(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;  // exp 的最低位是 1
        base = base * base % mod;
        exp >>= 1;  // exp 右移一位（相當於除以 2）
    }
    return result;
}

// 範例：2^10 % 1000000007 = 1024
cout << powMod(2, 10, 1000000007) << endl;

13.3 組合數（C(n, k)）

方法一：Pascal’s Triangle（小 n 適用）

1
2
3
4
5
6
7
8
9
10
11
12
// 預先建表，C[i][j] = C(i, j)
const int MAXN = 101;
long long C[MAXN][MAXN];

void buildPascal() {
    for (int i = 0; i < MAXN; i++) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; j++) {
            C[i][j] = C[i-1][j-1] + C[i-1][j];
        }
    }
}

方法二：費馬小定理（大 n，需取模）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const long long MOD = 1e9 + 7;

long long fact[100001], inv_fact[100001];

long long powMod(long long base, long long exp, long long mod) { /* 同上 */ }

void precompute(int n) {
    fact[0] = 1;
    for (int i = 1; i <= n; i++) fact[i] = fact[i-1] * i % MOD;
    inv_fact[n] = powMod(fact[n], MOD - 2, MOD);  // 費馬小定理求逆元
    for (int i = n - 1; i >= 0; i--) inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;
}

long long nCr(int n, int r) {
    if (r < 0 || r > n) return 0;
    return fact[n] % MOD * inv_fact[r] % MOD * inv_fact[n-r] % MOD;
}

13.4 常用數學公式速查

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 1 + 2 + ... + n
long long sumN(long long n) { return n * (n + 1) / 2; }

// 1² + 2² + ... + n²
long long sumSq(long long n) { return n * (n + 1) * (2*n + 1) / 6; }

// 判斷是否為完全平方數
bool isPerfectSquare(long long n) {
    long long s = sqrt((double)n);
    // sqrt 可能有浮點誤差，多檢查鄰近值
    for (long long x = max(0LL, s-1); x <= s+1; x++)
        if (x * x == n) return true;
    return false;
}

// 質因數分解
map<int,int> primeFactors(int n) {
    map<int,int> factors;
    for (int i = 2; (long long)i * i <= n; i++) {
        while (n % i == 0) {
            factors[i]++;
            n /= i;
        }
    }
    if (n > 1) factors[n]++;
    return factors;
}

14. 樹（Tree）

14.1 樹的基本建法與 DFS

樹是無環連通圖，常用相鄰串列表示。根節點通常為 1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <vector>
using namespace std;

vector<int> children[MAXV];  // 無權重樹
int parent[MAXV], depth[MAXV];

void dfs(int u, int par, int dep) {
    parent[u] = par;
    depth[u] = dep;
    for (int v : children[u]) {
        if (v != par) {        // 不走回頭路
            dfs(v, u, dep + 1);
        }
    }
}
// 呼叫：dfs(1, -1, 0);

14.2 計算子樹大小與直徑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int subtreeSize[MAXV];

void calcSize(int u, int par) {
    subtreeSize[u] = 1;
    for (int v : children[u]) {
        if (v != par) {
            calcSize(v, u);
            subtreeSize[u] += subtreeSize[v];
        }
    }
}

// 樹的直徑：從任意節點出發，做兩次 BFS/DFS
// 第一次找最遠節點 A，第二次從 A 找最遠節點 B，A-B 距離即為直徑
int farthestNode, maxDist;

void findFarthest(int u, int par, int dist) {
    if (dist > maxDist) {
        maxDist = dist;
        farthestNode = u;
    }
    for (int v : children[u]) {
        if (v != par) findFarthest(v, u, dist + 1);
    }
}

int treeDiameter(int root) {
    maxDist = 0;
    findFarthest(root, -1, 0);   // 第一次 DFS
    int A = farthestNode;
    maxDist = 0;
    findFarthest(A, -1, 0);      // 從 A 做第二次 DFS
    return maxDist;
}

14.3 最低共同祖先（LCA）— 二倍增法

問題： 給一棵樹，多次詢問兩個節點的最近公共祖先。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
const int LOG = 17;  // 2^17 > 10^5
int anc[MAXV][LOG];  // anc[u][k] = u 的第 2^k 個祖先
int dep[MAXV];

void dfsLCA(int u, int par, int d) {
    anc[u][0] = par;
    dep[u] = d;
    for (int k = 1; k < LOG; k++)
        anc[u][k] = anc[anc[u][k-1]][k-1];
    for (int v : children[u])
        if (v != par) dfsLCA(v, u, d + 1);
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int diff = dep[u] - dep[v];
    // 先把 u 提升到和 v 同深度
    for (int k = 0; k < LOG; k++)
        if ((diff >> k) & 1) u = anc[u][k];
    if (u == v) return u;
    // 同時往上跳，直到剩最後一步
    for (int k = LOG - 1; k >= 0; k--)
        if (anc[u][k] != anc[v][k]) {
            u = anc[u][k];
            v = anc[v][k];
        }
    return anc[u][0];
}

15. 樹狀陣列（BIT / Fenwick Tree）

適用： 需要頻繁做「單點更新」和「前綴和查詢」的題目，O(log n) 完成每次操作。

15.1 基本版：單點更新 + 前綴和查詢

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
struct BIT {
    int n;
    vector<int> tree;

    BIT(int n) : n(n), tree(n + 1, 0) {}

    // 在位置 i 加上 delta
    void update(int i, int delta) {
        for (; i <= n; i += i & (-i))  // i & (-i) 取最低位的 1
            tree[i] += delta;
    }

    // 查詢前綴和 [1, i]
    int query(int i) {
        int sum = 0;
        for (; i > 0; i -= i & (-i))
            sum += tree[i];
        return sum;
    }

    // 查詢區間和 [l, r]
    int rangeQuery(int l, int r) {
        return query(r) - query(l - 1);
    }
};

int main() {
    BIT bit(10);
    bit.update(3, 5);   // index 3 加 5
    bit.update(7, 3);   // index 7 加 3
    cout << bit.rangeQuery(2, 8) << endl;  // 輸出 8
}

15.2 進階版：區間更新 + 單點查詢

利用差分陣列的概念，讓 BIT 支援區間加值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct BIT_range {
    int n;
    vector<long long> tree;

    BIT_range(int n) : n(n), tree(n + 2, 0) {}

    void update(int i, long long delta) {
        for (; i <= n; i += i & (-i)) tree[i] += delta;
    }

    // 對區間 [l, r] 所有元素加上 delta
    void rangeUpdate(int l, int r, long long delta) {
        update(l, delta);
        update(r + 1, -delta);
    }

    // 查詢單點 i 的值（原陣列全 0 時）
    long long pointQuery(int i) {
        long long sum = 0;
        for (; i > 0; i -= i & (-i)) sum += tree[i];
        return sum;
    }
};

16. 線段樹（Segment Tree）

BIT 能做的事線段樹都能做，而且線段樹還能支援更複雜的區間操作（如區間最大值、區間最小值）。

16.1 基本版：區間最大值查詢

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
struct SegTree {
    int n;
    vector<int> tree;

    SegTree(int n, vector<int>& arr) : n(n), tree(4 * n) {
        build(arr, 1, 0, n - 1);
    }

    void build(vector<int>& arr, int node, int l, int r) {
        if (l == r) { tree[node] = arr[l]; return; }
        int mid = (l + r) / 2;
        build(arr, 2*node, l, mid);
        build(arr, 2*node+1, mid+1, r);
        tree[node] = max(tree[2*node], tree[2*node+1]);
    }

    // 單點更新：將位置 pos 的值改為 val
    void update(int node, int l, int r, int pos, int val) {
        if (l == r) { tree[node] = val; return; }
        int mid = (l + r) / 2;
        if (pos <= mid) update(2*node, l, mid, pos, val);
        else            update(2*node+1, mid+1, r, pos, val);
        tree[node] = max(tree[2*node], tree[2*node+1]);
    }

    // 查詢區間 [ql, qr] 的最大值
    int query(int node, int l, int r, int ql, int qr) {
        if (ql > r || qr < l) return INT_MIN;  // 完全不重疊
        if (ql <= l && r <= qr) return tree[node];  // 完全包含
        int mid = (l + r) / 2;
        return max(query(2*node, l, mid, ql, qr),
                   query(2*node+1, mid+1, r, ql, qr));
    }

    // 對外介面（不用每次傳 1, 0, n-1）
    void update(int pos, int val) { update(1, 0, n-1, pos, val); }
    int  query(int l, int r)      { return query(1, 0, n-1, l, r); }
};

int main() {
    vector<int> arr = {2, 5, 1, 8, 3, 7};
    SegTree st(6, arr);
    cout << st.query(1, 4) << endl;   // 輸出 8（區間最大值）
    st.update(2, 10);                 // 將 index 2 改成 10
    cout << st.query(1, 4) << endl;   // 輸出 10
}

可能持續更新中…