# 秘笈
考前看一下，放輕鬆，等等一定都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;
}
```
Sign in with Wallet
Connect another wallet