本文最后更新于191 天前，其中的信息可能已经过时，如有错误请发送邮件到898599301@qq.com
🤖ACM算法整理
ACM 竞赛中 C++ 中常用的算法模板、输入输出控制、字符串方法、STL 容器以及 algorithm 库的使用示例。
重要提示：
- 以下代码示例旨在提供一个基本模板，你可能需要根据具体题目要求（如数据类型、数组大小、图的表示方式等）进行调整。
- 在实际竞赛中，通常会在文件开头加入
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);来加速输入输出。 #include <bits/stdc++.h>在多数 OJ 上都是可用的，可以包含大部分常用库，但正式学习和代码提交时建议按需包含具体头文件。
1. 常用算法模型模板
1.1 排序：快速排序 (QuickSort)
一种高效的基于分治的排序算法。平均时间复杂度 $O(N \log N)$，最坏 $O(N^2)$。
#include <vector>
#include <algorithm> // for std::swap
// 快速排序模板
void quickSort(std::vector<int>& arr, int low, int high) {
if (low < high) {
int pivot = arr[high]; // 选择最后一个元素作为枢轴
int i = (low - 1); // 小于枢轴的元素区域的结束索引
for (int j = low; j <= high - 1; j++) {
// 如果当前元素小于或等于枢轴
if (arr[j] <= pivot) {
i++; // 增加小于枢轴的元素区域的结束索引
std::swap(arr[i], arr[j]);
}
}
std::swap(arr[i + 1], arr[high]); // 将枢轴放到正确的位置
int pi = i + 1; // 枢轴的最终位置
// 递归排序枢轴左右两边的子数组
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// 示例调用：
// std::vector<int> myVec = {10, 7, 8, 9, 1, 5};
// quickSort(myVec, 0, myVec.size() - 1);1.2 搜索：二分查找 (Binary Search)
适用于已排序数组中查找特定元素。时间复杂度 $O(\log N)$。
#include <vector>
// 二分查找模板 (查找是否存在)
bool binarySearch(const std::vector<int>& arr, int target) {
int low = 0;
int high = arr.size() - 1;
while (low <= high) {
int mid = low + (high - low) / 2; // 防止溢出
if (arr[mid] == target) {
return true; // 找到目标
} else if (arr[mid] < target) {
low = mid + 1; // 目标在右半部分
} else {
high = mid - 1; // 目标在左半部分
}
}
return false; // 未找到目标
}
// 二分查找模板 (查找第一个等于或大于target的元素索引，即lower_bound)
int lowerBound(const std::vector<int>& arr, int target) {
int low = 0;
int high = arr.size(); // 注意这里 high 的初始值是 arr.size()
int ans = arr.size(); // 结果，如果没有找到，就是 arr.size()
while (low < high) {
int mid = low + (high - low) / 2;
if (arr[mid] >= target) {
ans = mid;
high = mid; // 尝试在左半部分找到更小的索引
} else {
low = mid + 1;
}
}
return ans;
}
// 二分查找模板 (查找第一个大于target的元素索引，即upper_bound)
int upperBound(const std::vector<int>& arr, int target) {
int low = 0;
int high = arr.size();
int ans = arr.size();
while (low < high) {
int mid = low + (high - low) / 2;
if (arr[mid] > target) {
ans = mid;
high = mid;
} else {
low = mid + 1; // 目标在右半部分（包括 mid）
}
}
return ans;
}1.3 图论：广度优先搜索 (BFS)
用于遍历或搜索图的算法。常用于查找最短路径（无权图）或层级遍历。
#include <vector>
#include <queue>
#include <iostream>
// 图的邻接表表示
std::vector<std::vector<int>> adj;
std::vector<bool> visited;
std::vector<int> dist; // 记录距离（对于无权图的最短路径）
void bfs(int start_node, int num_nodes) {
visited.assign(num_nodes + 1, false); // 根据节点编号范围调整大小
dist.assign(num_nodes + 1, -1); // 初始化距离为-1（未访问）
std::queue<int> q;
q.push(start_node);
visited[start_node] = true;
dist[start_node] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
// 可以在这里处理节点 u，比如打印
// std::cout << "Visiting node: " << u << " (distance: " << dist[u] << ")\n";
for (int v : adj[u]) {
if (!visited[v]) {
visited[v] = true;
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
}
/*
// 示例使用
int main() {
int n = 5; // 节点数量
adj.resize(n + 1);
// 添加边
adj[1].push_back(2); adj[2].push_back(1);
adj[1].push_back(3); adj[3].push_back(1);
adj[2].push_back(4); adj[4].push_back(2);
adj[3].push_back(5); adj[5].push_back(3);
bfs(1, n);
for (int i = 1; i <= n; ++i) {
std::cout << "Distance from node 1 to node " << i << ": " << dist[i] << std::endl;
}
return 0;
}
*/1.4 图论：深度优先搜索 (DFS)
用于遍历或搜索图的算法。常用于连通性、环检测、拓扑排序等。
#include <vector>
#include <iostream>
// 图的邻接表表示
std::vector<std::vector<int>> adj_dfs;
std::vector<bool> visited_dfs;
void dfs(int u) {
visited_dfs[u] = true;
// std::cout << "Visiting node: " << u << std::endl; // 在这里处理节点
for (int v : adj_dfs[u]) {
if (!visited_dfs[v]) {
dfs(v);
}
}
}
/*
// 示例使用
int main() {
int n = 5; // 节点数量
adj_dfs.resize(n + 1);
visited_dfs.assign(n + 1, false);
// 添加边
adj_dfs[1].push_back(2); adj_dfs[2].push_back(1);
adj_dfs[1].push_back(3); adj_dfs[3].push_back(1);
adj_dfs[2].push_back(4); adj_dfs[4].push_back(2);
adj_dfs[3].push_back(5); adj_dfs[5].push_back(3);
dfs(1); // 从节点1开始DFS
// 检查所有节点是否都被访问
for (int i = 1; i <= n; ++i) {
if (!visited_dfs[i]) {
std::cout << "Node " << i << " is not reachable from node 1\n";
}
}
return 0;
}
*/1.5 动态规划：背包问题 (0/1 背包)
有 N 件物品和一个容量为 V 的背包。第 i 件物品的重量是 w[i]，价值是 v[i]。每件物品只能用一次，问在不超过背包容量的前提下，背包中物品的最大总价值。
#include <vector>
#include <algorithm> // for std::max
// 0/1 背包问题模板
// W: 背包容量
// weights: 物品重量数组
// values: 物品价值数组
// n: 物品数量
int knapsack01(int W, const std::vector<int>& weights, const std::vector<int>& values, int n) {
// dp[j] 表示容量为 j 时的最大价值
// 使用一维数组进行空间优化，j 从大到小遍历
std::vector<int> dp(W + 1, 0);
for (int i = 0; i < n; ++i) { // 遍历物品
for (int j = W; j >= weights[i]; --j) { // 遍历背包容量，从大到小
dp[j] = std::max(dp[j], dp[j - weights[i]] + values[i]);
}
}
return dp[W];
}
/*
// 示例使用
int main() {
int W = 10;
std::vector<int> weights = {2, 3, 4, 5};
std::vector<int> values = {3, 4, 5, 6};
int n = weights.size();
int max_value = knapsack01(W, weights, values, n);
std::cout << "Max value for 0/1 knapsack: " << max_value << std::endl; // Output: 7 (items with weights 2 and 5)
return 0;
}
*/1.6 动态规划：最长公共子序列 (LCS)
给定两个序列，找到它们之间最长的公共子序列的长度。
#include <string>
#include <vector>
#include <algorithm> // for std::max
#include <iostream>
// LCS 模板 (返回长度)
int longestCommonSubsequence(const std::string& text1, const std::string& text2) {
int m = text1.length();
int n = text2.length();
// dp[i][j] 表示 text1 的前 i 个字符和 text2 的前 j 个字符的最长公共子序列的长度
std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (text1[i - 1] == text2[j - 1]) {
dp[i][j] = 1 + dp[i - 1][j - 1];
} else {
dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
/*
// 示例使用
int main() {
std::string s1 = "abcde";
std::string s2 = "ace";
std::cout << "LCS length: " << longestCommonSubsequence(s1, s2) << std::endl; // Output: 3
return 0;
}
*/1.7 动态规划：最长递增子序列 (LIS)
给定一个无序的整数数组，找到其中最长递增子序列的长度。
#include <vector>
#include <algorithm> // for std::max, std::lower_bound
#include <iostream>
// LIS 模板 (O(N^2) 时间复杂度)
int longestIncreasingSubsequence_N2(const std::vector<int>& nums) {
if (nums.empty()) {
return 0;
}
int n = nums.size();
std::vector<int> dp(n, 1); // dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度
int max_len = 1;
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[i] > nums[j]) {
dp[i] = std::max(dp[i], dp[j] + 1);
}
}
max_len = std::max(max_len, dp[i]);
}
return max_len;
}
// LIS 模板 (O(N log N) 时间复杂度)
// tails[k] 存储所有长度为 k+1 的递增子序列中，最小的结尾元素
int longestIncreasingSubsequence_NlogN(const std::vector<int>& nums) {
if (nums.empty()) {
return 0;
}
std::vector<int> tails; // tails 数组是严格递增的
for (int num : nums) {
// 查找第一个大于或等于 num 的元素的位置
auto it = std::lower_bound(tails.begin(), tails.end(), num);
if (it == tails.end()) {
// 如果 num 比所有 tails 元素都大，则可以延长最长递增子序列
tails.push_back(num);
} else {
// 否则，更新 tails 数组中相应位置的元素为 num，
// 这样可以形成一个更小的结尾元素，为后续更长的序列创造机会
*it = num;
}
}
return tails.size();
}
/*
// 示例使用
int main() {
std::vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
std::cout << "LIS length (N^2): " << longestIncreasingSubsequence_N2(nums) << std::endl; // Output: 4 (2, 3, 7, 18 或 2, 5, 7, 18)
std::cout << "LIS length (N log N): " << longestIncreasingSubsequence_NlogN(nums) << std::endl; // Output: 4
return 0;
}
*/1.8 贪心算法 (Greedy Algorithms)
贪心算法没有通用模板，其核心思想是在每一步做出局部最优的选择，并期望这些局部最优解能导致全局最优解。这通常需要证明其正确性。
示例：活动选择问题
给定一组活动，每个活动有开始时间 s_i 和结束时间 f_i。选择最大数量的活动，使得它们两两不重叠。
#include <vector>
#include <algorithm> // for std::sort
#include <utility> // for std::pair
// 活动结构体
struct Activity {
int start;
int end;
};
// 比较函数，按结束时间升序排序
bool compareActivities(const Activity& a, const Activity& b) {
return a.end < b.end;
}
// 贪心算法：活动选择问题
int selectMaxActivities(std::vector<Activity>& activities) {
if (activities.empty()) {
return 0;
}
// 1. 按活动的结束时间进行排序
std::sort(activities.begin(), activities.end(), compareActivities);
int count = 1; // 至少选择第一个活动
int last_finish_time = activities[0].end; // 记录上一个选定活动的结束时间
// 2. 遍历排序后的活动，选择第一个不与上一个活动重叠的活动
for (size_t i = 1; i < activities.size(); ++i) {
if (activities[i].start >= last_finish_time) {
count++;
last_finish_time = activities[i].end;
}
}
return count;
}
/*
// 示例使用
int main() {
std::vector<Activity> activities = {
{1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 9}, {5, 9}, {6, 10}, {8, 11}, {8, 12}, {2, 14}, {12, 16}
};
// 排序后（按结束时间）: {1,4}, {3,5}, {0,6}, {5,7}, {3,9}, {5,9}, {6,10}, {8,11}, {8,12}, {2,14}, {12,16}
// 实际的排序结果依赖于 `std::sort` 的稳定性，但对于此算法不影响正确性
// 最优选择: (1,4), (5,7), (8,11), (12,16) -> 4个
std::cout << "Max activities selected: " << selectMaxActivities(activities) << std::endl; // Output: 4
return 0;
}
*/1.9 图论：最短路径算法
1.9.1 Dijkstra 算法 (迪杰斯特拉)
单源最短路径算法，适用于所有边权为非负的图。时间复杂度 $O(E \log V)$ (使用优先队列)。
#include <vector>
#include <queue>
#include <limits> // for std::numeric_limits
#include <utility> // for std::pair
const int INF = std::numeric_limits<int>::max(); // 无穷大
// 图的邻接表表示: pair<int, int> {目标节点, 边权}
std::vector<std::vector<std::pair<int, int>>> adj_dijkstra;
std::vector<int> dist_dijkstra; // 存储从源点到各点的最短距离
void dijkstra(int start_node, int num_nodes) {
dist_dijkstra.assign(num_nodes + 1, INF);
// 优先队列存储 {距离, 节点}，按距离从小到大排序
// 注意：std::priority_queue 默认是大顶堆，所以要存储 pair<负距离, 节点>
// 或者使用 `greater<std::pair<int, int>>` 来实现小顶堆
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;
dist_dijkstra[start_node] = 0;
pq.push({0, start_node}); // {距离, 节点}
while (!pq.empty()) {
int d = pq.top().first;
int u = pq.top().second;
pq.pop();
// 如果当前取出的距离比已知的最短距离大，则跳过（已经找到更短路径）
if (d > dist_dijkstra[u]) {
continue;
}
for (auto& edge : adj_dijkstra[u]) {
int v = edge.first;
int weight = edge.second;
if (dist_dijkstra[u] + weight < dist_dijkstra[v]) {
dist_dijkstra[v] = dist_dijkstra[u] + weight;
pq.push({dist_dijkstra[v], v});
}
}
}
}
/*
// 示例使用
int main() {
int n = 5; // 节点数量 (1-indexed)
adj_dijkstra.resize(n + 1);
// 添加边: u -> v, weight
adj_dijkstra[1].push_back({2, 10});
adj_dijkstra[1].push_back({3, 3});
adj_dijkstra[2].push_back({3, 1});
adj_dijkstra[2].push_back({4, 2});
adj_dijkstra[3].push_back({2, 4});
adj_dijkstra[3].push_back({4, 8});
adj_dijkstra[3].push_back({5, 2});
adj_dijkstra[4].push_back({5, 7});
dijkstra(1, n);
for (int i = 1; i <= n; ++i) {
if (dist_dijkstra[i] == INF) {
std::cout << "Node " << i << ": Unreachable\n";
} else {
std::cout << "Node " << i << ": " << dist_dijkstra[i] << "\n";
}
}
// Expected output for start_node 1:
// Node 1: 0
// Node 2: 7 (1->3->2: 3+4=7)
// Node 3: 3 (1->3: 3)
// Node 4: 9 (1->3->2->4: 3+4+2=9)
// Node 5: 5 (1->3->5: 3+2=5)
return 0;
}
*/1.9.2 Bellman-Ford 算法 (贝尔曼-福特)
单源最短路径算法，可以处理含有负权边的图，并能检测负权环。时间复杂度 $O(V \cdot E)$。
#include <vector>
#include <limits> // for std::numeric_limits
const int INF_BF = std::numeric_limits<int>::max();
// 边结构体
struct Edge {
int u, v, weight;
};
std::vector<int> dist_bf; // 存储从源点到各点的最短距离
// Bellman-Ford 算法模板
// V: 节点数量
// edges: 边的列表
// start_node: 源节点
// 返回 true 如果没有负权环，false 如果有负权环
bool bellmanFord(int V, const std::vector<Edge>& edges, int start_node) {
dist_bf.assign(V + 1, INF_BF);
dist_bf[start_node] = 0;
// 进行 V-1 轮松弛操作
for (int i = 0; i < V - 1; ++i) {
for (const auto& edge : edges) {
if (dist_bf[edge.u] != INF_BF && dist_bf[edge.u] + edge.weight < dist_bf[edge.v]) {
dist_bf[edge.v] = dist_bf[edge.u] + edge.weight;
}
}
}
// 再次松弛，检测负权环
for (const auto& edge : edges) {
if (dist_bf[edge.u] != INF_BF && dist_bf[edge.u] + edge.weight < dist_bf[edge.v]) {
return false; // 检测到负权环
}
}
return true; // 没有负权环
}
/*
// 示例使用
int main() {
int V = 5; // 节点数量 (1-indexed)
std::vector<Edge> edges = {
{1, 2, 10}, {1, 3, 3},
{2, 3, 1}, {2, 4, 2},
{3, 2, 4}, {3, 4, 8}, {3, 5, 2},
{4, 5, 7}
};
if (bellmanFord(V, edges, 1)) {
for (int i = 1; i <= V; ++i) {
if (dist_bf[i] == INF_BF) {
std::cout << "Node " << i << ": Unreachable\n";
} else {
std::cout << "Node " << i << ": " << dist_bf[i] << "\n";
}
}
} else {
std::cout << "Graph contains negative cycle!\n";
}
// 示例负权环
std::vector<Edge> negative_cycle_edges = {
{1, 2, 1}, {2, 3, -1}, {3, 1, -1}
};
std::cout << "\nTesting negative cycle:\n";
if (bellmanFord(3, negative_cycle_edges, 1)) {
std::cout << "No negative cycle.\n";
} else {
std::cout << "Graph contains negative cycle!\n";
}
return 0;
}
*/1.9.3 Floyd-Warshall 算法 (弗洛伊德-沃沙尔)
全源最短路径算法，可以处理含有负权边的图，但不能检测负权环（只能检测出自身到自身的负距离）。时间复杂度 $O(V^3)$。
#include <vector>
#include <limits> // for std::numeric_limits
#include <algorithm> // for std::min
const long long INF_FW = std::numeric_limits<long long>::max() / 2; // 用 long long 并除以2防止溢出
// Floyd-Warshall 算法模板
// dist[i][j] 存储从 i 到 j 的最短距离
std::vector<std::vector<long long>> dist_fw;
void floydWarshall(int V) {
// 初始化 dist 矩阵：对角线为0，有边为权重，无边为INF
// 假设 dist_fw 已经在外部 resize 并初始化好了
for (int k = 1; k <= V; ++k) { // 中间节点
for (int i = 1; i <= V; ++i) { // 起始节点
for (int j = 1; j <= V; ++j) { // 结束节点
if (dist_fw[i][k] != INF_FW && dist_fw[k][j] != INF_FW) { // 路径存在
dist_fw[i][j] = std::min(dist_fw[i][j], dist_fw[i][k] + dist_fw[k][j]);
}
}
}
}
// 检测负权环 (如果 dist[i][i] < 0)
// for (int i = 1; i <= V; ++i) {
// if (dist_fw[i][i] < 0) {
// // 存在负权环
// }
// }
}
/*
// 示例使用
int main() {
int V = 4; // 节点数量 (1-indexed)
dist_fw.assign(V + 1, std::vector<long long>(V + 1, INF_FW));
// 初始化自身到自身距离为0
for (int i = 1; i <= V; ++i) {
dist_fw[i][i] = 0;
}
// 添加边及权重
dist_fw[1][2] = 3;
dist_fw[1][4] = 7;
dist_fw[2][1] = 8;
dist_fw[2][3] = 2;
dist_fw[3][1] = 5;
dist_fw[3][4] = 1;
dist_fw[4][1] = 2;
floydWarshall(V);
std::cout << "All-Pairs Shortest Paths:\n";
for (int i = 1; i <= V; ++i) {
for (int j = 1; j <= V; ++j) {
if (dist_fw[i][j] == INF_FW) {
std::cout << "INF\t";
} else {
std::cout << dist_fw[i][j] << "\t";
}
}
std::cout << "\n";
}
return 0;
}
*/1.10 图论：最小生成树算法
1.10.1 Kruskal 算法 (克鲁斯卡尔)
基于边，使用并查集检测环。时间复杂度 $O(E \log E)$ 或 $O(E \log V)$。
#include <vector>
#include <algorithm> // for std::sort
#include <numeric> // for std::iota
// 边结构体
struct Edge_Kruskal {
int u, v, weight;
};
// 比较函数，按边权升序排序
bool compareEdges_Kruskal(const Edge_Kruskal& a, const Edge_Kruskal& b) {
return a.weight < b.weight;
}
// 并查集 (DSU) 模板
std::vector<int> parent_dsu;
std::vector<int> rank_dsu; // 用于按秩优化
void makeSet_dsu(int n) {
parent_dsu.resize(n + 1);
std::iota(parent_dsu.begin(), parent_dsu.end(), 0); // 初始化父节点为自身
rank_dsu.assign(n + 1, 0); // 初始化秩为0
}
int findSet_dsu(int i) {
if (parent_dsu[i] == i)
return i;
return parent_dsu[i] = findSet_dsu(parent_dsu[i]); // 路径压缩
}
void unionSets_dsu(int i, int j) {
int root_i = findSet_dsu(i);
int root_j = findSet_dsu(j);
if (root_i != root_j) {
// 按秩合并
if (rank_dsu[root_i] < rank_dsu[root_j]) {
parent_dsu[root_i] = root_j;
} else if (rank_dsu[root_i] > rank_dsu[root_j]) {
parent_dsu[root_j] = root_i;
} else {
parent_dsu[root_j] = root_i;
rank_dsu[root_i]++;
}
}
}
// Kruskal 算法模板
// V: 节点数量
// edges: 边的列表
// 返回 MST 的总权重，如果图不连通则返回 -1 (或 INF)
long long kruskal(int V, std::vector<Edge_Kruskal>& edges) {
makeSet_dsu(V); // 初始化并查集
std::sort(edges.begin(), edges.end(), compareEdges_Kruskal); // 边按权重排序
long long mst_weight = 0;
int edges_count = 0; // 统计加入 MST 的边数
for (const auto& edge : edges) {
int root_u = findSet_dsu(edge.u);
int root_v = findSet_dsu(edge.v);
if (root_u != root_v) { // 如果 u 和 v 不在同一个连通分量中
unionSets_dsu(edge.u, edge.v); // 合并这两个连通分量
mst_weight += edge.weight;
edges_count++;
}
}
if (edges_count == V - 1) { // 如果形成了包含所有 V 个节点且 V-1 条边的树
return mst_weight;
} else {
return -1; // 图不连通，无法形成生成树
}
}
/*
// 示例使用
int main() {
int V = 4; // 节点数量 (1-indexed)
std::vector<Edge_Kruskal> edges = {
{1, 2, 1}, {1, 3, 3}, {1, 4, 4},
{2, 3, 1}, {3, 4, 2}
};
// Expected MST edges: (1,2,1), (2,3,1), (3,4,2)
// MST weight: 1 + 1 + 2 = 4
long long weight = kruskal(V, edges);
if (weight != -1) {
std::cout << "Minimum Spanning Tree weight: " << weight << std::endl; // Output: 4
} else {
std::cout << "Graph is not connected.\n";
}
return 0;
}
*/1.10.2 Prim 算法 (普里姆)
基于点，使用优先队列。时间复杂度 $O(E \log V)$ (使用优先队列)。
#include <vector>
#include <queue>
#include <limits> // for std::numeric_limits
#include <utility> // for std::pair
const int INF_PRIM = std::numeric_limits<int>::max();
// 图的邻接表表示: pair<int, int> {目标节点, 边权}
std::vector<std::vector<std::pair<int, int>>> adj_prim;
std::vector<int> min_cost_prim; // 存储节点到 MST 的最小边权
std::vector<bool> in_mst_prim; // 标记节点是否已加入 MST
// Prim 算法模板
// V: 节点数量
// start_node: 起始节点 (任意选择)
// 返回 MST 的总权重，如果图不连通则返回 -1 (或 INF)
long long prim(int V, int start_node) {
min_cost_prim.assign(V + 1, INF_PRIM);
in_mst_prim.assign(V + 1, false);
long long mst_weight = 0;
int edges_count = 0;
// 优先队列存储 {权重, 节点}，按权重从小到大排序
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;
min_cost_prim[start_node] = 0;
pq.push({0, start_node}); // {当前节点到MST的最小权值, 节点}
while (!pq.empty() && edges_count < V) {
int u_cost = pq.top().first;
int u = pq.top().second;
pq.pop();
if (in_mst_prim[u]) { // 如果节点已在MST中，跳过
continue;
}
in_mst_prim[u] = true;
mst_weight += u_cost;
edges_count++;
for (auto& edge : adj_prim[u]) {
int v = edge.first;
int weight = edge.second;
// 如果 v 不在 MST 中，并且通过 u 到 v 的边权重更小
if (!in_mst_prim[v] && weight < min_cost_prim[v]) {
min_cost_prim[v] = weight;
pq.push({min_cost_prim[v], v});
}
}
}
if (edges_count == V) { // 确保所有节点都加入 MST
return mst_weight;
} else {
return -1; // 图不连通
}
}
/*
// 示例使用
int main() {
int V = 4; // 节点数量 (1-indexed)
adj_prim.resize(V + 1);
// 添加边: u <-> v, weight (无向图，所以要加两次)
adj_prim[1].push_back({2, 1}); adj_prim[2].push_back({1, 1});
adj_prim[1].push_back({3, 3}); adj_prim[3].push_back({1, 3});
adj_prim[1].push_back({4, 4}); adj_prim[4].push_back({1, 4});
adj_prim[2].push_back({3, 1}); adj_prim[3].push_back({2, 1});
adj_prim[3].push_back({4, 2}); adj_prim[4].push_back({3, 2});
long long weight = prim(V, 1); // 从节点1开始Prim
if (weight != -1) {
std::cout << "Minimum Spanning Tree weight: " << weight << std::endl; // Output: 4
} else {
std::cout << "Graph is not connected.\n";
}
return 0;
}
*/1.11 图论：拓扑排序 (Topological Sort)
对有向无环图 (DAG) 的顶点进行线性排序，使得对于每个有向边 $(u, v)$，u 都出现在 v 的前面。
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm> // for std::sort (if needed, but for topological sort it's usually BFS/DFS)
// 图的邻接表表示
std::vector<std::vector<int>> adj_topo;
std::vector<int> in_degree_topo; // 记录每个节点的入度
// 拓扑排序模板 (Kahn's Algorithm - BFS)
// V: 节点数量
// 返回拓扑排序结果，如果存在环则返回空 vector
std::vector<int> topologicalSort(int V) {
std::vector<int> result;
std::queue<int> q;
// 1. 初始化入度
in_degree_topo.assign(V + 1, 0); // 假设节点从1开始
for (int u = 1; u <= V; ++u) {
for (int v : adj_topo[u]) {
in_degree_topo[v]++;
}
}
// 2. 将所有入度为0的节点加入队列
for (int i = 1; i <= V; ++i) {
if (in_degree_topo[i] == 0) {
q.push(i);
}
}
// 3. BFS 遍历
while (!q.empty()) {
int u = q.front();
q.pop();
result.push_back(u);
for (int v : adj_topo[u]) {
in_degree_topo[v]--; // 移除 u 及其所有出边，相当于减少 v 的入度
if (in_degree_topo[v] == 0) {
q.push(v);
}
}
}
// 4. 检查是否存在环 (如果排序的节点数量不等于总节点数，则存在环)
if (result.size() != V) {
// std::cout << "Graph contains a cycle! No topological sort possible.\n";
return {}; // 返回空 vector 表示有环
}
return result;
}
/*
// 示例使用
int main() {
int V = 6; // 节点数量 (1-indexed)
adj_topo.resize(V + 1);
// 添加有向边 (u -> v)
adj_topo[1].push_back(2);
adj_topo[1].push_back(3);
adj_topo[2].push_back(4);
adj_topo[3].push_back(4);
adj_topo[4].push_back(5);
adj_topo[4].push_back(6);
std::vector<int> sorted_nodes = topologicalSort(V);
if (sorted_nodes.empty()) {
std::cout << "Graph contains a cycle.\n";
} else {
std::cout << "Topological Sort: ";
for (int node : sorted_nodes) {
std::cout << node << " ";
}
std::cout << std::endl; // Possible output: 1 2 3 4 5 6 (或 1 3 2 4 5 6 等)
}
// 示例：有环图
adj_topo.assign(3 + 1, std::vector<int>());
adj_topo[1].push_back(2);
adj_topo[2].push_back(3);
adj_topo[3].push_back(1); // 形成环
std::cout << "\nTesting cyclic graph:\n";
sorted_nodes = topologicalSort(3);
if (sorted_nodes.empty()) {
std::cout << "Graph contains a cycle.\n"; // Expected
}
return 0;
}
*/1.12 图论：二分图匹配 (Bipartite Matching)
使用匈牙利算法（基于 DFS 寻找增广路径）。时间复杂度 $O(V \cdot E)$。
#include <vector>
#include <iostream>
// 图的邻接表表示 (从左侧集合指向右侧集合的边)
std::vector<std::vector<int>> adj_bipartite;
std::vector<int> match_r; // match_r[v] = u 表示右侧节点 v 匹配了左侧节点 u
std::vector<bool> visited_bipartite; // 每次 DFS 访问标记
// 匈牙利算法的 DFS 部分
// u: 当前尝试匹配的左侧节点
bool dfs_bipartite_match(int u) {
for (int v : adj_bipartite[u]) {
if (!visited_bipartite[v]) { // 如果右侧节点 v 未被当前 DFS 访问
visited_bipartite[v] = true;
// 如果 v 未被匹配，或者 v 的匹配对象可以找到新的匹配
if (match_r[v] == -1 || dfs_bipartite_match(match_r[v])) {
match_r[v] = u; // 匹配成功，将 v 匹配给 u
return true;
}
}
}
return false; // 无法找到增广路径
}
// 二分图最大匹配模板 (匈牙利算法)
// num_left_nodes: 左侧节点数量 (假设从 1 到 num_left_nodes)
// num_right_nodes: 右侧节点数量 (假设从 1 到 num_right_nodes)
// adj_bipartite: 邻接表，adj_bipartite[u] 存储与左侧节点 u 相连的右侧节点
int maxBipartiteMatch(int num_left_nodes, int num_right_nodes) {
match_r.assign(num_right_nodes + 1, -1); // 初始化所有右侧节点未匹配
int result = 0; // 匹配数量
// 遍历左侧的每个节点，尝试为其找到匹配
for (int u = 1; u <= num_left_nodes; ++u) {
visited_bipartite.assign(num_right_nodes + 1, false); // 每次 DFS 前清空访问标记
if (dfs_bipartite_match(u)) {
result++;
}
}
return result;
}
/*
// 示例使用
int main() {
int num_left = 3; // 左侧节点 U = {1, 2, 3}
int num_right = 3; // 右侧节点 V = {1, 2, 3}
adj_bipartite.resize(num_left + 1);
// 添加边 (U -> V)
adj_bipartite[1].push_back(2);
adj_bipartite[2].push_back(1);
adj_bipartite[2].push_back(3);
adj_bipartite[3].push_back(2);
int max_match = maxBipartiteMatch(num_left, num_right);
std::cout << "Max Bipartite Matching: " << max_match << std::endl; // Output: 2 (e.g., 1->2, 2->1)
return 0;
}
*/1.13 其他常用算法补充
1.13.1 并查集 (Disjoint Set Union, DSU)
管理一系列不相交的集合，支持合并（union）和查找（find）操作。常用于连通性问题和 Kruskal 算法。
#include <vector>
#include <numeric> // for std::iota
// 并查集模板
std::vector<int> parent; // 父节点数组
std::vector<int> sz; // 集合大小数组 (用于按大小合并优化)
// std::vector<int> rank; // 秩数组 (用于按秩合并优化，与大小优化二选一)
// 初始化并查集
void init_dsu(int n) {
parent.resize(n + 1);
std::iota(parent.begin(), parent.end(), 0); // 每个元素的父节点是自己
sz.assign(n + 1, 1); // 每个集合的初始大小是1
// rank.assign(n + 1, 0); // 初始化秩为0
}
// 查找元素 i 所在的集合的根节点（带路径压缩）
int find_set(int i) {
if (parent[i] == i)
return i;
return parent[i] = find_set(parent[i]); // 路径压缩
}
// 合并元素 i 和 j 所在的集合（按大小合并）
void union_sets(int i, int j) {
int root_i = find_set(i);
int root_j = find_set(j);
if (root_i != root_j) {
// 将小集合合并到大集合
if (sz[root_i] < sz[root_j])
std::swap(root_i, root_j);
parent[root_j] = root_i;
sz[root_i] += sz[root_j];
}
}
// 合并元素 i 和 j 所在的集合（按秩合并）
// void union_sets_rank(int i, int j) {
// int root_i = find_set(i);
// int root_j = find_set(j);
// if (root_i != root_j) {
// if (rank[root_i] < rank[root_j])
// std::swap(root_i, root_j);
// parent[root_j] = root_i;
// if (rank[root_i] == rank[root_j])
// rank[root_i]++;
// }
// }
/*
// 示例使用
int main() {
init_dsu(5); // 初始化 5 个元素 (1-5)
union_sets(1, 2);
union_sets(3, 4);
union_sets(1, 3); // 合并 (1,2) 和 (3,4) 所在的集合
// 检查连通性
std::cout << "Are 1 and 4 connected? " << (find_set(1) == find_set(4) ? "Yes" : "No") << std::endl; // Output: Yes
std::cout << "Are 1 and 5 connected? " << (find_set(1) == find_set(5) ? "Yes" : "No") << std::endl; // Output: No
return 0;
}
*/1.13.2 快速幂 (Binary Exponentiation / Exponentiation by Squaring)
高效计算 $A^B \pmod M$ 的算法。时间复杂度 $O(\log B)$。
#include <iostream>
// 快速幂模板 (计算 base^exp % mod)
long long power(long long base, long long exp, long long mod) {
long long res = 1;
base %= mod; // 确保 base 在模数范围内
while (exp > 0) {
if (exp % 2 == 1) { // 如果指数是奇数，累乘 base
res = (res * base) % mod;
}
base = (base * base) % mod; // base 自乘
exp /= 2; // 指数减半
}
return res;
}
// 快速幂模板 (计算 base^exp，不带模数)
long long power(long long base, long long exp) {
long long res = 1;
while (exp > 0) {
if (exp % 2 == 1) {
res *= base;
}
base *= base;
exp /= 2;
}
return res;
}
/*
// 示例使用
int main() {
std::cout << "2^10 % 1000 = " << power(2, 10, 1000) << std::endl; // Output: 24
std::cout << "3^5 = " << power(3, 5) << std::endl; // Output: 243
return 0;
}
*/1.13.3 埃拉托斯特尼筛法 (Sieve of Eratosthenes)
用于在一个给定范围内查找所有素数。
#include <vector>
#include <iostream>
// 埃拉托斯特尼筛法模板
// max_n: 要查找素数的最大范围
std::vector<bool> is_prime_sieve;
std::vector<int> primes_list; // 存储找到的素数
void sieve(int max_n) {
is_prime_sieve.assign(max_n + 1, true); // 假设所有数都是素数
is_prime_sieve[0] = is_prime_sieve[1] = false; // 0和1不是素数
for (int p = 2; p * p <= max_n; ++p) { // 遍历到 sqrt(max_n)
if (is_prime_sieve[p]) {
// 如果 p 是素数，则其所有倍数都不是素数
for (int i = p * p; i <= max_n; i += p) {
is_prime_sieve[i] = false;
}
}
}
// 收集素数列表
primes_list.clear();
for (int p = 2; p <= max_n; ++p) {
if (is_prime_sieve[p]) {
primes_list.push_back(p);
}
}
}
/*
// 示例使用
int main() {
sieve(30);
std::cout << "Primes up to 30: ";
for (int p : primes_list) {
std::cout << p << " ";
}
std::cout << std::endl; // Output: 2 3 5 7 11 13 17 19 23 29
return 0;
}
*/2. 输入输出控制精度
在 C++ 中，可以使用 iomanip 头文件中的函数来控制浮点数的输出精度。
#include <iostream>
#include <iomanip> // 包含这个头文件
int main() {
double pi = 3.1415926535;
double large_num = 12345.6789;
double small_num = 0.000000123;
// 1. 默认输出
std::cout << "Default: " << pi << std::endl; // 3.14159
std::cout << "Default: " << large_num << std::endl; // 12345.7 (默认有效数字)
std::cout << "Default: " << small_num << std::endl; // 1.23e-07 (默认科学计数法)
// 2. 设置总有效数字位数 (precision)
// precision 默认是总的有效数字位数
std::cout << "\nSet precision (total digits):\n";
std::cout << std::setprecision(3) << pi << std::endl; // 3.14
std::cout << std::setprecision(5) << large_num << std::endl; // 12346
std::cout << std::setprecision(2) << small_num << std::endl; // 1.2e-07
// 3. 设置小数点后的位数 (需要结合 fixed 或 scientific)
// fixed: 固定小数位数，不再使用科学计数法
std::cout << "\nSet precision (decimal places with fixed):\n";
std::cout << std::fixed << std::setprecision(2) << pi << std::endl; // 3.14
std::cout << std::fixed << std::setprecision(4) << pi << std::endl; // 3.1416
std::cout << std::fixed << std::setprecision(2) << large_num << std::endl; // 12345.68
std::cout << std::fixed << std::setprecision(8) << small_num << std::endl; // 0.00000012
// 4. 使用科学计数法 (scientific)
std::cout << "\nSet precision (scientific):\n";
std::cout << std::scientific << std::setprecision(5) << pi << std::endl; // 3.14159e+00
std::cout << std::scientific << std::setprecision(3) << large_num << std::endl; // 1.235e+04
std::cout << std::scientific << std::setprecision(5) << small_num << std::endl; // 1.23000e-07
// 5. 恢复默认格式 (一般不需要，但了解一下)
std::cout.unsetf(std::ios_base::floatfield); // 移除 fixed 或 scientific
std::cout << std::setprecision(6); // 恢复默认精度
std::cout << "\nBack to default: " << pi << std::endl;
// C 风格的 printf 也能控制精度
printf("\nUsing printf:\n");
printf("pi (2 decimal places): %.2f\n", pi); // 3.14
printf("pi (4 decimal places): %.4f\n", pi); // 3.1416
printf("large_num (no scientific, 2 decimal places): %.2f\n", large_num); // 12345.68
printf("small_num (scientific, 3 digits): %.3e\n", small_num); // 1.230e-07
return 0;
}3. String 类型常用方法
string 类型在 C++ 中是处理字符串的强大工具。
#include <iostream>
#include <string>
#include <vector> // for vector example
int main() {
std::string s1 = "Hello, World!";
std::string s2 = "C++ Programming";
std::string s3 = " Trim me ";
// 1. 构造函数
std::string empty_s; // 空字符串
std::string copy_s = s1; // 拷贝构造
std::string part_s(s1, 7, 5); // 从 s1 的索引 7 开始取 5 个字符 ("World")
std::string char_s(5, 'x'); // 5 个 'x' ("xxxxx")
std::cout << "part_s: " << part_s << std::endl;
std::cout << "char_s: " << char_s << std::endl;
// 2. 长度和容量
std::cout << "s1.length(): " << s1.length() << std::endl; // 13
std::cout << "s1.size(): " << s1.size() << std::endl; // 13 (同 length)
std::cout << "s1.capacity(): " << s1.capacity() << std::endl; // >= 13 (实际分配内存)
std::cout << "empty_s.empty(): " << empty_s.empty() << std::endl; // 1 (true)
// 3. 访问字符
std::cout << "s1[0]: " << s1[0] << std::endl; // H
std::cout << "s1.at(1): " << s1.at(1) << std::endl; // e (at() 提供边界检查)
// 4. 字符串拼接
std::string s4 = s1 + " " + s2;
std::cout << "s4: " << s4 << std::endl; // "Hello, World! C++ Programming"
s1.append(" Beautiful"); // "Hello, World! Beautiful"
std::cout << "s1 after append: " << s1 << std::endl;
// 5. 子字符串
std::string sub = s1.substr(7, 5); // 从索引 7 开始取 5 个字符
std::cout << "s1.substr(7, 5): " << sub << std::endl; // "World"
// 6. 查找
size_t pos = s1.find("World");
if (pos != std::string::npos) {
std::cout << "'World' found at pos: " << pos << std::endl; // 7
} else {
std::cout << "'World' not found." << std::endl;
}
pos = s1.rfind("l"); // 从后往前找
std::cout << "Last 'l' found at pos: " << pos << std::endl; // 9
// 7. 插入和删除
s1.insert(0, "Greetings, "); // "Greetings, Hello, World! Beautiful"
std::cout << "s1 after insert: " << s1 << std::endl;
s1.erase(0, 11); // 删除从索引 0 开始的 11 个字符
std::cout << "s1 after erase: " << s1 << std::endl; // "Hello, World! Beautiful"
// 8. 替换
s1.replace(7, 5, "Earth"); // 从索引 7 开始的 5 个字符替换为 "Earth"
std::cout << "s1 after replace: " << s1 << std::endl; // "Hello, Earth! Beautiful"
// 9. 清空
empty_s.clear();
std::cout << "empty_s.empty() after clear: " << empty_s.empty() << std::endl;
// 10. 字符串与数字转换
std::string num_str = "123";
int num_int = std::stoi(num_str); // string to int
std::cout << "stoi('123'): " << num_int << std::endl;
std::string pi_str = "3.14159";
double pi_double = std::stod(pi_str); // string to double
std::cout << "stod('3.14159'): " << pi_double << std::endl;
int another_int = 456;
std::string another_str = std::to_string(another_int); // int to string
std::cout << "to_string(456): " << another_str << std::endl;
// 11. 遍历字符串
std::cout << "Iterating s2: ";
for (char c : s2) { // C++11 range-based for loop
std::cout << c << " ";
}
std::cout << std::endl;
for (size_t i = 0; i < s2.length(); ++i) { // 传统 for loop
// std::cout << s2[i];
}
}4. STL 容器相关方法及示例
4.1 std::vector (动态数组)
#include <iostream>
#include <vector>
#include <algorithm> // for std::sort, std::reverse etc.
int main() {
// 1. 构造
std::vector<int> v1; // 空 vector
std::vector<int> v2(5); // 5 个元素，初始化为 0
std::vector<int> v3(3, 100); // 3 个元素，初始化为 100 -> {100, 100, 100}
std::vector<int> v4 = {1, 2, 3, 4, 5}; // 初始化列表
std::cout << "v3: "; for (int x : v3) std::cout << x << " "; std::cout << std::endl; // 100 100 100
// 2. 添加/删除元素
v1.push_back(10); // 在末尾添加
v1.push_back(20);
v1.push_back(30);
std::cout << "v1 after push_back: "; for (int x : v1) std::cout << x << " "; std::cout << std::endl; // 10 20 30
v1.pop_back(); // 移除末尾元素 (30)
std::cout << "v1 after pop_back: "; for (int x : v1) std::cout << x << " "; std::cout << std::endl; // 10 20
// 3. 访问元素
std::cout << "v1[0]: " << v1[0] << std::endl; // 10
std::cout << "v1.at(1): " << v1.at(1) << std::endl; // 20 (带边界检查)
std::cout << "v1.front(): " << v1.front() << std::endl; // 10
std::cout << "v1.back(): " << v1.back() << std::endl; // 20
// 4. 大小与容量
std::cout << "v1.size(): " << v1.size() << std::endl; // 2
std::cout << "v1.capacity(): " << v1.capacity() << std::endl; // >= 2
std::cout << "v1.empty(): " << v1.empty() << std::endl; // 0 (false)
// 5. 插入和删除（通过迭代器）
v4 = {1, 2, 3, 4, 5};
v4.insert(v4.begin() + 2, 99); // 在索引 2 处插入 99 -> {1, 2, 99, 3, 4, 5}
std::cout << "v4 after insert: "; for (int x : v4) std::cout << x << " "; std::cout << std::endl;
v4.erase(v4.begin() + 2); // 删除索引 2 处的元素 (99) -> {1, 2, 3, 4, 5}
std::cout << "v4 after erase: "; for (int x : v4) std::cout << x << " "; std::cout << std::endl;
// 6. 清空
v1.clear();
std::cout << "v1.size() after clear: " << v1.size() << std::endl; // 0
}4.2 std::map (有序键值对)
基于红黑树实现，键自动排序，查找、插入、删除平均 $O(\log N)$。
#include <iostream>
#include <map>
#include <string>
int main() {
// 1. 构造
std::map<std::string, int> ages;
// 2. 插入元素
ages["Alice"] = 30; // 方式一：使用 operator[]
ages["Bob"] = 25;
ages.insert({"Charlie", 35}); // 方式二：使用 insert (pair 或 initializer_list)
ages.emplace("David", 40); // 方式三：使用 emplace (更高效，避免临时对象)
// 3. 访问元素
std::cout << "Alice's age: " << ages["Alice"] << std::endl; // 30
// 如果键不存在，operator[] 会插入一个默认值元素
std::cout << "Eve's age (access via []): " << ages["Eve"] << std::endl; // 0 (int 默认值)
// 推荐使用 find 检查是否存在，避免不必要的插入
auto it = ages.find("Bob");
if (it != ages.end()) {
std::cout << "Bob's age (access via find): " << it->second << std::endl; // 25
}
// 4. 遍历
std::cout << "\nMap contents:\n";
for (const auto& pair : ages) { // C++11 range-based for
std::cout << pair.first << ": " << pair.second << std::endl;
}
// 键按字典序排序输出：Alice, Bob, Charlie, David, Eve
// 5. 查找键是否存在
std::cout << "Count for 'Alice': " << ages.count("Alice") << std::endl; // 1
std::cout << "Count for 'Frank': " << ages.count("Frank") << std::endl; // 0
// 6. 删除元素
ages.erase("Eve"); // 根据键删除
it = ages.find("Bob");
if (it != ages.end()) {
ages.erase(it); // 根据迭代器删除
}
std::cout << "\nMap after erase:\n";
for (const auto& pair : ages) {
std::cout << pair.first << ": " << pair.second << std::endl;
}
// 7. 大小与清空
std::cout << "Map size: " << ages.size() << std::endl; // 3
ages.clear();
std::cout << "Map empty: " << ages.empty() << std::endl; // 1 (true)
}4.3 std::set (有序不重复元素集合)
基于红黑树实现，元素自动排序，查找、插入、删除平均 $O(\log N)$。
#include <iostream>
#include <set>
int main() {
// 1. 构造
std::set<int> mySet;
// 2. 插入元素
mySet.insert(10);
mySet.insert(30);
mySet.insert(20);
mySet.insert(10); // 重复元素不会被插入
// 3. 遍历 (元素自动排序)
std::cout << "Set elements: ";
for (int x : mySet) {
std::cout << x << " "; // Output: 10 20 30
}
std::cout << std::endl;
// 4. 查找元素
auto it = mySet.find(20);
if (it != mySet.end()) {
std::cout << "Found 20 in set." << std::endl;
} else {
std::cout << "20 not found." << std::endl;
}
std::cout << "Count for 30: " << mySet.count(30) << std::endl; // 1
std::cout << "Count for 50: " << mySet.count(50) << std::endl; // 0
// 5. 删除元素
mySet.erase(10); // 根据值删除
std::cout << "Set after erasing 10: ";
for (int x : mySet) {
std::cout << x << " "; // Output: 20 30
}
std::cout << std::endl;
// 6. 大小与清空
std::cout << "Set size: " << mySet.size() << std::endl; // 2
mySet.clear();
std::cout << "Set empty: " << mySet.empty() << std::endl; // 1 (true)
}4.4 std::unordered_map (无序键值对)
基于哈希表实现，键不排序，查找、插入、删除平均 $O(1)$，最坏 $O(N)$（哈希冲突严重）。
#include <iostream>
#include <unordered_map>
#include <string>
int main() {
// 1. 构造
std::unordered_map<std::string, int> scores;
// 2. 插入元素 (与 std::map 类似)
scores["Alice"] = 95;
scores.insert({"Bob", 88});
scores.emplace("Charlie", 76);
// 3. 访问元素 (与 std::map 类似)
std::cout << "Alice's score: " << scores["Alice"] << std::endl; // 95
// 4. 遍历 (元素顺序不确定)
std::cout << "\nUnordered Map contents:\n";
for (const auto& pair : scores) {
std::cout << pair.first << ": " << pair.second << std::endl;
}
// 5. 查找键是否存在 (与 std::map 类似)
if (scores.count("Bob")) {
std::cout << "Bob is in the map." << std::endl;
}
// 6. 删除元素 (与 std::map 类似)
scores.erase("Charlie");
// 7. 大小与清空
std::cout << "Unordered Map size: " << scores.size() << std::endl; // 2
scores.clear();
}5. algorithm 库中常用方法
algorithm 头文件包含了大量的非成员函数模板，用于对各种容器进行操作。
#include <iostream>
#include <vector>
#include <string>
#include <algorithm> // 核心算法库
#include <numeric> // for std::accumulate
int main() {
std::vector<int> vec = {5, 2, 8, 1, 9, 3};
std::string str = "hello";
// 1. `std::sort()`
// 对容器的元素进行排序。默认升序。
std::sort(vec.begin(), vec.end());
std::cout << "Sorted vec: ";
for (int x : vec) std::cout << x << " "; // Output: 1 2 3 5 8 9
std::cout << std::endl;
// 自定义排序 (降序)
std::sort(vec.begin(), vec.end(), std::greater<int>());
std::cout << "Sorted vec (desc): ";
for (int x : vec) std::cout << x << " "; // Output: 9 8 5 3 2 1
std::cout << std::endl;
// 2. `std::reverse()`
// 反转容器中元素的顺序。
std::reverse(str.begin(), str.end());
std::cout << "Reversed string: " << str << std::endl; // Output: olleh
// 3. `std::min_element()` / `std::max_element()`
// 返回指向序列中最小/最大元素的迭代器。
auto min_it = std::min_element(vec.begin(), vec.end());
std::cout << "Min element: " << *min_it << std::endl; // Output: 1 (after re-sorting ascending first)
auto max_it = std::max_element(vec.begin(), vec.end());
std::cout << "Max element: " << *max_it << std::endl; // Output: 9
// 4. `std::accumulate()` (在 `<numeric>` 中)
// 对容器中的元素进行累加。
int sum = std::accumulate(vec.begin(), vec.end(), 0); // 0 是初始值
std::cout << "Sum of vec elements: " << sum << std::endl; // Output: 30 (9+8+5+3+2+1)
// 5. `std::count()` / `std::count_if()`
// 统计某个特定值出现的次数 / 统计满足某个条件的元素次数。
std::vector<int> count_vec = {1, 2, 2, 3, 2, 4};
int num_twos = std::count(count_vec.begin(), count_vec.end(), 2);
std::cout << "Number of 2s: " << num_twos << std::endl; // Output: 3
int num_even = std::count_if(count_vec.begin(), count_vec.end(), [](int x){ return x % 2 == 0; });
std::cout << "Number of even elements: " << num_even << std::endl; // Output: 4 (2, 2, 2, 4)
// 6. `std::find()` / `std::find_if()`
// 查找某个特定值 / 查找满足某个条件的第一个元素。
auto found_it = std::find(count_vec.begin(), count_vec.end(), 3);
if (found_it != count_vec.end()) {
std::cout << "Found 3 at index: " << std::distance(count_vec.begin(), found_it) << std::endl; // Output: 3
}
auto found_odd = std::find_if(count_vec.begin(), count_vec.end(), [](int x){ return x % 2 != 0; });
std::cout << "First odd element: " << *found_odd << std::endl; // Output: 1
// 7. `std::lower_bound()` / `std::upper_bound()`
// 仅适用于有序序列。
// lower_bound: 返回指向第一个 **不小于** 某个值的元素的迭代器。
// upper_bound: 返回指向第一个 **大于** 某个值的元素的迭代器。
std::vector<int> sorted_vec = {1, 2, 2, 3, 4, 5};
auto lb = std::lower_bound(sorted_vec.begin(), sorted_vec.end(), 2);
std::cout << "lower_bound for 2: " << *lb << " at index " << std::distance(sorted_vec.begin(), lb) << std::endl; // Output: 2 at index 1
auto ub = std::upper_bound(sorted_vec.begin(), sorted_vec.end(), 2);
std::cout << "upper_bound for 2: " << *ub << " at index " << std::distance(sorted_vec.begin(), ub) << std::endl; // Output: 3 at index 3
// 8. `std::fill()`
// 将指定范围内的元素填充为某个值。
std::vector<int> fill_vec(5);
std::fill(fill_vec.begin(), fill_vec.end(), 7);
std::cout << "Filled vector: ";
for (int x : fill_vec) std::cout << x << " "; // Output: 7 7 7 7 7
std::cout << std::endl;
// 9. `std::unique()`
// 移除相邻的重复元素（并不能真正改变容器大小，只将不重复元素移到前面，返回一个迭代器指向新序列的尾后）。
// 通常需要配合 `erase()` 来真正删除。
std::vector<int> unique_vec = {1, 2, 2, 3, 3, 3, 4, 5, 5};
auto last = std::unique(unique_vec.begin(), unique_vec.end());
unique_vec.erase(last, unique_vec.end());
std::cout << "Unique elements: ";
for (int x : unique_vec) std::cout << x << " "; // Output: 1 2 3 4 5
std::cout << std::endl;
// 10. `std::next_permutation()` / `std::prev_permutation()`
// 生成序列的下一个/上一个字典序排列。
std::string p_str = "bac";
std::sort(p_str.begin(), p_str.end()); // 必须先排序到最小排列
std::cout << "Permutations of 'bac':\n";
do {
std::cout << p_str << std::endl;
} while (std::next_permutation(p_str.begin(), p_str.end()));
// Output: abc, acb, bac, bca, cab, cba
// 11. `std::swap()`
// 交换两个变量的值。
int a = 10, b = 20;
std::swap(a, b);
std::cout << "a: " << a << ", b: " << b << std::endl; // Output: a: 20, b: 10
}补充
#include <vector> // 包含vector容器
#include <string> // 包含string类型
#include <iostream> // 包含输入输出流，用于示例或调试
/**
* @brief 计算KMP算法的LPS (Longest Proper Prefix which is also a Suffix) 数组。
* LPS数组（也称为前缀函数或部分匹配表）是KMP算法的核心，
* 它帮助我们在发生不匹配时知道应该“跳过”多少字符，避免重复比较。
* lps[i] 表示 pattern[0...i] 这个子串的最长相等前缀和后缀的长度。
*
* @param pattern 要计算LPS数组的模式字符串。
* @return vector<int> LPS数组。
*/
vector<int> computeLPS(string pattern) {
int m = pattern.length(); // 获取模式字符串的长度
vector<int> lps(m, 0); // 初始化LPS数组，大小与模式字符串相同，所有元素初始为0
// len 变量表示当前已匹配的最长公共前缀和后缀的长度。
// 在构建LPS数组时，它也代表着 pattern[0...len-1] 是 pattern[0...i] 的一个前缀，
// 并且这个前缀也等于 pattern[i - len + 1 ... i] 这个后缀的长度。
int len = 0;
// i 变量用于遍历模式字符串，从索引1开始，因为lps[0]始终为0（单个字符没有真前缀和真后缀）。
int i = 1;
// 遍历模式字符串的每个字符来填充LPS数组
while (i < m) {
// 情况1：当前字符 pattern[i] 与 pattern[len] 匹配
// 这意味着我们可以将当前的最长公共前缀后缀的长度增加1
if (pattern[i] == pattern[len]) {
len++; // 长度加1
lps[i] = len; // 更新 lps[i] 为新的长度
i++; // 移动到模式字符串的下一个字符
}
// 情况2：当前字符 pattern[i] 与 pattern[len] 不匹配
else {
// 如果 len 不为0，说明之前有匹配的前缀后缀，现在发生不匹配，
// 我们需要“回溯”len，将其设置为 pattern[len-1] 对应的LPS值。
// 这样，我们尝试寻找一个更短的、但是仍然是pattern[0...i-1]前缀后缀的子串，
// 来作为新的匹配起点。
if (len != 0) {
len = lps[len - 1];
// 注意：这里 i 不变，因为我们只是改变了 len 的值，
// 需要用新的 len 值继续与 pattern[i] 比较。
}
// 如果 len 已经为0（即 pattern[0] 就不匹配，或者已经回溯到起点），
// 这意味着没有更短的公共前缀后缀了。
else {
lps[i] = 0; // lps[i] 设为0
i++; // 移动到模式字符串的下一个字符
}
}
}
return lps; // 返回计算好的LPS数组
}
/**
* @brief 使用KMP算法在文本字符串中查找模式字符串的所有出现位置。
* KMP算法通过利用模式字符串自身的特性（LPS数组）来避免在匹配失败时
* 对文本字符串指针的回溯，从而实现高效的查找。
*
* @param text 要搜索的文本字符串。
* @param pattern 要查找的模式字符串。
* @return vector<int> 包含模式字符串在文本中所有起始索引的列表。
*/
vector<int> KMP(string text, string pattern) {
vector<int> result; // 存储所有找到的匹配的起始索引
// 调用 computeLPS 函数预处理模式字符串，获取LPS数组
vector<int> lps = computeLPS(pattern);
int n = text.length(); // 文本字符串的长度
int m = pattern.length(); // 模式字符串的长度
// i 是文本字符串 text 的当前字符索引
// j 是模式字符串 pattern 的当前字符索引（也表示已匹配的字符数量）
int i = 0, j = 0;
// 遍历文本字符串，直到文本指针到达末尾
while (i < n) {
// 情况1：当前字符 text[i] 与 pattern[j] 匹配
if (pattern[j] == text[i]) {
i++; // 文本指针向前移动
j++; // 模式指针向前移动
}
// 情况2：模式字符串完全匹配（j 达到了模式的长度 m）
if (j == m) {
// 找到一个匹配，其起始索引为 text[i - j]
result.push_back(i - j);
// 利用LPS数组进行模式字符串的“跳跃”：
// j 回溯到 lps[j-1] 的位置，这意味着我们已经匹配的部分
// pattern[0...j-1] 的最长公共前缀后缀是 pattern[0...lps[j-1]-1]。
// 我们可以直接从这个位置继续匹配，无需从头开始。
j = lps[j - 1];
}
// 情况3：当前字符不匹配（pattern[j] != text[i]），且文本指针还在文本范围内
else if (i < n && pattern[j] != text[i]) {
// 如果模式指针 j 不为0，说明之前有部分匹配，现在发生不匹配。
// 我们可以利用LPS数组进行模式字符串的“跳跃”：
// 将模式指针 j 设置为 lps[j-1]，这样可以避免不必要的回溯和重复比较。
if (j != 0) {
j = lps[j - 1];
}
// 如果模式指针 j 已经为0，这意味着 pattern[0] 就不匹配当前 text[i]，
// 只能简单地将文本指针向前移动，模式指针 j 保持0。
else {
i++;
}
}
}
return result; // 返回所有匹配的起始索引列表
}