一、數論

如果想要計算整除向上取整（x+y-1）/y 或者（x-1）/y +1

最大公約數：

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;
}

埃氏篩法：

// C++ program to print all primes smaller than or equal to
// n using Sieve of Eratosthenes
#include <bits/stdc++.h>
using namespace std;
void SieveOfEratosthenes(int n)
{// Create a boolean array "prime[0..n]" and initialize// all entries it as true. A value in prime[i] will// finally be false if i is Not a prime, else true.vector<bool> prime(n + 1, true);for (int p = 2; p * p <= n; p++) {if (prime[p] == true) {// Update all multiples of p greater than or// equal to the square of it numbers which are// multiple of p and are less than p^2 are// already been marked.for (int i = p * p; i <= n; i += p)prime[i] = false;}}// Print all prime numbersfor (int p = 2; p <= n; p++)if (prime[p])cout << p << " ";
}// Driver Code
int main()
{int n = 30;cout << "Following are the prime numbers smaller "<< " than or equal to " << n << endl;SieveOfEratosthenes(n);return 0;
}

唯一分解定理：

#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>> nums;
int main(){int x;cin>>x;for(int i=2;i<x/i;i++){if(x%i){continue;}int cnt=0;while(x%i==0){cnt++;x/=i;}nums.push_back({i,cnt});}if(x>1){nums.push_back({x,1});}int v=nums.size();for(const auto i: nums){cout<<i.first<<"^"<<i.second<<endl;}return 0;
}

快速冪：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int qmi(ll a,ll b){ll res=1;while(b){if(b&1){res=res*a;}a=a*a;b>>=1;}return res;
}
int main(){ll x,n;cin>>x>>n;ll ans=qmi(x,n);cout<<ans;return 0;
}

費馬小定理：

當 p?是質數時，a 的 (p?1)次方除以 p?的余數必為1 ?

逆元：

ll inv(ll x){return qmi(x,p-2);
}

歐拉函數：

二、組合數學?

楊輝三角?

dp法求組合數：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<int>> dp;
int main(){ll n,m,c;cin>>n>>m>>c;dp.resize(n+1);for(int i=0;i<=n;i++){dp[i].resize(m+1);dp[i][0]=1;}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){dp[i][j]=(dp[i-1][j]+dp[i-1][j-1])%c;}}cout<<dp[n][m]<<endl;return 0;
}

const int N = 70;LL C[N][N];void init() {for (int i = 0; i < N; i ++) for (int j = 0; j <= i; j ++) if (!j) C[i][j] = 1;else C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
}int main() {    ios::sync_with_stdio(false);    cin.tie(nullptr), cout.tie(nullptr);init();LL ans = 0;int n, m; cin >> n >> m;for (int i = n; i <= m; i ++) ans += C[m][i];cout << ans << endl;return 0;
}

預處理法求組合函數：僅僅適用于p為質數時候?

公式： p+q=p⊕q+2×(p&q)

這個公式的核心思想是：二進制加法可以分解為無進位加法（XOR）和進位（AND）的組合。?

三、并查集

1. 尋找根節點，函數：find(int u)，也就是判斷這個節點的祖先節點是哪個
2. 將兩個節點接入到同一個集合，函數：join(int u, int v)，將兩個節點連在同一個根節點上
3. 判斷兩個節點是否在同一個集合，函數：isSame(int u, int v)，就是判斷兩個節點是不是同一個根節點

int n = 1005; // n根據題目中節點數量而定，一般比節點數量大一點就好
vector<int> father = vector<int> (n, 0); // C++里的一種數組結構// 并查集初始化
void init() {for (int i = 0; i < n; ++i) {father[i] = i;}
}
// 并查集里尋根的過程
int find(int u) {return u == father[u] ? u : father[u] = find(father[u]); // 路徑壓縮
}// 判斷 u 和 v是否找到同一個根
bool isSame(int u, int v) {u = find(u);v = find(v);return u == v;
}// 將v->u 這條邊加入并查集
void join(int u, int v) {u = find(u); // 尋找u的根v = find(v); // 尋找v的根if (u == v) return ; // 如果發現根相同，則說明在一個集合，不用兩個節點相連直接返回father[v] = u;
}

四、二維前綴和?

#include<iostream>
using namespace std;
const int N = 1e4+10;
int n,m,q;
int a[N][N],s[N][N];int main(){scanf("%d %d %d",&n,&m,&q); for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);3for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j];while(q--){int l1,r1,l2,r2;scanf("%d %d %d %d",&l1,&r1,&l2,&r2);printf("%d",s[l2][r2]-s[l2][r1-1]-s[l1-1][r2]+s[l1-1][l2-1]);}return 0;
}

一維差分

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], diff[N]; // a為原數組，diff為差分數組// 插入操作：對區間 [l, r] 加上c
void insert(int l, int r, int c) {diff[l] += c;diff[r + 1] -= c;
}int main() {int n, m;cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> a[i];// 初始化差分數組：將每個元素視為對自身區間的插入insert(i, i, a[i]);}while (m--) {int l, r, c;cin >> l >> r >> c;insert(l, r, c); // 應用區間修改}// 計算前綴和得到最終結果for (int i = 1; i <= n; i++) {diff[i] += diff[i - 1];cout << diff[i] << " ";}return 0;
}

二維差分?

#include <iostream>
using namespace std;
const int N = 1010;
int a[N][N], diff[N][N]; // a為原矩陣，diff為差分矩陣// 插入操作：對子矩陣 (x1,y1)-(x2,y2) 加上c
void insert(int x1, int y1, int x2, int y2, int c) {diff[x1][y1] += c;diff[x2 + 1][y1] -= c;diff[x1][y2 + 1] -= c;diff[x2 + 1][y2 + 1] += c;
}int main() {int n, m, q;cin >> n >> m >> q;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cin >> a[i][j];// 初始化差分矩陣：將每個元素視為對單點的插入insert(i, j, i, j, a[i][j]);}}while (q--) {int x1, y1, x2, y2, c;cin >> x1 >> y1 >> x2 >> y2 >> c;insert(x1, y1, x2, y2, c); // 應用子矩陣修改}// 計算二維前綴和得到最終矩陣for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];cout << diff[i][j] << " ";}cout << endl;}return 0;
}

五、單調棧

// 版本一
class Solution {
public:vector<int> dailyTemperatures(vector<int>& T) {// 遞增棧stack<int> st;vector<int> result(T.size(), 0);st.push(0);for (int i = 1; i < T.size(); i++) {if (T[i] < T[st.top()]) {                       // 情況一st.push(i);} else if (T[i] == T[st.top()]) {               // 情況二st.push(i);} else {while (!st.empty() && T[i] > T[st.top()]) { // 情況三result[st.top()] = i - st.top();st.pop();}st.push(i);}}return result;}
};

// 版本二
class Solution {
public:vector<int> dailyTemperatures(vector<int>& T) {stack<int> st; // 遞增棧vector<int> result(T.size(), 0);for (int i = 0; i < T.size(); i++) {while (!st.empty() && T[i] > T[st.top()]) { // 注意棧不能為空result[st.top()] = i - st.top();st.pop();}st.push(i);}return result;}
};

六、st表

用于多次查詢區間中最大值或者最小值

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;const int MAXN = 1e5 + 5;
const int LOGN = 20;  // 覆蓋2^20的區間長度int st[MAXN][LOGN];   // ST表存儲最大值
int log_table[MAXN];   // 預處理log2向下取整// 預處理log_table數組
void init_log(int n) {log_table[1] = 0;for (int i = 2; i <= n; i++) log_table[i] = log_table[i/2] + 1;
}// 構建ST表
void build_st(const vector<int>& arr) {int n = arr.size();for (int i = 0; i < n; i++)st[i][0] = arr[i];  // 初始化長度為1的區間for (int j = 1; (1 << j) <= n; j++) {for (int i = 0; i + (1 << j) - 1 < n; i++) {int prev = 1 << (j-1);st[i][j] = max(st[i][j-1], st[i + prev][j-1]);}}
}// 查詢區間[l, r]的最大值
int query_max(int l, int r) {int k = log_table[r - l + 1];return max(st[l][k], st[r - (1 << k) + 1][k]);
}int main() {int n, q;cout << "輸入數組長度和查詢次數: ";cin >> n >> q;vector<int> arr(n);cout << "輸入數組元素: ";for (int i = 0; i < n; i++) cin >> arr[i];init_log(n);     // 初始化log表build_st(arr);   // 構建ST表while (q--) {int l, r;cout << "輸入查詢區間[l, r] (0-based): ";cin >> l >> r;if (l > r) swap(l, r);cout << "最大值: " << query_max(l, r) << endl;}return 0;
}

七、樹狀數組

動態求區間和

#include <bits/stdc++.h>
using namespace std;int n, m;           // 數據數量和操作次數
int tree[2000010];  // 樹狀數組（大小通常開2*n）// 核心函數：獲取數字二進制表示中最低位的1對應的值
int lowbit(int k) {return k & -k;  // 例如：k=6(110), lowbit(k)=2(10)
}// 單點更新：在位置x處增加k
void add(int x, int k) {while (x <= n) {          // 從葉子節點向上更新tree[x] += k;         // 更新當前節點x += lowbit(x);       // 跳轉到父節點（x += 最低位的1）}
}// 前綴和查詢：計算[1, x]的區間和
int sum(int x) {int ans = 0;while (x != 0) {          // 從右往左累加區間塊ans += tree[x];       // 累加當前節點值x -= lowbit(x);       // 跳轉到前驅節點（x -= 最低位的1）}return ans;
}int main() {cin >> n >> m;// 初始化樹狀數組（等效于逐個插入元素）for (int i = 1; i <= n; i++) {int a;scanf("%d", &a);add(i, a);  // 將初始值插入樹狀數組}// 處理操作for (int i = 1; i <= m; i++) {int a, b, c;scanf("%d%d%d", &a, &b, &c);if (a == 1) {add(b, c);  // 在位置b處加c} else if (a == 2) {// 區間和 = [1,c]的和 - [1,b-1]的和cout << sum(c) - sum(b - 1) << endl;}}
}

• 八、字符串哈希

• 原理：選擇兩個大素數作為基數（Base）和模數（MOD），計算哈希值后取模。
• 公式：
  hash[i]=(hash[i?1]×Base+str[i])mod??MODhash[i]=(hash[i?1]×Base+str[i])modMOD
  例如，Base=13，MOD=101時，字符串"abc"的哈希值為97?
• 優點：沖突概率較低，適合多數場景。

• #include<bits/stdc++.h>
  using namespace std;
  int n;
  const int base=131;
  long long mod=19260817;
  vector<int> hashnum;
  long long myhash(string s){int n=s.size();long long minhash;for(int i=0;i<n;i++){minhash=minhash*base+s[i]%mod;}return minhash;
  }
  int main(){cin>>n;hashnum.resize(n);for(int i=0;i<n;i++){string s;cin>>s;hashnum[i]=myhash(s);}sort(hashnum.begin(),hashnum.end());int ans=0;for(int i=0;i<n;i++){if(hashnum[i]!=hashnum[i-1]){ans++;}}cout<<ans;return 0;
  }

• #include <iostream>
  #include <string>
  #include <vector>
  using namespace std;class StringHash {
  private:static const int Base = 131;       // 推薦的大素數，減少哈希沖突static const int MOD = 1e9 + 7;    // 大素數模數vector<long long> hash;             // 前綴哈希數組vector<long long> p;               // Base的冪次數組
  public:// 初始化哈希數組和冪次數組void init(const string &s) {int n = s.size();hash.resize(n + 1, 0);p.resize(n + 1, 1);for (int i = 1; i <= n; ++i) {p[i] = (p[i-1] * Base) % MOD;         // 計算Base^i % MODhash[i] = (hash[i-1] * Base + s[i-1]) % MOD;  // 前綴哈希計算}}// 獲取子串s[l..r)的哈希值（左閉右開區間）long long getHash(int l, int r) {if (l >= r) return 0;long long res = (hash[r] - hash[l] * p[r - l]) % MOD;return res < 0 ? res + MOD : res;         // 處理負數結果}
  };int main() {string s = "abcabc";StringHash sh;sh.init(s);// 示例：查詢子串哈希cout << "子串 [0,3) 的哈希值: " << sh.getHash(0, 3) << endl;  // abccout << "子串 [3,6) 的哈希值: " << sh.getHash(3, 6) << endl;  // abc// 判斷兩個子串是否相等if (sh.getHash(0, 3) == sh.getHash(3, 6)) {cout << "子串 abc 和 abc 哈希相等" << endl;}return 0;
  }

  九、圖論

????????拓補排序?

vector<int> topologicalSort(int n, vector<vector<int>>& edges) {vector<vector<int>> adj(n + 1);  // 鄰接表（節點編號從1開始）vector<int> inDegree(n + 1, 0);  // 入度數組vector<int> result;              // 拓撲序列// 1. 建圖并統計入度for (auto& e : edges) {int u = e[0], v = e[1];adj[u].push_back(v);inDegree[v]++;}// 2. 初始化隊列（入度為0的節點）queue<int> q;for (int i = 1; i <= n; i++) {if (inDegree[i] == 0) q.push(i);}// 3. BFS處理拓撲排序while (!q.empty()) {int u = q.front();q.pop();result.push_back(u);for (int v : adj[u]) {inDegree[v]--;if (inDegree[v] == 0) q.push(v);}}// 4. 檢測環：若結果長度≠節點數，說明存在環if (result.size() != n) return {};return result;
}

????????Floyd

#include <bits/stdc++.h>
using namespace std;const int N = 405;
const int INF = 0x3f3f3f3f; // 避免INT_MAX溢出
int graph[N][N];
int n, m, q;int main() {// 初始化鄰接矩陣memset(graph, 0x3f, sizeof(graph)); // 快速初始化為INFcin >> n >> m >> q;for(int i=1; i<=n; i++) graph[i][i] = 0;// 輸入邊while(m--){int u, v, w;cin >> u >> v >> w;if(w < graph[u][v]){ // 處理重復邊graph[u][v] = w;graph[v][u] = w; // 無向圖}}// Floyd-Warshall算法for(int k=1; k<=n; k++){for(int i=1; i<=n; i++){for(int j=1; j<=n; j++){if(graph[i][k] != INF && graph[k][j] != INF){graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);}}}}// 查詢while(q--){int st, ed;cin >> st >> ed;cout << (graph[st][ed] == INF ? -1 : graph[st][ed]) << '\n';}return 0;
}

dijistra

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10, INF = 0x3f3f3f3f;int n, m, s;        // 點數、邊數、起點
int h[N], e[N], w[N], ne[N], idx;  // 鄰接表存圖
int dist[N];        // 存儲最短距離
bool vis[N];         // 標記是否已確定最短路徑void add(int a, int b, int c) {e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}void dijkstra() {memset(dist, 0x3f, sizeof dist);dist[s] = 0;priority_queue<PII, vector<PII>, greater<PII>> heap;heap.push({0, s});while (!heap.empty()) {auto t = heap.top();heap.pop();int ver = t.second, distance = t.first;if (vis[ver]) continue;  // 已確定最短路徑則跳過vis[ver] = true;// 遍歷鄰接點更新距離for (int i = h[ver]; i != -1; i = ne[i]) {int j = e[i];if (dist[j] > distance + w[i]) {dist[j] = distance + w[i];heap.push({dist[j], j});}}}
}
int main() {memset(h, -1, sizeof h);cin >> n >> m >> s;while (m--) {int a, b, c;cin >> a >> b >> c;add(a, b, c);  // 有向圖，無向圖需反向添加}dijkstra();for (int i = 1; i <= n; i++) cout << (dist[i] == INF ? -1 : dist[i]) << " ";return 0;
}

最小生成樹?

prim找距離最小的點

#include<iostream>
#include<vector>
#include <climits>using namespace std;
int main() {int v, e;int x, y, k;cin >> v >> e;// 填一個默認最大值，題目描述val最大為10000vector<vector<int>> grid(v + 1, vector<int>(v + 1, 10001));while (e--) {cin >> x >> y >> k;// 因為是雙向圖，所以兩個方向都要填上grid[x][y] = k;grid[y][x] = k;}// 所有節點到最小生成樹的最小距離vector<int> minDist(v + 1, 10001);// 這個節點是否在樹里vector<bool> isInTree(v + 1, false);// 我們只需要循環 n-1次，建立 n - 1條邊，就可以把n個節點的圖連在一起for (int i = 1; i < v; i++) {// 1、prim三部曲，第一步：選距離生成樹最近節點int cur = -1; // 選中哪個節點 加入最小生成樹int minVal = INT_MAX;for (int j = 1; j <= v; j++) { // 1 - v，頂點編號，這里下標從1開始//  選取最小生成樹節點的條件：//  （1）不在最小生成樹里//  （2）距離最小生成樹最近的節點if (!isInTree[j] &&  minDist[j] < minVal) {minVal = minDist[j];cur = j;}}// 2、prim三部曲，第二步：最近節點（cur）加入生成樹isInTree[cur] = true;// 3、prim三部曲，第三步：更新非生成樹節點到生成樹的距離（即更新minDist數組）// cur節點加入之后， 最小生成樹加入了新的節點，那么所有節點到 最小生成樹的距離（即minDist數組）需要更新一下// 由于cur節點是新加入到最小生成樹，那么只需要關心與 cur 相連的 非生成樹節點 的距離 是否比 原來 非生成樹節點到生成樹節點的距離更小了呢for (int j = 1; j <= v; j++) {// 更新的條件：// （1）節點是 非生成樹里的節點// （2）與cur相連的某節點的權值 比 該某節點距離最小生成樹的距離小// 很多錄友看到自己 就想不明白什么意思，其實就是 cur 是新加入 最小生成樹的節點，那么 所有非生成樹的節點距離生成樹節點的最近距離 由于 cur的新加入，需要更新一下數據了if (!isInTree[j] && grid[cur][j] < minDist[j]) {minDist[j] = grid[cur][j];}}}// 統計結果int result = 0;for (int i = 2; i <= v; i++) { // 不計第一個頂點，因為統計的是邊的權值，v個節點有 v-1條邊result += minDist[i];}cout << result << endl;}

kruskal找最短邊

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;// l,r為 邊兩邊的節點，val為邊的數值
struct Edge {int l, r, val;
};// 節點數量
int n = 10001;
// 并查集標記節點關系的數組
vector<int> father(n, -1); // 節點編號是從1開始的，n要大一些// 并查集初始化
void init() {for (int i = 0; i < n; ++i) {father[i] = i;}
}// 并查集的查找操作
int find(int u) {return u == father[u] ? u : father[u] = find(father[u]); // 路徑壓縮
}// 并查集的加入集合
void join(int u, int v) {u = find(u); // 尋找u的根v = find(v); // 尋找v的根if (u == v) return ; // 如果發現根相同，則說明在一個集合，不用兩個節點相連直接返回father[v] = u;
}int main() {int v, e;int v1, v2, val;vector<Edge> edges;int result_val = 0;cin >> v >> e;while (e--) {cin >> v1 >> v2 >> val;edges.push_back({v1, v2, val});}// 執行Kruskal算法// 按邊的權值對邊進行從小到大排序sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {return a.val < b.val;});// 并查集初始化init();// 從頭開始遍歷邊for (Edge edge : edges) {// 并查集，搜出兩個節點的祖先int x = find(edge.l);int y = find(edge.r);// 如果祖先不同，則不在同一個集合if (x != y) {result_val += edge.val; // 這條邊可以作為生成樹的邊join(x, y); // 兩個節點加入到同一個集合}}cout << result_val << endl;return 0;
}

BF?

#include <iostream>
#include <vector>
#include <list>
#include <climits>
using namespace std;int main() {int n, m, p1, p2, val;cin >> n >> m;vector<vector<int>> grid;// 將所有邊保存起來for(int i = 0; i < m; i++){cin >> p1 >> p2 >> val;// p1 指向 p2，權值為 valgrid.push_back({p1, p2, val});}int start = 1;  // 起點int end = n;    // 終點vector<int> minDist(n + 1 , INT_MAX);minDist[start] = 0;for (int i = 1; i < n; i++) { // 對所有邊 松弛 n-1 次for (vector<int> &side : grid) { // 每一次松弛，都是對所有邊進行松弛int from = side[0]; // 邊的出發點int to = side[1]; // 邊的到達點int price = side[2]; // 邊的權值// 松弛操作 // minDist[from] != INT_MAX 防止從未計算過的節點出發if (minDist[from] != INT_MAX && minDist[to] > minDist[from] + price) { minDist[to] = minDist[from] + price;  }}}if (minDist[end] == INT_MAX) cout << "unconnected" << endl; // 不能到達終點else cout << minDist[end] << endl; // 到達終點最短路徑}

SPFA?

#include <cstring>
#include <queue>
using namespace std;const int MAXN = 1e5 + 5;  // 根據題目調整最大節點數
const int INF = 0x3f3f3f3f; // 表示無窮大struct Edge {int v;  // 目標節點int w;  // 邊權
};vector<Edge> e[MAXN];  // 鄰接表存圖
int dis[MAXN];         // 起點到各點的最短距離
int cnt[MAXN];         // 記錄到某節點的最短路邊數（用于負環檢測）
bool vis[MAXN];        // 標記節點是否在隊列中// SPFA 主函數
// 返回值: true=無負環，false=存在負環
// 參數: n=總節點數，s=起點
bool spfa(int n, int s) {// 初始化距離和隊列memset(dis, 0x3f, sizeof(dis));  // 初始化為INFmemset(cnt, 0, sizeof(cnt));memset(vis, 0, sizeof(vis));queue<int> q;dis[s] = 0;q.push(s);vis[s] = true;while (!q.empty()) {int u = q.front();q.pop();vis[u] = false;  // 出隊后取消標記// 遍歷所有鄰接邊for (auto &ed : e[u]) {int v = ed.v, w = ed.w;// 松弛操作：嘗試縮短 dis[v]if (dis[v] > dis[u] + w) {dis[v] = dis[u] + w;cnt[v] = cnt[u] + 1;  // 更新路徑邊數// 存在負環的判定條件if (cnt[v] >= n) return false;// 若v不在隊列中，則入隊if (!vis[v]) {q.push(v);vis[v] = true;}}}}return true;  // 未發現負環
}

十、動態規劃

LCS最長公共子序列

// 計算LCS長度
int lengthOfLCS(string s1, string s2) {int m = s1.size(), n = s2.size();vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (s1[i] == s2[j]) {dp[i + 1][j + 1] = dp[i][j] + 1;} else {dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);}}}return dp[m][n];
}// 輸出一個具體的LCS序列
string getLCS(string s1, string s2) {int m = s1.size(), n = s2.size();vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (s1[i] == s2[j]) {dp[i + 1][j + 1] = dp[i][j] + 1;} else {dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);}}}string lcs;int i = m, j = n;while (i > 0 && j > 0) {if (s1[i - 1] == s2[j - 1]) {lcs.push_back(s1[i - 1]);i--, j--;} else if (dp[i - 1][j] > dp[i][j - 1]) {i--;} else {j--;}}reverse(lcs.begin(), lcs.end());return lcs;
}

LIS最長上升子序列

/ 計算LIS長度
int lengthOfLIS_DP(vector<int>& nums) {int n = nums.size();vector<int> dp(n, 1);int max_len = 1;for (int i = 0; i < n; ++i) {for (int j = 0; j < i; ++j) {if (nums[j] < nums[i]) {dp[i] = max(dp[i], dp[j] + 1);}}max_len = max(max_len, dp[i]);}return max_len;
}// 輸出一個具體的LIS序列
vector<int> getLIS(vector<int>& nums) {int n = nums.size();vector<int> dp(n, 1), prev(n, -1);int max_len = 1, end_idx = 0;for (int i = 0; i < n; ++i) {for (int j = 0; j < i; ++j) {if (nums[j] < nums[i] && dp[i] < dp[j] + 1) {dp[i] = dp[j] + 1;prev[i] = j;}}if (dp[i] > max_len) {max_len = dp[i];end_idx = i;}}vector<int> lis;while (end_idx != -1) {lis.push_back(nums[end_idx]);end_idx = prev[end_idx];}reverse(lis.begin(), lis.end());return lis;
}

1. 01背包問題

特點：每件物品只能選或不選（0或1次）。

二維數組模板（時間復雜度O(NV)，空間復雜度O(NV)）

int dp[N][V]; // N為物品數，V為背包容量
for (int i = 1; i <= n; i++) {int w = weight[i], v = value[i];for (int j = 0; j <= V; j++) {if (j < w) dp[i][j] = dp[i-1][j];else dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v);}
}
// 結果：dp[n][V]

關鍵點：狀態從上一行（i-1）轉移而來。

一維數組優化（空間復雜度O(V)）

int dp[V+1] = {0};
for (int i = 1; i <= n; i++) {int w = weight[i], v = value[i];for (int j = V; j >= w; j--) { // 逆序遍歷防止覆蓋dp[j] = max(dp[j], dp[j-w] + v);}
}
// 結果：dp[V]

關鍵點：逆序更新確保每個物品僅被計算一次。

2. 完全背包問題

特點：每件物品可選無限次。

二維數組模板

int dp[N][V];
for (int i = 1; i <= n; i++) {int w = weight[i], v = value[i];for (int j = 0; j <= V; j++) {if (j < w) dp[i][j] = dp[i-1][j];else dp[i][j] = max(dp[i-1][j], dp[i][j-w] + v); // 區別：當前行轉移}
}
// 結果：dp[n][V]

關鍵點：狀態從當前行轉移，允許重復選擇。

一維數組優化

int dp[V+1] = {0};
for (int i = 1; i <= n; i++) {int w = weight[i], v = value[i];for (int j = w; j <= V; j++) { // 正序遍歷允許重復dp[j] = max(dp[j], dp[j-w] + v);}
}
// 結果：dp[V]

關鍵點：正序更新允許多次選擇同一物品。

3. 多重背包問題

特點：第i種物品最多選s[i]次。

二維數組模板（樸素版）

int dp[N][V];
for (int i = 1; i <= n; i++) {int w = weight[i], v = value[i], s = cnt[i];for (int j = 0; j <= V; j++) {dp[i][j] = dp[i-1][j];for (int k = 1; k <= s && k*w <= j; k++) {dp[i][j] = max(dp[i][j], dp[i-1][j-k*w] + k*v);}}
}
// 結果：dp[n][V]

關鍵點：三層循環遍歷物品、容量和選取次數。

一維數組優化（二進制拆分）

#include <iostream>
#include <vector>
using namespace std;int main() {int N, W;cin >> N >> W;vector<int> dp(W + 1, 0);vector<pair<int, int>> items;  // 存儲拆分后的物品（重量，價值）for (int i = 0; i < N; i++) {int w, v, s;cin >> w >> v >> s;// 二進制拆分int k = 1;while (k <= s) {items.push_back({w * k, v * k});s -= k;k *= 2;}if (s > 0) {items.push_back({w * s, v * s});}}// 01 背包動態規劃for (auto &item : items) {int w = item.first, v = item.second;for (int j = W; j >= w; j--) {dp[j] = max(dp[j], dp[j - w] + v);}}cout << dp[W] << endl;return 0;
}

關鍵點：通過二進制拆分將問題轉化為01背包，降低復雜度

十一、二分查找

while(l<r)

盡量向左找目標//在a數組中尋找第一個>=x的數，并返回其下標
int bsearch_1(int l, int r)
{while (l < r){int mid = l + r >> 1;//或寫成(l+r)/2if (a[mid]>=x) r = mid;else l = mid + 1;}return l;//因為while循環當l==r時終止，return r也可以
}

盡量向右找目標//在a數組中尋找最后一個<=x的數，并返回其下標
int bsearch_2(int l, int r)
{while (l < r){int mid = l + r + 1 >> 1;//或寫成(l+r+1)/2if (a[mid]<=x) l = mid;else r = mid - 1;}return l;//因為while循環當l==r時終止，return r也可以
}

#include <iostream>
// 邊長數組，這樣我們就不用擔心數據裝不下了
#include <vector>
using namespace std;
vector<int > vec;
int main() {int n, m;int t;cin >> n >> m;int index;// 向數組尾部放入數據，因為這個特性，vector也可以當成stack用while(n--) cin >> t, vec.push_back(t);while(m--) {cin >> t;// 在序列里查找目標數據index = lower_bound(vec.begin(), vec.end(), t) - vec.begin();// 如果目標數據找到了，輸出答案，注意我們的數組下標是從0開始的if (t == vec[index]) cout << index + 1 << ' ';// 沒找到記得輸出-1哦else cout << -1 << ' ';}return 0;

1. 核心功能差異

函數	返回值條件（升序序列）	返回值條件（降序序列）	示例（升序序列?{1,3,4,4,6}）
lower_bound	第一個≥目標值的元素位置	第一個≤目標值的元素位置	lower_bound(4)?→ 指向第一個4（索引2）
upper_bound	第一個>目標值的元素位置	第一個<目標值的元素位置	upper_bound(4)?→ 指向6（索引4）

關鍵點：

• 升序時：lower_bound?包含等于，upper_bound?排除等于。
• 降序時：需通過比較函數（如?greater<int>()）反轉邏輯，此時?lower_bound?尋找第一個小于等于的元素，upper_bound?尋找第一個小于的元素 。

#include <iostream>
using namespace std;const int N = 100010;int n, q;
int a[N];// 查找左邊界：第一個等于x的位置
int find_left(int x) {int l = 0, r = n - 1;while (l <= r) {int mid = (l + r) >> 1;if (a[mid] >= x) r = mid - 1; // 向左逼近else l = mid + 1;}// 檢查是否找到return (l < n && a[l] == x) ? l : -1;
}// 查找右邊界：最后一個等于x的位置
int find_right(int x) {int l = 0, r = n - 1;while (l <= r) {int mid = (l + r) >> 1;if (a[mid] <= x) l = mid + 1; // 向右逼近else r = mid - 1;}// 檢查是否找到return (r >= 0 && a[r] == x) ? r : -1;
}

一、l <= r?模板（左閉右閉區間）

1.?適用場景

• 精確查找目標值是否存在
• 尋找第一個滿足條件的元素（如第一個錯誤版本）
• 適用于明確閉區間?[left, right]?的情況，確保所有元素都被覆蓋 。

2.?代碼模板

int binarySearch(vector<int>& nums, int target) {int l = 0, r = nums.size() - 1;  // 閉區間初始化while (l <= r) {                 // 終止條件：l > rint mid = l + (r - l) / 2;   // 防溢出寫法if (nums[mid] == target) {return mid;              // 找到目標值} else if (nums[mid] < target) {l = mid + 1;            // 目標在右半區間} else {r = mid - 1;            // 目標在左半區間}}return -1;                       // 未找到
}

3.?特點

• 循環條件：l <= r?確保所有元素被檢查，包括?l == r?的情況 。
• 邊界更新：每次嚴格縮小范圍，避免死循環。
• 典型應用：基礎二分查找（如 LeetCode 704）。

二、l < r?模板（左閉右開區間）

1.?適用場景

• 尋找插入位置（如?lower_bound?/?upper_bound）
• 處理邊界問題（如第一個/最后一個滿足條件的元素）
• 適用于左閉右開區間?[left, right)，常用于迭代器或數組尾部。
  ?

2.?代碼模板

// 尋找第一個 >= target 的位置（lower_bound）
int lowerBound(vector<int>& nums, int target) {int l = 0, r = nums.size();      // 右開區間初始化while (l < r) {                  // 終止條件：l == rint mid = l + (r - l) / 2;   // 防溢出寫法if (nums[mid] >= target) {r = mid;                // 目標在左半區間（包含 mid）} else {l = mid + 1;            // 目標在右半區間（排除 mid）}}return l;                        // 若未找到，返回插入位置
}// 尋找第一個 > target 的位置（upper_bound）
int upperBound(vector<int>& nums, int target) {int l = 0, r = nums.size();while (l < r) {int mid = l + (r - l) / 2;if (nums[mid] > target) {r = mid;} else {l = mid + 1;}}return l;  // 返回插入位置（最后一個等于 target 的下一個位置）
}

3.?特點

• 循環條件：l < r?確保區間范圍逐步縮小，最終?l == r。
• 邊界更新：右邊界?r?不包含在搜索范圍內，需注意最終結果的驗證（如?nums[l]?是否等于目標值）。
• 典型應用：查找插入位置（LeetCode 35）或重復元素的邊界 。
  ?

三、核心區別與選擇原則

特性	l <= r（閉區間）	l < r（左閉右開）
初始區間	[0, n-1]	[0, n)
終止條件	l > r（所有元素已檢查）	l == r（區間為空）
更新邏輯	mid ± 1?嚴格縮小范圍	r = mid?或?l = mid + 1
適用場景	精確查找、存在性判斷	邊界查找、插入位置、重復元素處理
防溢出寫法	mid = l + (r - l) / 2	同上

十三、高精度

加法：

#include <vector>
#include <string>
using namespace std;vector<int> add(vector<int>& A, vector<int>& B) {if (A.size() < B.size()) return add(B, A); // 保證A位數≥Bvector<int> C;int t = 0; // 進位for (int i = 0; i < A.size(); i++) {t += A[i];if (i < B.size()) t += B[i];C.push_back(t % 10);t /= 10;}if (t) C.push_back(t);return C;
}// 調用示例
string a = "999999999", b = "1";
vector<int> A, B;
for (int i = a.size()-1; i >= 0; i--) A.push_back(a[i]-'0');
for (int i = b.size()-1; i >= 0; i--) B.push_back(b[i]-'0');
vector<int> C = add(A, B);
// 逆序輸出結果：for (int i = C.size()-1; i >= 0; i--) cout << C[i];

減法：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=505;
vector<int> a, b;// 修正比較函數：判斷a是否>=b
bool cmp(vector<int>& x, vector<int>& y) { // 添加引用避免拷貝if (x.size() != y.size()) return x.size() > y.size();for (int i = x.size()-1; i >= 0; i--) {if (x[i] != y[i]) return x[i] > y[i];}return true;
}// 修正減法函數：使用參數y的數據
vector<int> sub(vector<int>& x, vector<int>& y) { // 添加引用避免拷貝vector<int> c;for (int i = 0, t = 0; i < x.size(); i++) {t = x[i] - t;if (i < y.size()) t -= y[i]; // 正確使用y[i]c.push_back((t + 10) % 10);t = (t < 0) ? 1 : 0;}while (c.size() > 1 && c.back() == 0) c.pop_back();return c;
}int main() {string s1, s2;cin >> s1 >> s2;for (int i = s1.size()-1; i >= 0; i--) a.push_back(s1[i]-'0');for (int i = s2.size()-1; i >= 0; i--) b.push_back(s2[i]-'0');vector<int> c;if (cmp(a, b)) {c = sub(a, b);} else {cout << "-"; // 處理負號c = sub(b, a);}for (int i = c.size()-1; i >= 0; i--) cout << c[i];return 0;
}

乘法：

#include <bits/stdc++.h>
using namespace std;vector<int> mul(vector<int>& x, vector<int>& y) {vector<int> c(x.size() + y.size(), 0);for (int i = 0; i < x.size(); i++)for (int j = 0; j < y.size(); j++)c[i + j] += x[i] * y[j];int carry = 0;for (int i = 0; i < c.size(); i++) {c[i] += carry;carry = c[i] / 10;c[i] %= 10;}while (c.size() > 1 && c.back() == 0) c.pop_back();return c;
}int main() {string s1, s2;cin >> s1 >> s2;vector<int> a, b;// 逆序存儲，個位在前for (int i = s1.size()-1; i >=0; i--) a.push_back(s1[i] - '0');for (int i = s2.size()-1; i >=0; i--) b.push_back(s2[i] - '0');vector<int> c = mul(a, b);// 逆序輸出for (int i = c.size()-1; i >=0; i--) cout << c[i];return 0;
}

十四、取消同步流

ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//取消同步流