ACM \u7ade\u8d5b\u4e2d C++ \u4e2d\u5e38\u7528\u7684\u7b97\u6cd5\u6a21\u677f\u3001\u8f93\u5165\u8f93\u51fa\u63a7\u5236\u3001\u5b57\u7b26\u4e32\u65b9\u6cd5\u3001STL \u5bb9\u5668\u4ee5\u53ca \u91cd\u8981\u63d0\u793a\uff1a<\/strong><\/p>\n \u4e00\u79cd\u9ad8\u6548\u7684\u57fa\u4e8e\u5206\u6cbb\u7684\u6392\u5e8f\u7b97\u6cd5\u3002\u5e73\u5747\u65f6\u95f4\u590d\u6742\u5ea6 $O(N \\log N)$\uff0c\u6700\u574f $O(N^2)$\u3002<\/p>\n \u9002\u7528\u4e8e\u5df2\u6392\u5e8f\u6570\u7ec4\u4e2d\u67e5\u627e\u7279\u5b9a\u5143\u7d20\u3002\u65f6\u95f4\u590d\u6742\u5ea6 $O(\\log N)$\u3002<\/p>\n \u7528\u4e8e\u904d\u5386\u6216\u641c\u7d22\u56fe\u7684\u7b97\u6cd5\u3002\u5e38\u7528\u4e8e\u67e5\u627e\u6700\u77ed\u8def\u5f84\uff08\u65e0\u6743\u56fe\uff09\u6216\u5c42\u7ea7\u904d\u5386\u3002<\/p>\n \u7528\u4e8e\u904d\u5386\u6216\u641c\u7d22\u56fe\u7684\u7b97\u6cd5\u3002\u5e38\u7528\u4e8e\u8fde\u901a\u6027\u3001\u73af\u68c0\u6d4b\u3001\u62d3\u6251\u6392\u5e8f\u7b49\u3002<\/p>\n \u6709 N \u4ef6\u7269\u54c1\u548c\u4e00\u4e2a\u5bb9\u91cf\u4e3a V \u7684\u80cc\u5305\u3002\u7b2c i \u4ef6\u7269\u54c1\u7684\u91cd\u91cf\u662f \u7ed9\u5b9a\u4e24\u4e2a\u5e8f\u5217\uff0c\u627e\u5230\u5b83\u4eec\u4e4b\u95f4\u6700\u957f\u7684\u516c\u5171\u5b50\u5e8f\u5217\u7684\u957f\u5ea6\u3002<\/p>\n \u7ed9\u5b9a\u4e00\u4e2a\u65e0\u5e8f\u7684\u6574\u6570\u6570\u7ec4\uff0c\u627e\u5230\u5176\u4e2d\u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217\u7684\u957f\u5ea6\u3002<\/p>\n \u8d2a\u5fc3\u7b97\u6cd5\u6ca1\u6709\u901a\u7528\u6a21\u677f\uff0c\u5176\u6838\u5fc3\u601d\u60f3\u662f\u5728\u6bcf\u4e00\u6b65\u505a\u51fa\u5c40\u90e8\u6700\u4f18\u7684\u9009\u62e9\uff0c\u5e76\u671f\u671b\u8fd9\u4e9b\u5c40\u90e8\u6700\u4f18\u89e3\u80fd\u5bfc\u81f4\u5168\u5c40\u6700\u4f18\u89e3\u3002\u8fd9\u901a\u5e38\u9700\u8981\u8bc1\u660e<\/strong>\u5176\u6b63\u786e\u6027\u3002<\/p>\n \u793a\u4f8b\uff1a\u6d3b\u52a8\u9009\u62e9\u95ee\u9898<\/strong><\/p>\n \u7ed9\u5b9a\u4e00\u7ec4\u6d3b\u52a8\uff0c\u6bcf\u4e2a\u6d3b\u52a8\u6709\u5f00\u59cb\u65f6\u95f4 \u5355\u6e90\u6700\u77ed\u8def\u5f84\u7b97\u6cd5\uff0c\u9002\u7528\u4e8e\u6240\u6709\u8fb9\u6743\u4e3a\u975e\u8d1f\u7684\u56fe\u3002\u65f6\u95f4\u590d\u6742\u5ea6 $O(E \\log V)$ (\u4f7f\u7528\u4f18\u5148\u961f\u5217)\u3002<\/p>\n \u5355\u6e90\u6700\u77ed\u8def\u5f84\u7b97\u6cd5\uff0c\u53ef\u4ee5\u5904\u7406\u542b\u6709\u8d1f\u6743\u8fb9\u7684\u56fe\uff0c\u5e76\u80fd\u68c0\u6d4b\u8d1f\u6743\u73af\u3002\u65f6\u95f4\u590d\u6742\u5ea6 $O(V \\cdot E)$\u3002<\/p>\n \u5168\u6e90\u6700\u77ed\u8def\u5f84\u7b97\u6cd5\uff0c\u53ef\u4ee5\u5904\u7406\u542b\u6709\u8d1f\u6743\u8fb9\u7684\u56fe\uff0c\u4f46\u4e0d\u80fd\u68c0\u6d4b\u8d1f\u6743\u73af\uff08\u53ea\u80fd\u68c0\u6d4b\u51fa\u81ea\u8eab\u5230\u81ea\u8eab\u7684\u8d1f\u8ddd\u79bb\uff09\u3002\u65f6\u95f4\u590d\u6742\u5ea6 $O(V^3)$\u3002<\/p>\n \u57fa\u4e8e\u8fb9\uff0c\u4f7f\u7528\u5e76\u67e5\u96c6\u68c0\u6d4b\u73af\u3002\u65f6\u95f4\u590d\u6742\u5ea6 $O(E \\log E)$ \u6216 $O(E \\log V)$\u3002<\/p>\n \u57fa\u4e8e\u70b9\uff0c\u4f7f\u7528\u4f18\u5148\u961f\u5217\u3002\u65f6\u95f4\u590d\u6742\u5ea6 $O(E \\log V)$ (\u4f7f\u7528\u4f18\u5148\u961f\u5217)\u3002<\/p>\n \u5bf9\u6709\u5411\u65e0\u73af\u56fe (DAG) \u7684\u9876\u70b9\u8fdb\u884c\u7ebf\u6027\u6392\u5e8f\uff0c\u4f7f\u5f97\u5bf9\u4e8e\u6bcf\u4e2a\u6709\u5411\u8fb9 $(u, v)$\uff0c \u4f7f\u7528\u5308\u7259\u5229\u7b97\u6cd5\uff08\u57fa\u4e8e DFS \u5bfb\u627e\u589e\u5e7f\u8def\u5f84\uff09\u3002\u65f6\u95f4\u590d\u6742\u5ea6 $O(V \\cdot E)$\u3002<\/p>\n \u7ba1\u7406\u4e00\u7cfb\u5217\u4e0d\u76f8\u4ea4\u7684\u96c6\u5408\uff0c\u652f\u6301\u5408\u5e76\uff08union\uff09\u548c\u67e5\u627e\uff08find\uff09\u64cd\u4f5c\u3002\u5e38\u7528\u4e8e\u8fde\u901a\u6027\u95ee\u9898\u548c Kruskal \u7b97\u6cd5\u3002<\/p>\n \u9ad8\u6548\u8ba1\u7b97 $A^B \\pmod M$ \u7684\u7b97\u6cd5\u3002\u65f6\u95f4\u590d\u6742\u5ea6 $O(\\log B)$\u3002<\/p>\n \u7528\u4e8e\u5728\u4e00\u4e2a\u7ed9\u5b9a\u8303\u56f4\u5185\u67e5\u627e\u6240\u6709\u7d20\u6570\u3002<\/p>\n \u5728 C++ \u4e2d\uff0c\u53ef\u4ee5\u4f7f\u7528 \u57fa\u4e8e\u7ea2\u9ed1\u6811\u5b9e\u73b0\uff0c\u952e\u81ea\u52a8\u6392\u5e8f\uff0c\u67e5\u627e\u3001\u63d2\u5165\u3001\u5220\u9664\u5e73\u5747 $O(\\log N)$\u3002<\/p>\n \u57fa\u4e8e\u7ea2\u9ed1\u6811\u5b9e\u73b0\uff0c\u5143\u7d20\u81ea\u52a8\u6392\u5e8f\uff0c\u67e5\u627e\u3001\u63d2\u5165\u3001\u5220\u9664\u5e73\u5747 $O(\\log N)$\u3002<\/p>\n \u57fa\u4e8e\u54c8\u5e0c\u8868\u5b9e\u73b0\uff0c\u952e\u4e0d\u6392\u5e8f\uff0c\u67e5\u627e\u3001\u63d2\u5165\u3001\u5220\u9664\u5e73\u5747 $O(1)$\uff0c\u6700\u574f $O(N)$\uff08\u54c8\u5e0c\u51b2\u7a81\u4e25\u91cd\uff09\u3002<\/p>\n \ud83e\udd16ACM\u7b97\u6cd5\u6574\u7406 ACM \u7ade\u8d5b\u4e2d C++ \u4e2d\u5e38\u7528\u7684\u7b97\u6cd5\u6a21\u677f\u3001\u8f93\u5165\u8f93\u51fa\u63a7\u5236\u3001\u5b57\u7b26\u4e32\u65b9\u6cd5\u3001STL \u5bb9\u5668\u4ee5\u53ca alg […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2,7],"tags":[10],"class_list":["post-101","post","type-post","status-publish","format-standard","hentry","category-c","category-7","tag-acm"],"_links":{"self":[{"href":"https:\/\/blog.notiq.cn\/index.php\/wp-json\/wp\/v2\/posts\/101","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.notiq.cn\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.notiq.cn\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.notiq.cn\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.notiq.cn\/index.php\/wp-json\/wp\/v2\/comments?post=101"}],"version-history":[{"count":0,"href":"https:\/\/blog.notiq.cn\/index.php\/wp-json\/wp\/v2\/posts\/101\/revisions"}],"wp:attachment":[{"href":"https:\/\/blog.notiq.cn\/index.php\/wp-json\/wp\/v2\/media?parent=101"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.notiq.cn\/index.php\/wp-json\/wp\/v2\/categories?post=101"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.notiq.cn\/index.php\/wp-json\/wp\/v2\/tags?post=101"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}algorithm<\/code> \u5e93\u7684\u4f7f\u7528\u793a\u4f8b\u3002<\/p>\n
\n\n
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);<\/code> \u6765\u52a0\u901f\u8f93\u5165\u8f93\u51fa\u3002<\/li>\n#include <bits\/stdc++.h><\/code> \u5728\u591a\u6570 OJ \u4e0a\u90fd\u662f\u53ef\u7528\u7684\uff0c\u53ef\u4ee5\u5305\u542b\u5927\u90e8\u5206\u5e38\u7528\u5e93\uff0c\u4f46\u6b63\u5f0f\u5b66\u4e60\u548c\u4ee3\u7801\u63d0\u4ea4\u65f6\u5efa\u8bae\u6309\u9700\u5305\u542b\u5177\u4f53\u5934\u6587\u4ef6\u3002<\/li>\n<\/ul>\n
\n1. \u5e38\u7528\u7b97\u6cd5\u6a21\u578b\u6a21\u677f<\/h2>\n
1.1 \u6392\u5e8f\uff1a\u5feb\u901f\u6392\u5e8f (QuickSort)<\/h3>\n
#include <vector>\n#include <algorithm> \/\/ for std::swap\n\n\/\/ \u5feb\u901f\u6392\u5e8f\u6a21\u677f\nvoid quickSort(std::vector<int>& arr, int low, int high) {\n if (low < high) {\n int pivot = arr[high]; \/\/ \u9009\u62e9\u6700\u540e\u4e00\u4e2a\u5143\u7d20\u4f5c\u4e3a\u67a2\u8f74\n int i = (low - 1); \/\/ \u5c0f\u4e8e\u67a2\u8f74\u7684\u5143\u7d20\u533a\u57df\u7684\u7ed3\u675f\u7d22\u5f15\n\n for (int j = low; j <= high - 1; j++) {\n \/\/ \u5982\u679c\u5f53\u524d\u5143\u7d20\u5c0f\u4e8e\u6216\u7b49\u4e8e\u67a2\u8f74\n if (arr[j] <= pivot) {\n i++; \/\/ \u589e\u52a0\u5c0f\u4e8e\u67a2\u8f74\u7684\u5143\u7d20\u533a\u57df\u7684\u7ed3\u675f\u7d22\u5f15\n std::swap(arr[i], arr[j]);\n }\n }\n std::swap(arr[i + 1], arr[high]); \/\/ \u5c06\u67a2\u8f74\u653e\u5230\u6b63\u786e\u7684\u4f4d\u7f6e\n\n int pi = i + 1; \/\/ \u67a2\u8f74\u7684\u6700\u7ec8\u4f4d\u7f6e\n\n \/\/ \u9012\u5f52\u6392\u5e8f\u67a2\u8f74\u5de6\u53f3\u4e24\u8fb9\u7684\u5b50\u6570\u7ec4\n quickSort(arr, low, pi - 1);\n quickSort(arr, pi + 1, high);\n }\n}\n\n\/\/ \u793a\u4f8b\u8c03\u7528\uff1a\n\/\/ std::vector<int> myVec = {10, 7, 8, 9, 1, 5};\n\/\/ quickSort(myVec, 0, myVec.size() - 1);<\/code><\/pre>\n1.2 \u641c\u7d22\uff1a\u4e8c\u5206\u67e5\u627e (Binary Search)<\/h3>\n
#include <vector>\n\n\/\/ \u4e8c\u5206\u67e5\u627e\u6a21\u677f (\u67e5\u627e\u662f\u5426\u5b58\u5728)\nbool binarySearch(const std::vector<int>& arr, int target) {\n int low = 0;\n int high = arr.size() - 1;\n\n while (low <= high) {\n int mid = low + (high - low) \/ 2; \/\/ \u9632\u6b62\u6ea2\u51fa\n\n if (arr[mid] == target) {\n return true; \/\/ \u627e\u5230\u76ee\u6807\n } else if (arr[mid] < target) {\n low = mid + 1; \/\/ \u76ee\u6807\u5728\u53f3\u534a\u90e8\u5206\n } else {\n high = mid - 1; \/\/ \u76ee\u6807\u5728\u5de6\u534a\u90e8\u5206\n }\n }\n return false; \/\/ \u672a\u627e\u5230\u76ee\u6807\n}\n\n\/\/ \u4e8c\u5206\u67e5\u627e\u6a21\u677f (\u67e5\u627e\u7b2c\u4e00\u4e2a\u7b49\u4e8e\u6216\u5927\u4e8etarget\u7684\u5143\u7d20\u7d22\u5f15\uff0c\u5373lower_bound)\nint lowerBound(const std::vector<int>& arr, int target) {\n int low = 0;\n int high = arr.size(); \/\/ \u6ce8\u610f\u8fd9\u91cc high \u7684\u521d\u59cb\u503c\u662f arr.size()\n int ans = arr.size(); \/\/ \u7ed3\u679c\uff0c\u5982\u679c\u6ca1\u6709\u627e\u5230\uff0c\u5c31\u662f arr.size()\n\n while (low < high) {\n int mid = low + (high - low) \/ 2;\n if (arr[mid] >= target) {\n ans = mid;\n high = mid; \/\/ \u5c1d\u8bd5\u5728\u5de6\u534a\u90e8\u5206\u627e\u5230\u66f4\u5c0f\u7684\u7d22\u5f15\n } else {\n low = mid + 1;\n }\n }\n return ans;\n}\n\n\/\/ \u4e8c\u5206\u67e5\u627e\u6a21\u677f (\u67e5\u627e\u7b2c\u4e00\u4e2a\u5927\u4e8etarget\u7684\u5143\u7d20\u7d22\u5f15\uff0c\u5373upper_bound)\nint upperBound(const std::vector<int>& arr, int target) {\n int low = 0;\n int high = arr.size();\n int ans = arr.size();\n\n while (low < high) {\n int mid = low + (high - low) \/ 2;\n if (arr[mid] > target) {\n ans = mid;\n high = mid;\n } else {\n low = mid + 1; \/\/ \u76ee\u6807\u5728\u53f3\u534a\u90e8\u5206\uff08\u5305\u62ec mid\uff09\n }\n }\n return ans;\n}<\/code><\/pre>\n1.3 \u56fe\u8bba\uff1a\u5e7f\u5ea6\u4f18\u5148\u641c\u7d22 (BFS)<\/h3>\n
#include <vector>\n#include <queue>\n#include <iostream>\n\n\/\/ \u56fe\u7684\u90bb\u63a5\u8868\u8868\u793a\nstd::vector<std::vector<int>> adj;\nstd::vector<bool> visited;\nstd::vector<int> dist; \/\/ \u8bb0\u5f55\u8ddd\u79bb\uff08\u5bf9\u4e8e\u65e0\u6743\u56fe\u7684\u6700\u77ed\u8def\u5f84\uff09\n\nvoid bfs(int start_node, int num_nodes) {\n visited.assign(num_nodes + 1, false); \/\/ \u6839\u636e\u8282\u70b9\u7f16\u53f7\u8303\u56f4\u8c03\u6574\u5927\u5c0f\n dist.assign(num_nodes + 1, -1); \/\/ \u521d\u59cb\u5316\u8ddd\u79bb\u4e3a-1\uff08\u672a\u8bbf\u95ee\uff09\n\n std::queue<int> q;\n\n q.push(start_node);\n visited[start_node] = true;\n dist[start_node] = 0;\n\n while (!q.empty()) {\n int u = q.front();\n q.pop();\n\n \/\/ \u53ef\u4ee5\u5728\u8fd9\u91cc\u5904\u7406\u8282\u70b9 u\uff0c\u6bd4\u5982\u6253\u5370\n \/\/ std::cout << "Visiting node: " << u << " (distance: " << dist[u] << ")\\n";\n\n for (int v : adj[u]) {\n if (!visited[v]) {\n visited[v] = true;\n dist[v] = dist[u] + 1;\n q.push(v);\n }\n }\n }\n}\n\n\/*\n\/\/ \u793a\u4f8b\u4f7f\u7528\nint main() {\n int n = 5; \/\/ \u8282\u70b9\u6570\u91cf\n adj.resize(n + 1);\n\n \/\/ \u6dfb\u52a0\u8fb9\n adj[1].push_back(2); adj[2].push_back(1);\n adj[1].push_back(3); adj[3].push_back(1);\n adj[2].push_back(4); adj[4].push_back(2);\n adj[3].push_back(5); adj[5].push_back(3);\n\n bfs(1, n);\n\n for (int i = 1; i <= n; ++i) {\n std::cout << "Distance from node 1 to node " << i << ": " << dist[i] << std::endl;\n }\n return 0;\n}\n*\/<\/code><\/pre>\n1.4 \u56fe\u8bba\uff1a\u6df1\u5ea6\u4f18\u5148\u641c\u7d22 (DFS)<\/h3>\n
#include <vector>\n#include <iostream>\n\n\/\/ \u56fe\u7684\u90bb\u63a5\u8868\u8868\u793a\nstd::vector<std::vector<int>> adj_dfs;\nstd::vector<bool> visited_dfs;\n\nvoid dfs(int u) {\n visited_dfs[u] = true;\n \/\/ std::cout << "Visiting node: " << u << std::endl; \/\/ \u5728\u8fd9\u91cc\u5904\u7406\u8282\u70b9\n\n for (int v : adj_dfs[u]) {\n if (!visited_dfs[v]) {\n dfs(v);\n }\n }\n}\n\n\/*\n\/\/ \u793a\u4f8b\u4f7f\u7528\nint main() {\n int n = 5; \/\/ \u8282\u70b9\u6570\u91cf\n adj_dfs.resize(n + 1);\n visited_dfs.assign(n + 1, false);\n\n \/\/ \u6dfb\u52a0\u8fb9\n adj_dfs[1].push_back(2); adj_dfs[2].push_back(1);\n adj_dfs[1].push_back(3); adj_dfs[3].push_back(1);\n adj_dfs[2].push_back(4); adj_dfs[4].push_back(2);\n adj_dfs[3].push_back(5); adj_dfs[5].push_back(3);\n\n dfs(1); \/\/ \u4ece\u8282\u70b91\u5f00\u59cbDFS\n\n \/\/ \u68c0\u67e5\u6240\u6709\u8282\u70b9\u662f\u5426\u90fd\u88ab\u8bbf\u95ee\n for (int i = 1; i <= n; ++i) {\n if (!visited_dfs[i]) {\n std::cout << "Node " << i << " is not reachable from node 1\\n";\n }\n }\n return 0;\n}\n*\/<\/code><\/pre>\n1.5 \u52a8\u6001\u89c4\u5212\uff1a\u80cc\u5305\u95ee\u9898 (0\/1 \u80cc\u5305)<\/h3>\n
w[i]<\/code>\uff0c\u4ef7\u503c\u662f v[i]<\/code>\u3002\u6bcf\u4ef6\u7269\u54c1\u53ea\u80fd\u7528\u4e00\u6b21\uff0c\u95ee\u5728\u4e0d\u8d85\u8fc7\u80cc\u5305\u5bb9\u91cf\u7684\u524d\u63d0\u4e0b\uff0c\u80cc\u5305\u4e2d\u7269\u54c1\u7684\u6700\u5927\u603b\u4ef7\u503c\u3002<\/p>\n#include <vector>\n#include <algorithm> \/\/ for std::max\n\n\/\/ 0\/1 \u80cc\u5305\u95ee\u9898\u6a21\u677f\n\/\/ W: \u80cc\u5305\u5bb9\u91cf\n\/\/ weights: \u7269\u54c1\u91cd\u91cf\u6570\u7ec4\n\/\/ values: \u7269\u54c1\u4ef7\u503c\u6570\u7ec4\n\/\/ n: \u7269\u54c1\u6570\u91cf\nint knapsack01(int W, const std::vector<int>& weights, const std::vector<int>& values, int n) {\n \/\/ dp[j] \u8868\u793a\u5bb9\u91cf\u4e3a j \u65f6\u7684\u6700\u5927\u4ef7\u503c\n \/\/ \u4f7f\u7528\u4e00\u7ef4\u6570\u7ec4\u8fdb\u884c\u7a7a\u95f4\u4f18\u5316\uff0cj \u4ece\u5927\u5230\u5c0f\u904d\u5386\n std::vector<int> dp(W + 1, 0);\n\n for (int i = 0; i < n; ++i) { \/\/ \u904d\u5386\u7269\u54c1\n for (int j = W; j >= weights[i]; --j) { \/\/ \u904d\u5386\u80cc\u5305\u5bb9\u91cf\uff0c\u4ece\u5927\u5230\u5c0f\n dp[j] = std::max(dp[j], dp[j - weights[i]] + values[i]);\n }\n }\n return dp[W];\n}\n\n\/*\n\/\/ \u793a\u4f8b\u4f7f\u7528\nint main() {\n int W = 10;\n std::vector<int> weights = {2, 3, 4, 5};\n std::vector<int> values = {3, 4, 5, 6};\n int n = weights.size();\n\n int max_value = knapsack01(W, weights, values, n);\n std::cout << "Max value for 0\/1 knapsack: " << max_value << std::endl; \/\/ Output: 7 (items with weights 2 and 5)\n return 0;\n}\n*\/<\/code><\/pre>\n1.6 \u52a8\u6001\u89c4\u5212\uff1a\u6700\u957f\u516c\u5171\u5b50\u5e8f\u5217 (LCS)<\/h3>\n
#include <string>\n#include <vector>\n#include <algorithm> \/\/ for std::max\n#include <iostream>\n\n\/\/ LCS \u6a21\u677f (\u8fd4\u56de\u957f\u5ea6)\nint longestCommonSubsequence(const std::string& text1, const std::string& text2) {\n int m = text1.length();\n int n = text2.length();\n\n \/\/ dp[i][j] \u8868\u793a text1 \u7684\u524d i \u4e2a\u5b57\u7b26\u548c text2 \u7684\u524d j \u4e2a\u5b57\u7b26\u7684\u6700\u957f\u516c\u5171\u5b50\u5e8f\u5217\u7684\u957f\u5ea6\n std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));\n\n for (int i = 1; i <= m; ++i) {\n for (int j = 1; j <= n; ++j) {\n if (text1[i - 1] == text2[j - 1]) {\n dp[i][j] = 1 + dp[i - 1][j - 1];\n } else {\n dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);\n }\n }\n }\n return dp[m][n];\n}\n\n\/*\n\/\/ \u793a\u4f8b\u4f7f\u7528\nint main() {\n std::string s1 = "abcde";\n std::string s2 = "ace";\n std::cout << "LCS length: " << longestCommonSubsequence(s1, s2) << std::endl; \/\/ Output: 3\n return 0;\n}\n*\/<\/code><\/pre>\n1.7 \u52a8\u6001\u89c4\u5212\uff1a\u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217 (LIS)<\/h3>\n
#include <vector>\n#include <algorithm> \/\/ for std::max, std::lower_bound\n#include <iostream>\n\n\/\/ LIS \u6a21\u677f (O(N^2) \u65f6\u95f4\u590d\u6742\u5ea6)\nint longestIncreasingSubsequence_N2(const std::vector<int>& nums) {\n if (nums.empty()) {\n return 0;\n }\n int n = nums.size();\n std::vector<int> dp(n, 1); \/\/ dp[i] \u8868\u793a\u4ee5 nums[i] \u7ed3\u5c3e\u7684\u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217\u7684\u957f\u5ea6\n int max_len = 1;\n\n for (int i = 1; i < n; ++i) {\n for (int j = 0; j < i; ++j) {\n if (nums[i] > nums[j]) {\n dp[i] = std::max(dp[i], dp[j] + 1);\n }\n }\n max_len = std::max(max_len, dp[i]);\n }\n return max_len;\n}\n\n\/\/ LIS \u6a21\u677f (O(N log N) \u65f6\u95f4\u590d\u6742\u5ea6)\n\/\/ tails[k] \u5b58\u50a8\u6240\u6709\u957f\u5ea6\u4e3a k+1 \u7684\u9012\u589e\u5b50\u5e8f\u5217\u4e2d\uff0c\u6700\u5c0f\u7684\u7ed3\u5c3e\u5143\u7d20\nint longestIncreasingSubsequence_NlogN(const std::vector<int>& nums) {\n if (nums.empty()) {\n return 0;\n }\n std::vector<int> tails; \/\/ tails \u6570\u7ec4\u662f\u4e25\u683c\u9012\u589e\u7684\n\n for (int num : nums) {\n \/\/ \u67e5\u627e\u7b2c\u4e00\u4e2a\u5927\u4e8e\u6216\u7b49\u4e8e num \u7684\u5143\u7d20\u7684\u4f4d\u7f6e\n auto it = std::lower_bound(tails.begin(), tails.end(), num);\n\n if (it == tails.end()) {\n \/\/ \u5982\u679c num \u6bd4\u6240\u6709 tails \u5143\u7d20\u90fd\u5927\uff0c\u5219\u53ef\u4ee5\u5ef6\u957f\u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217\n tails.push_back(num);\n } else {\n \/\/ \u5426\u5219\uff0c\u66f4\u65b0 tails \u6570\u7ec4\u4e2d\u76f8\u5e94\u4f4d\u7f6e\u7684\u5143\u7d20\u4e3a num\uff0c\n \/\/ \u8fd9\u6837\u53ef\u4ee5\u5f62\u6210\u4e00\u4e2a\u66f4\u5c0f\u7684\u7ed3\u5c3e\u5143\u7d20\uff0c\u4e3a\u540e\u7eed\u66f4\u957f\u7684\u5e8f\u5217\u521b\u9020\u673a\u4f1a\n *it = num;\n }\n }\n return tails.size();\n}\n\n\/*\n\/\/ \u793a\u4f8b\u4f7f\u7528\nint main() {\n std::vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};\n std::cout << "LIS length (N^2): " << longestIncreasingSubsequence_N2(nums) << std::endl; \/\/ Output: 4 (2, 3, 7, 18 \u6216 2, 5, 7, 18)\n std::cout << "LIS length (N log N): " << longestIncreasingSubsequence_NlogN(nums) << std::endl; \/\/ Output: 4\n return 0;\n}\n*\/<\/code><\/pre>\n1.8 \u8d2a\u5fc3\u7b97\u6cd5 (Greedy Algorithms)<\/h3>\n
s_i<\/code> \u548c\u7ed3\u675f\u65f6\u95f4 f_i<\/code>\u3002\u9009\u62e9\u6700\u5927\u6570\u91cf\u7684\u6d3b\u52a8\uff0c\u4f7f\u5f97\u5b83\u4eec\u4e24\u4e24\u4e0d\u91cd\u53e0\u3002<\/p>\n#include <vector>\n#include <algorithm> \/\/ for std::sort\n#include <utility> \/\/ for std::pair\n\n\/\/ \u6d3b\u52a8\u7ed3\u6784\u4f53\nstruct Activity {\n int start;\n int end;\n};\n\n\/\/ \u6bd4\u8f83\u51fd\u6570\uff0c\u6309\u7ed3\u675f\u65f6\u95f4\u5347\u5e8f\u6392\u5e8f\nbool compareActivities(const Activity& a, const Activity& b) {\n return a.end < b.end;\n}\n\n\/\/ \u8d2a\u5fc3\u7b97\u6cd5\uff1a\u6d3b\u52a8\u9009\u62e9\u95ee\u9898\nint selectMaxActivities(std::vector<Activity>& activities) {\n if (activities.empty()) {\n return 0;\n }\n\n \/\/ 1. \u6309\u6d3b\u52a8\u7684\u7ed3\u675f\u65f6\u95f4\u8fdb\u884c\u6392\u5e8f\n std::sort(activities.begin(), activities.end(), compareActivities);\n\n int count = 1; \/\/ \u81f3\u5c11\u9009\u62e9\u7b2c\u4e00\u4e2a\u6d3b\u52a8\n int last_finish_time = activities[0].end; \/\/ \u8bb0\u5f55\u4e0a\u4e00\u4e2a\u9009\u5b9a\u6d3b\u52a8\u7684\u7ed3\u675f\u65f6\u95f4\n\n \/\/ 2. \u904d\u5386\u6392\u5e8f\u540e\u7684\u6d3b\u52a8\uff0c\u9009\u62e9\u7b2c\u4e00\u4e2a\u4e0d\u4e0e\u4e0a\u4e00\u4e2a\u6d3b\u52a8\u91cd\u53e0\u7684\u6d3b\u52a8\n for (size_t i = 1; i < activities.size(); ++i) {\n if (activities[i].start >= last_finish_time) {\n count++;\n last_finish_time = activities[i].end;\n }\n }\n return count;\n}\n\n\/*\n\/\/ \u793a\u4f8b\u4f7f\u7528\nint main() {\n std::vector<Activity> activities = {\n {1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 9}, {5, 9}, {6, 10}, {8, 11}, {8, 12}, {2, 14}, {12, 16}\n };\n \/\/ \u6392\u5e8f\u540e\uff08\u6309\u7ed3\u675f\u65f6\u95f4\uff09: {1,4}, {3,5}, {0,6}, {5,7}, {3,9}, {5,9}, {6,10}, {8,11}, {8,12}, {2,14}, {12,16}\n \/\/ \u5b9e\u9645\u7684\u6392\u5e8f\u7ed3\u679c\u4f9d\u8d56\u4e8e `std::sort` \u7684\u7a33\u5b9a\u6027\uff0c\u4f46\u5bf9\u4e8e\u6b64\u7b97\u6cd5\u4e0d\u5f71\u54cd\u6b63\u786e\u6027\n \/\/ \u6700\u4f18\u9009\u62e9: (1,4), (5,7), (8,11), (12,16) -> 4\u4e2a\n\n std::cout << "Max activities selected: " << selectMaxActivities(activities) << std::endl; \/\/ Output: 4\n return 0;\n}\n*\/<\/code><\/pre>\n1.9 \u56fe\u8bba\uff1a\u6700\u77ed\u8def\u5f84\u7b97\u6cd5<\/h3>\n
1.9.1 Dijkstra \u7b97\u6cd5 (\u8fea\u6770\u65af\u7279\u62c9)<\/h4>\n
#include <vector>\n#include <queue>\n#include <limits> \/\/ for std::numeric_limits\n#include <utility> \/\/ for std::pair\n\nconst int INF = std::numeric_limits<int>::max(); \/\/ \u65e0\u7a77\u5927\n\n\/\/ \u56fe\u7684\u90bb\u63a5\u8868\u8868\u793a: pair<int, int> {\u76ee\u6807\u8282\u70b9, \u8fb9\u6743}\nstd::vector<std::vector<std::pair<int, int>>> adj_dijkstra;\nstd::vector<int> dist_dijkstra; \/\/ \u5b58\u50a8\u4ece\u6e90\u70b9\u5230\u5404\u70b9\u7684\u6700\u77ed\u8ddd\u79bb\n\nvoid dijkstra(int start_node, int num_nodes) {\n dist_dijkstra.assign(num_nodes + 1, INF);\n \/\/ \u4f18\u5148\u961f\u5217\u5b58\u50a8 {\u8ddd\u79bb, \u8282\u70b9}\uff0c\u6309\u8ddd\u79bb\u4ece\u5c0f\u5230\u5927\u6392\u5e8f\n \/\/ \u6ce8\u610f\uff1astd::priority_queue \u9ed8\u8ba4\u662f\u5927\u9876\u5806\uff0c\u6240\u4ee5\u8981\u5b58\u50a8 pair<\u8d1f\u8ddd\u79bb, \u8282\u70b9>\n \/\/ \u6216\u8005\u4f7f\u7528 `greater<std::pair<int, int>>` \u6765\u5b9e\u73b0\u5c0f\u9876\u5806\n std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;\n\n dist_dijkstra[start_node] = 0;\n pq.push({0, start_node}); \/\/ {\u8ddd\u79bb, \u8282\u70b9}\n\n while (!pq.empty()) {\n int d = pq.top().first;\n int u = pq.top().second;\n pq.pop();\n\n \/\/ \u5982\u679c\u5f53\u524d\u53d6\u51fa\u7684\u8ddd\u79bb\u6bd4\u5df2\u77e5\u7684\u6700\u77ed\u8ddd\u79bb\u5927\uff0c\u5219\u8df3\u8fc7\uff08\u5df2\u7ecf\u627e\u5230\u66f4\u77ed\u8def\u5f84\uff09\n if (d > dist_dijkstra[u]) {\n continue;\n }\n\n for (auto& edge : adj_dijkstra[u]) {\n int v = edge.first;\n int weight = edge.second;\n\n if (dist_dijkstra[u] + weight < dist_dijkstra[v]) {\n dist_dijkstra[v] = dist_dijkstra[u] + weight;\n pq.push({dist_dijkstra[v], v});\n }\n }\n }\n}\n\n\/*\n\/\/ \u793a\u4f8b\u4f7f\u7528\nint main() {\n int n = 5; \/\/ \u8282\u70b9\u6570\u91cf (1-indexed)\n adj_dijkstra.resize(n + 1);\n\n \/\/ \u6dfb\u52a0\u8fb9: u -> v, weight\n adj_dijkstra[1].push_back({2, 10});\n adj_dijkstra[1].push_back({3, 3});\n adj_dijkstra[2].push_back({3, 1});\n adj_dijkstra[2].push_back({4, 2});\n adj_dijkstra[3].push_back({2, 4});\n adj_dijkstra[3].push_back({4, 8});\n adj_dijkstra[3].push_back({5, 2});\n adj_dijkstra[4].push_back({5, 7});\n\n dijkstra(1, n);\n\n for (int i = 1; i <= n; ++i) {\n if (dist_dijkstra[i] == INF) {\n std::cout << "Node " << i << ": Unreachable\\n";\n } else {\n std::cout << "Node " << i << ": " << dist_dijkstra[i] << "\\n";\n }\n }\n \/\/ Expected output for start_node 1:\n \/\/ Node 1: 0\n \/\/ Node 2: 7 (1->3->2: 3+4=7)\n \/\/ Node 3: 3 (1->3: 3)\n \/\/ Node 4: 9 (1->3->2->4: 3+4+2=9)\n \/\/ Node 5: 5 (1->3->5: 3+2=5)\n return 0;\n}\n*\/<\/code><\/pre>\n1.9.2 Bellman-Ford \u7b97\u6cd5 (\u8d1d\u5c14\u66fc-\u798f\u7279)<\/h4>\n
#include <vector>\n#include <limits> \/\/ for std::numeric_limits\n\nconst int INF_BF = std::numeric_limits<int>::max();\n\n\/\/ \u8fb9\u7ed3\u6784\u4f53\nstruct Edge {\n int u, v, weight;\n};\n\nstd::vector<int> dist_bf; \/\/ \u5b58\u50a8\u4ece\u6e90\u70b9\u5230\u5404\u70b9\u7684\u6700\u77ed\u8ddd\u79bb\n\n\/\/ Bellman-Ford \u7b97\u6cd5\u6a21\u677f\n\/\/ V: \u8282\u70b9\u6570\u91cf\n\/\/ edges: \u8fb9\u7684\u5217\u8868\n\/\/ start_node: \u6e90\u8282\u70b9\n\/\/ \u8fd4\u56de true \u5982\u679c\u6ca1\u6709\u8d1f\u6743\u73af\uff0cfalse \u5982\u679c\u6709\u8d1f\u6743\u73af\nbool bellmanFord(int V, const std::vector<Edge>& edges, int start_node) {\n dist_bf.assign(V + 1, INF_BF);\n dist_bf[start_node] = 0;\n\n \/\/ \u8fdb\u884c V-1 \u8f6e\u677e\u5f1b\u64cd\u4f5c\n for (int i = 0; i < V - 1; ++i) {\n for (const auto& edge : edges) {\n if (dist_bf[edge.u] != INF_BF && dist_bf[edge.u] + edge.weight < dist_bf[edge.v]) {\n dist_bf[edge.v] = dist_bf[edge.u] + edge.weight;\n }\n }\n }\n\n \/\/ \u518d\u6b21\u677e\u5f1b\uff0c\u68c0\u6d4b\u8d1f\u6743\u73af\n for (const auto& edge : edges) {\n if (dist_bf[edge.u] != INF_BF && dist_bf[edge.u] + edge.weight < dist_bf[edge.v]) {\n return false; \/\/ \u68c0\u6d4b\u5230\u8d1f\u6743\u73af\n }\n }\n return true; \/\/ \u6ca1\u6709\u8d1f\u6743\u73af\n}\n\n\/*\n\/\/ \u793a\u4f8b\u4f7f\u7528\nint main() {\n int V = 5; \/\/ \u8282\u70b9\u6570\u91cf (1-indexed)\n std::vector<Edge> edges = {\n {1, 2, 10}, {1, 3, 3},\n {2, 3, 1}, {2, 4, 2},\n {3, 2, 4}, {3, 4, 8}, {3, 5, 2},\n {4, 5, 7}\n };\n\n if (bellmanFord(V, edges, 1)) {\n for (int i = 1; i <= V; ++i) {\n if (dist_bf[i] == INF_BF) {\n std::cout << "Node " << i << ": Unreachable\\n";\n } else {\n std::cout << "Node " << i << ": " << dist_bf[i] << "\\n";\n }\n }\n } else {\n std::cout << "Graph contains negative cycle!\\n";\n }\n\n \/\/ \u793a\u4f8b\u8d1f\u6743\u73af\n std::vector<Edge> negative_cycle_edges = {\n {1, 2, 1}, {2, 3, -1}, {3, 1, -1}\n };\n std::cout << "\\nTesting negative cycle:\\n";\n if (bellmanFord(3, negative_cycle_edges, 1)) {\n std::cout << "No negative cycle.\\n";\n } else {\n std::cout << "Graph contains negative cycle!\\n";\n }\n return 0;\n}\n*\/<\/code><\/pre>\n1.9.3 Floyd-Warshall \u7b97\u6cd5 (\u5f17\u6d1b\u4f0a\u5fb7-\u6c83\u6c99\u5c14)<\/h4>\n
#include <vector>\n#include <limits> \/\/ for std::numeric_limits\n#include <algorithm> \/\/ for std::min\n\nconst long long INF_FW = std::numeric_limits<long long>::max() \/ 2; \/\/ \u7528 long long \u5e76\u9664\u4ee52\u9632\u6b62\u6ea2\u51fa\n\n\/\/ Floyd-Warshall \u7b97\u6cd5\u6a21\u677f\n\/\/ dist[i][j] \u5b58\u50a8\u4ece i \u5230 j \u7684\u6700\u77ed\u8ddd\u79bb\nstd::vector<std::vector<long long>> dist_fw;\n\nvoid floydWarshall(int V) {\n \/\/ \u521d\u59cb\u5316 dist \u77e9\u9635\uff1a\u5bf9\u89d2\u7ebf\u4e3a0\uff0c\u6709\u8fb9\u4e3a\u6743\u91cd\uff0c\u65e0\u8fb9\u4e3aINF\n \/\/ \u5047\u8bbe dist_fw \u5df2\u7ecf\u5728\u5916\u90e8 resize \u5e76\u521d\u59cb\u5316\u597d\u4e86\n\n for (int k = 1; k <= V; ++k) { \/\/ \u4e2d\u95f4\u8282\u70b9\n for (int i = 1; i <= V; ++i) { \/\/ \u8d77\u59cb\u8282\u70b9\n for (int j = 1; j <= V; ++j) { \/\/ \u7ed3\u675f\u8282\u70b9\n if (dist_fw[i][k] != INF_FW && dist_fw[k][j] != INF_FW) { \/\/ \u8def\u5f84\u5b58\u5728\n dist_fw[i][j] = std::min(dist_fw[i][j], dist_fw[i][k] + dist_fw[k][j]);\n }\n }\n }\n }\n\n \/\/ \u68c0\u6d4b\u8d1f\u6743\u73af (\u5982\u679c dist[i][i] < 0)\n \/\/ for (int i = 1; i <= V; ++i) {\n \/\/ if (dist_fw[i][i] < 0) {\n \/\/ \/\/ \u5b58\u5728\u8d1f\u6743\u73af\n \/\/ }\n \/\/ }\n}\n\n\/*\n\/\/ \u793a\u4f8b\u4f7f\u7528\nint main() {\n int V = 4; \/\/ \u8282\u70b9\u6570\u91cf (1-indexed)\n dist_fw.assign(V + 1, std::vector<long long>(V + 1, INF_FW));\n\n \/\/ \u521d\u59cb\u5316\u81ea\u8eab\u5230\u81ea\u8eab\u8ddd\u79bb\u4e3a0\n for (int i = 1; i <= V; ++i) {\n dist_fw[i][i] = 0;\n }\n\n \/\/ \u6dfb\u52a0\u8fb9\u53ca\u6743\u91cd\n dist_fw[1][2] = 3;\n dist_fw[1][4] = 7;\n dist_fw[2][1] = 8;\n dist_fw[2][3] = 2;\n dist_fw[3][1] = 5;\n dist_fw[3][4] = 1;\n dist_fw[4][1] = 2;\n\n floydWarshall(V);\n\n std::cout << "All-Pairs Shortest Paths:\\n";\n for (int i = 1; i <= V; ++i) {\n for (int j = 1; j <= V; ++j) {\n if (dist_fw[i][j] == INF_FW) {\n std::cout << "INF\\t";\n } else {\n std::cout << dist_fw[i][j] << "\\t";\n }\n }\n std::cout << "\\n";\n }\n return 0;\n}\n*\/<\/code><\/pre>\n1.10 \u56fe\u8bba\uff1a\u6700\u5c0f\u751f\u6210\u6811\u7b97\u6cd5<\/h3>\n
1.10.1 Kruskal \u7b97\u6cd5 (\u514b\u9c81\u65af\u5361\u5c14)<\/h4>\n
#include <vector>\n#include <algorithm> \/\/ for std::sort\n#include <numeric> \/\/ for std::iota\n\n\/\/ \u8fb9\u7ed3\u6784\u4f53\nstruct Edge_Kruskal {\n int u, v, weight;\n};\n\n\/\/ \u6bd4\u8f83\u51fd\u6570\uff0c\u6309\u8fb9\u6743\u5347\u5e8f\u6392\u5e8f\nbool compareEdges_Kruskal(const Edge_Kruskal& a, const Edge_Kruskal& b) {\n return a.weight < b.weight;\n}\n\n\/\/ \u5e76\u67e5\u96c6 (DSU) \u6a21\u677f\nstd::vector<int> parent_dsu;\nstd::vector<int> rank_dsu; \/\/ \u7528\u4e8e\u6309\u79e9\u4f18\u5316\n\nvoid makeSet_dsu(int n) {\n parent_dsu.resize(n + 1);\n std::iota(parent_dsu.begin(), parent_dsu.end(), 0); \/\/ \u521d\u59cb\u5316\u7236\u8282\u70b9\u4e3a\u81ea\u8eab\n rank_dsu.assign(n + 1, 0); \/\/ \u521d\u59cb\u5316\u79e9\u4e3a0\n}\n\nint findSet_dsu(int i) {\n if (parent_dsu[i] == i)\n return i;\n return parent_dsu[i] = findSet_dsu(parent_dsu[i]); \/\/ \u8def\u5f84\u538b\u7f29\n}\n\nvoid unionSets_dsu(int i, int j) {\n int root_i = findSet_dsu(i);\n int root_j = findSet_dsu(j);\n if (root_i != root_j) {\n \/\/ \u6309\u79e9\u5408\u5e76\n if (rank_dsu[root_i] < rank_dsu[root_j]) {\n parent_dsu[root_i] = root_j;\n } else if (rank_dsu[root_i] > rank_dsu[root_j]) {\n parent_dsu[root_j] = root_i;\n } else {\n parent_dsu[root_j] = root_i;\n rank_dsu[root_i]++;\n }\n }\n}\n\n\/\/ Kruskal \u7b97\u6cd5\u6a21\u677f\n\/\/ V: \u8282\u70b9\u6570\u91cf\n\/\/ edges: \u8fb9\u7684\u5217\u8868\n\/\/ \u8fd4\u56de MST \u7684\u603b\u6743\u91cd\uff0c\u5982\u679c\u56fe\u4e0d\u8fde\u901a\u5219\u8fd4\u56de -1 (\u6216 INF)\nlong long kruskal(int V, std::vector<Edge_Kruskal>& edges) {\n makeSet_dsu(V); \/\/ \u521d\u59cb\u5316\u5e76\u67e5\u96c6\n std::sort(edges.begin(), edges.end(), compareEdges_Kruskal); \/\/ \u8fb9\u6309\u6743\u91cd\u6392\u5e8f\n\n long long mst_weight = 0;\n int edges_count = 0; \/\/ \u7edf\u8ba1\u52a0\u5165 MST \u7684\u8fb9\u6570\n\n for (const auto& edge : edges) {\n int root_u = findSet_dsu(edge.u);\n int root_v = findSet_dsu(edge.v);\n\n if (root_u != root_v) { \/\/ \u5982\u679c u \u548c v \u4e0d\u5728\u540c\u4e00\u4e2a\u8fde\u901a\u5206\u91cf\u4e2d\n unionSets_dsu(edge.u, edge.v); \/\/ \u5408\u5e76\u8fd9\u4e24\u4e2a\u8fde\u901a\u5206\u91cf\n mst_weight += edge.weight;\n edges_count++;\n }\n }\n\n if (edges_count == V - 1) { \/\/ \u5982\u679c\u5f62\u6210\u4e86\u5305\u542b\u6240\u6709 V \u4e2a\u8282\u70b9\u4e14 V-1 \u6761\u8fb9\u7684\u6811\n return mst_weight;\n } else {\n return -1; \/\/ \u56fe\u4e0d\u8fde\u901a\uff0c\u65e0\u6cd5\u5f62\u6210\u751f\u6210\u6811\n }\n}\n\n\/*\n\/\/ \u793a\u4f8b\u4f7f\u7528\nint main() {\n int V = 4; \/\/ \u8282\u70b9\u6570\u91cf (1-indexed)\n std::vector<Edge_Kruskal> edges = {\n {1, 2, 1}, {1, 3, 3}, {1, 4, 4},\n {2, 3, 1}, {3, 4, 2}\n };\n \/\/ Expected MST edges: (1,2,1), (2,3,1), (3,4,2)\n \/\/ MST weight: 1 + 1 + 2 = 4\n\n long long weight = kruskal(V, edges);\n if (weight != -1) {\n std::cout << "Minimum Spanning Tree weight: " << weight << std::endl; \/\/ Output: 4\n } else {\n std::cout << "Graph is not connected.\\n";\n }\n return 0;\n}\n*\/<\/code><\/pre>\n1.10.2 Prim \u7b97\u6cd5 (\u666e\u91cc\u59c6)<\/h4>\n
#include <vector>\n#include <queue>\n#include <limits> \/\/ for std::numeric_limits\n#include <utility> \/\/ for std::pair\n\nconst int INF_PRIM = std::numeric_limits<int>::max();\n\n\/\/ \u56fe\u7684\u90bb\u63a5\u8868\u8868\u793a: pair<int, int> {\u76ee\u6807\u8282\u70b9, \u8fb9\u6743}\nstd::vector<std::vector<std::pair<int, int>>> adj_prim;\nstd::vector<int> min_cost_prim; \/\/ \u5b58\u50a8\u8282\u70b9\u5230 MST \u7684\u6700\u5c0f\u8fb9\u6743\nstd::vector<bool> in_mst_prim; \/\/ \u6807\u8bb0\u8282\u70b9\u662f\u5426\u5df2\u52a0\u5165 MST\n\n\/\/ Prim \u7b97\u6cd5\u6a21\u677f\n\/\/ V: \u8282\u70b9\u6570\u91cf\n\/\/ start_node: \u8d77\u59cb\u8282\u70b9 (\u4efb\u610f\u9009\u62e9)\n\/\/ \u8fd4\u56de MST \u7684\u603b\u6743\u91cd\uff0c\u5982\u679c\u56fe\u4e0d\u8fde\u901a\u5219\u8fd4\u56de -1 (\u6216 INF)\nlong long prim(int V, int start_node) {\n min_cost_prim.assign(V + 1, INF_PRIM);\n in_mst_prim.assign(V + 1, false);\n\n long long mst_weight = 0;\n int edges_count = 0;\n\n \/\/ \u4f18\u5148\u961f\u5217\u5b58\u50a8 {\u6743\u91cd, \u8282\u70b9}\uff0c\u6309\u6743\u91cd\u4ece\u5c0f\u5230\u5927\u6392\u5e8f\n std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;\n\n min_cost_prim[start_node] = 0;\n pq.push({0, start_node}); \/\/ {\u5f53\u524d\u8282\u70b9\u5230MST\u7684\u6700\u5c0f\u6743\u503c, \u8282\u70b9}\n\n while (!pq.empty() && edges_count < V) {\n int u_cost = pq.top().first;\n int u = pq.top().second;\n pq.pop();\n\n if (in_mst_prim[u]) { \/\/ \u5982\u679c\u8282\u70b9\u5df2\u5728MST\u4e2d\uff0c\u8df3\u8fc7\n continue;\n }\n\n in_mst_prim[u] = true;\n mst_weight += u_cost;\n edges_count++;\n\n for (auto& edge : adj_prim[u]) {\n int v = edge.first;\n int weight = edge.second;\n\n \/\/ \u5982\u679c v \u4e0d\u5728 MST \u4e2d\uff0c\u5e76\u4e14\u901a\u8fc7 u \u5230 v \u7684\u8fb9\u6743\u91cd\u66f4\u5c0f\n if (!in_mst_prim[v] && weight < min_cost_prim[v]) {\n min_cost_prim[v] = weight;\n pq.push({min_cost_prim[v], v});\n }\n }\n }\n\n if (edges_count == V) { \/\/ \u786e\u4fdd\u6240\u6709\u8282\u70b9\u90fd\u52a0\u5165 MST\n return mst_weight;\n } else {\n return -1; \/\/ \u56fe\u4e0d\u8fde\u901a\n }\n}\n\n\/*\n\/\/ \u793a\u4f8b\u4f7f\u7528\nint main() {\n int V = 4; \/\/ \u8282\u70b9\u6570\u91cf (1-indexed)\n adj_prim.resize(V + 1);\n\n \/\/ \u6dfb\u52a0\u8fb9: u <-> v, weight (\u65e0\u5411\u56fe\uff0c\u6240\u4ee5\u8981\u52a0\u4e24\u6b21)\n adj_prim[1].push_back({2, 1}); adj_prim[2].push_back({1, 1});\n adj_prim[1].push_back({3, 3}); adj_prim[3].push_back({1, 3});\n adj_prim[1].push_back({4, 4}); adj_prim[4].push_back({1, 4});\n adj_prim[2].push_back({3, 1}); adj_prim[3].push_back({2, 1});\n adj_prim[3].push_back({4, 2}); adj_prim[4].push_back({3, 2});\n\n long long weight = prim(V, 1); \/\/ \u4ece\u8282\u70b91\u5f00\u59cbPrim\n\n if (weight != -1) {\n std::cout << "Minimum Spanning Tree weight: " << weight << std::endl; \/\/ Output: 4\n } else {\n std::cout << "Graph is not connected.\\n";\n }\n return 0;\n}\n*\/<\/code><\/pre>\n1.11 \u56fe\u8bba\uff1a\u62d3\u6251\u6392\u5e8f (Topological Sort)<\/h3>\n
u<\/code> \u90fd\u51fa\u73b0\u5728 v<\/code> \u7684\u524d\u9762\u3002<\/p>\n#include <vector>\n#include <queue>\n#include <iostream>\n#include <algorithm> \/\/ for std::sort (if needed, but for topological sort it's usually BFS\/DFS)\n\n\/\/ \u56fe\u7684\u90bb\u63a5\u8868\u8868\u793a\nstd::vector<std::vector<int>> adj_topo;\nstd::vector<int> in_degree_topo; \/\/ \u8bb0\u5f55\u6bcf\u4e2a\u8282\u70b9\u7684\u5165\u5ea6\n\n\/\/ \u62d3\u6251\u6392\u5e8f\u6a21\u677f (Kahn's Algorithm - BFS)\n\/\/ V: \u8282\u70b9\u6570\u91cf\n\/\/ \u8fd4\u56de\u62d3\u6251\u6392\u5e8f\u7ed3\u679c\uff0c\u5982\u679c\u5b58\u5728\u73af\u5219\u8fd4\u56de\u7a7a vector\nstd::vector<int> topologicalSort(int V) {\n std::vector<int> result;\n std::queue<int> q;\n\n \/\/ 1. \u521d\u59cb\u5316\u5165\u5ea6\n in_degree_topo.assign(V + 1, 0); \/\/ \u5047\u8bbe\u8282\u70b9\u4ece1\u5f00\u59cb\n for (int u = 1; u <= V; ++u) {\n for (int v : adj_topo[u]) {\n in_degree_topo[v]++;\n }\n }\n\n \/\/ 2. \u5c06\u6240\u6709\u5165\u5ea6\u4e3a0\u7684\u8282\u70b9\u52a0\u5165\u961f\u5217\n for (int i = 1; i <= V; ++i) {\n if (in_degree_topo[i] == 0) {\n q.push(i);\n }\n }\n\n \/\/ 3. BFS \u904d\u5386\n while (!q.empty()) {\n int u = q.front();\n q.pop();\n result.push_back(u);\n\n for (int v : adj_topo[u]) {\n in_degree_topo[v]--; \/\/ \u79fb\u9664 u \u53ca\u5176\u6240\u6709\u51fa\u8fb9\uff0c\u76f8\u5f53\u4e8e\u51cf\u5c11 v \u7684\u5165\u5ea6\n if (in_degree_topo[v] == 0) {\n q.push(v);\n }\n }\n }\n\n \/\/ 4. \u68c0\u67e5\u662f\u5426\u5b58\u5728\u73af (\u5982\u679c\u6392\u5e8f\u7684\u8282\u70b9\u6570\u91cf\u4e0d\u7b49\u4e8e\u603b\u8282\u70b9\u6570\uff0c\u5219\u5b58\u5728\u73af)\n if (result.size() != V) {\n \/\/ std::cout << "Graph contains a cycle! No topological sort possible.\\n";\n return {}; \/\/ \u8fd4\u56de\u7a7a vector \u8868\u793a\u6709\u73af\n }\n return result;\n}\n\n\/*\n\/\/ \u793a\u4f8b\u4f7f\u7528\nint main() {\n int V = 6; \/\/ \u8282\u70b9\u6570\u91cf (1-indexed)\n adj_topo.resize(V + 1);\n\n \/\/ \u6dfb\u52a0\u6709\u5411\u8fb9 (u -> v)\n adj_topo[1].push_back(2);\n adj_topo[1].push_back(3);\n adj_topo[2].push_back(4);\n adj_topo[3].push_back(4);\n adj_topo[4].push_back(5);\n adj_topo[4].push_back(6);\n\n std::vector<int> sorted_nodes = topologicalSort(V);\n\n if (sorted_nodes.empty()) {\n std::cout << "Graph contains a cycle.\\n";\n } else {\n std::cout << "Topological Sort: ";\n for (int node : sorted_nodes) {\n std::cout << node << " ";\n }\n std::cout << std::endl; \/\/ Possible output: 1 2 3 4 5 6 (\u6216 1 3 2 4 5 6 \u7b49)\n }\n\n \/\/ \u793a\u4f8b\uff1a\u6709\u73af\u56fe\n adj_topo.assign(3 + 1, std::vector<int>());\n adj_topo[1].push_back(2);\n adj_topo[2].push_back(3);\n adj_topo[3].push_back(1); \/\/ \u5f62\u6210\u73af\n std::cout << "\\nTesting cyclic graph:\\n";\n sorted_nodes = topologicalSort(3);\n if (sorted_nodes.empty()) {\n std::cout << "Graph contains a cycle.\\n"; \/\/ Expected\n }\n return 0;\n}\n*\/<\/code><\/pre>\n1.12 \u56fe\u8bba\uff1a\u4e8c\u5206\u56fe\u5339\u914d (Bipartite Matching)<\/h3>\n
#include <vector>\n#include <iostream>\n\n\/\/ \u56fe\u7684\u90bb\u63a5\u8868\u8868\u793a (\u4ece\u5de6\u4fa7\u96c6\u5408\u6307\u5411\u53f3\u4fa7\u96c6\u5408\u7684\u8fb9)\nstd::vector<std::vector<int>> adj_bipartite;\nstd::vector<int> match_r; \/\/ match_r[v] = u \u8868\u793a\u53f3\u4fa7\u8282\u70b9 v \u5339\u914d\u4e86\u5de6\u4fa7\u8282\u70b9 u\nstd::vector<bool> visited_bipartite; \/\/ \u6bcf\u6b21 DFS \u8bbf\u95ee\u6807\u8bb0\n\n\/\/ \u5308\u7259\u5229\u7b97\u6cd5\u7684 DFS \u90e8\u5206\n\/\/ u: \u5f53\u524d\u5c1d\u8bd5\u5339\u914d\u7684\u5de6\u4fa7\u8282\u70b9\nbool dfs_bipartite_match(int u) {\n for (int v : adj_bipartite[u]) {\n if (!visited_bipartite[v]) { \/\/ \u5982\u679c\u53f3\u4fa7\u8282\u70b9 v \u672a\u88ab\u5f53\u524d DFS \u8bbf\u95ee\n visited_bipartite[v] = true;\n\n \/\/ \u5982\u679c v \u672a\u88ab\u5339\u914d\uff0c\u6216\u8005 v \u7684\u5339\u914d\u5bf9\u8c61\u53ef\u4ee5\u627e\u5230\u65b0\u7684\u5339\u914d\n if (match_r[v] == -1 || dfs_bipartite_match(match_r[v])) {\n match_r[v] = u; \/\/ \u5339\u914d\u6210\u529f\uff0c\u5c06 v \u5339\u914d\u7ed9 u\n return true;\n }\n }\n }\n return false; \/\/ \u65e0\u6cd5\u627e\u5230\u589e\u5e7f\u8def\u5f84\n}\n\n\/\/ \u4e8c\u5206\u56fe\u6700\u5927\u5339\u914d\u6a21\u677f (\u5308\u7259\u5229\u7b97\u6cd5)\n\/\/ num_left_nodes: \u5de6\u4fa7\u8282\u70b9\u6570\u91cf (\u5047\u8bbe\u4ece 1 \u5230 num_left_nodes)\n\/\/ num_right_nodes: \u53f3\u4fa7\u8282\u70b9\u6570\u91cf (\u5047\u8bbe\u4ece 1 \u5230 num_right_nodes)\n\/\/ adj_bipartite: \u90bb\u63a5\u8868\uff0cadj_bipartite[u] \u5b58\u50a8\u4e0e\u5de6\u4fa7\u8282\u70b9 u \u76f8\u8fde\u7684\u53f3\u4fa7\u8282\u70b9\nint maxBipartiteMatch(int num_left_nodes, int num_right_nodes) {\n match_r.assign(num_right_nodes + 1, -1); \/\/ \u521d\u59cb\u5316\u6240\u6709\u53f3\u4fa7\u8282\u70b9\u672a\u5339\u914d\n int result = 0; \/\/ \u5339\u914d\u6570\u91cf\n\n \/\/ \u904d\u5386\u5de6\u4fa7\u7684\u6bcf\u4e2a\u8282\u70b9\uff0c\u5c1d\u8bd5\u4e3a\u5176\u627e\u5230\u5339\u914d\n for (int u = 1; u <= num_left_nodes; ++u) {\n visited_bipartite.assign(num_right_nodes + 1, false); \/\/ \u6bcf\u6b21 DFS \u524d\u6e05\u7a7a\u8bbf\u95ee\u6807\u8bb0\n if (dfs_bipartite_match(u)) {\n result++;\n }\n }\n return result;\n}\n\n\/*\n\/\/ \u793a\u4f8b\u4f7f\u7528\nint main() {\n int num_left = 3; \/\/ \u5de6\u4fa7\u8282\u70b9 U = {1, 2, 3}\n int num_right = 3; \/\/ \u53f3\u4fa7\u8282\u70b9 V = {1, 2, 3}\n adj_bipartite.resize(num_left + 1);\n\n \/\/ \u6dfb\u52a0\u8fb9 (U -> V)\n adj_bipartite[1].push_back(2);\n adj_bipartite[2].push_back(1);\n adj_bipartite[2].push_back(3);\n adj_bipartite[3].push_back(2);\n\n int max_match = maxBipartiteMatch(num_left, num_right);\n std::cout << "Max Bipartite Matching: " << max_match << std::endl; \/\/ Output: 2 (e.g., 1->2, 2->1)\n return 0;\n}\n*\/<\/code><\/pre>\n1.13 \u5176\u4ed6\u5e38\u7528\u7b97\u6cd5\u8865\u5145<\/h3>\n
1.13.1 \u5e76\u67e5\u96c6 (Disjoint Set Union, DSU)<\/h4>\n
#include <vector>\n#include <numeric> \/\/ for std::iota\n\n\/\/ \u5e76\u67e5\u96c6\u6a21\u677f\nstd::vector<int> parent; \/\/ \u7236\u8282\u70b9\u6570\u7ec4\nstd::vector<int> sz; \/\/ \u96c6\u5408\u5927\u5c0f\u6570\u7ec4 (\u7528\u4e8e\u6309\u5927\u5c0f\u5408\u5e76\u4f18\u5316)\n\/\/ std::vector<int> rank; \/\/ \u79e9\u6570\u7ec4 (\u7528\u4e8e\u6309\u79e9\u5408\u5e76\u4f18\u5316\uff0c\u4e0e\u5927\u5c0f\u4f18\u5316\u4e8c\u9009\u4e00)\n\n\/\/ \u521d\u59cb\u5316\u5e76\u67e5\u96c6\nvoid init_dsu(int n) {\n parent.resize(n + 1);\n std::iota(parent.begin(), parent.end(), 0); \/\/ \u6bcf\u4e2a\u5143\u7d20\u7684\u7236\u8282\u70b9\u662f\u81ea\u5df1\n sz.assign(n + 1, 1); \/\/ \u6bcf\u4e2a\u96c6\u5408\u7684\u521d\u59cb\u5927\u5c0f\u662f1\n \/\/ rank.assign(n + 1, 0); \/\/ \u521d\u59cb\u5316\u79e9\u4e3a0\n}\n\n\/\/ \u67e5\u627e\u5143\u7d20 i \u6240\u5728\u7684\u96c6\u5408\u7684\u6839\u8282\u70b9\uff08\u5e26\u8def\u5f84\u538b\u7f29\uff09\nint find_set(int i) {\n if (parent[i] == i)\n return i;\n return parent[i] = find_set(parent[i]); \/\/ \u8def\u5f84\u538b\u7f29\n}\n\n\/\/ \u5408\u5e76\u5143\u7d20 i \u548c j \u6240\u5728\u7684\u96c6\u5408\uff08\u6309\u5927\u5c0f\u5408\u5e76\uff09\nvoid union_sets(int i, int j) {\n int root_i = find_set(i);\n int root_j = find_set(j);\n if (root_i != root_j) {\n \/\/ \u5c06\u5c0f\u96c6\u5408\u5408\u5e76\u5230\u5927\u96c6\u5408\n if (sz[root_i] < sz[root_j])\n std::swap(root_i, root_j);\n parent[root_j] = root_i;\n sz[root_i] += sz[root_j];\n }\n}\n\n\/\/ \u5408\u5e76\u5143\u7d20 i \u548c j \u6240\u5728\u7684\u96c6\u5408\uff08\u6309\u79e9\u5408\u5e76\uff09\n\/\/ void union_sets_rank(int i, int j) {\n\/\/ int root_i = find_set(i);\n\/\/ int root_j = find_set(j);\n\/\/ if (root_i != root_j) {\n\/\/ if (rank[root_i] < rank[root_j])\n\/\/ std::swap(root_i, root_j);\n\/\/ parent[root_j] = root_i;\n\/\/ if (rank[root_i] == rank[root_j])\n\/\/ rank[root_i]++;\n\/\/ }\n\/\/ }\n\n\/*\n\/\/ \u793a\u4f8b\u4f7f\u7528\nint main() {\n init_dsu(5); \/\/ \u521d\u59cb\u5316 5 \u4e2a\u5143\u7d20 (1-5)\n\n union_sets(1, 2);\n union_sets(3, 4);\n union_sets(1, 3); \/\/ \u5408\u5e76 (1,2) \u548c (3,4) \u6240\u5728\u7684\u96c6\u5408\n\n \/\/ \u68c0\u67e5\u8fde\u901a\u6027\n std::cout << "Are 1 and 4 connected? " << (find_set(1) == find_set(4) ? "Yes" : "No") << std::endl; \/\/ Output: Yes\n std::cout << "Are 1 and 5 connected? " << (find_set(1) == find_set(5) ? "Yes" : "No") << std::endl; \/\/ Output: No\n return 0;\n}\n*\/<\/code><\/pre>\n1.13.2 \u5feb\u901f\u5e42 (Binary Exponentiation \/ Exponentiation by Squaring)<\/h4>\n
#include <iostream>\n\n\/\/ \u5feb\u901f\u5e42\u6a21\u677f (\u8ba1\u7b97 base^exp % mod)\nlong long power(long long base, long long exp, long long mod) {\n long long res = 1;\n base %= mod; \/\/ \u786e\u4fdd base \u5728\u6a21\u6570\u8303\u56f4\u5185\n\n while (exp > 0) {\n if (exp % 2 == 1) { \/\/ \u5982\u679c\u6307\u6570\u662f\u5947\u6570\uff0c\u7d2f\u4e58 base\n res = (res * base) % mod;\n }\n base = (base * base) % mod; \/\/ base \u81ea\u4e58\n exp \/= 2; \/\/ \u6307\u6570\u51cf\u534a\n }\n return res;\n}\n\n\/\/ \u5feb\u901f\u5e42\u6a21\u677f (\u8ba1\u7b97 base^exp\uff0c\u4e0d\u5e26\u6a21\u6570)\nlong long power(long long base, long long exp) {\n long long res = 1;\n while (exp > 0) {\n if (exp % 2 == 1) {\n res *= base;\n }\n base *= base;\n exp \/= 2;\n }\n return res;\n}\n\n\/*\n\/\/ \u793a\u4f8b\u4f7f\u7528\nint main() {\n std::cout << "2^10 % 1000 = " << power(2, 10, 1000) << std::endl; \/\/ Output: 24\n std::cout << "3^5 = " << power(3, 5) << std::endl; \/\/ Output: 243\n return 0;\n}\n*\/<\/code><\/pre>\n1.13.3 \u57c3\u62c9\u6258\u65af\u7279\u5c3c\u7b5b\u6cd5 (Sieve of Eratosthenes)<\/h4>\n
#include <vector>\n#include <iostream>\n\n\/\/ \u57c3\u62c9\u6258\u65af\u7279\u5c3c\u7b5b\u6cd5\u6a21\u677f\n\/\/ max_n: \u8981\u67e5\u627e\u7d20\u6570\u7684\u6700\u5927\u8303\u56f4\nstd::vector<bool> is_prime_sieve;\nstd::vector<int> primes_list; \/\/ \u5b58\u50a8\u627e\u5230\u7684\u7d20\u6570\n\nvoid sieve(int max_n) {\n is_prime_sieve.assign(max_n + 1, true); \/\/ \u5047\u8bbe\u6240\u6709\u6570\u90fd\u662f\u7d20\u6570\n is_prime_sieve[0] = is_prime_sieve[1] = false; \/\/ 0\u548c1\u4e0d\u662f\u7d20\u6570\n\n for (int p = 2; p * p <= max_n; ++p) { \/\/ \u904d\u5386\u5230 sqrt(max_n)\n if (is_prime_sieve[p]) {\n \/\/ \u5982\u679c p \u662f\u7d20\u6570\uff0c\u5219\u5176\u6240\u6709\u500d\u6570\u90fd\u4e0d\u662f\u7d20\u6570\n for (int i = p * p; i <= max_n; i += p) {\n is_prime_sieve[i] = false;\n }\n }\n }\n\n \/\/ \u6536\u96c6\u7d20\u6570\u5217\u8868\n primes_list.clear();\n for (int p = 2; p <= max_n; ++p) {\n if (is_prime_sieve[p]) {\n primes_list.push_back(p);\n }\n }\n}\n\n\/*\n\/\/ \u793a\u4f8b\u4f7f\u7528\nint main() {\n sieve(30);\n std::cout << "Primes up to 30: ";\n for (int p : primes_list) {\n std::cout << p << " ";\n }\n std::cout << std::endl; \/\/ Output: 2 3 5 7 11 13 17 19 23 29\n return 0;\n}\n*\/<\/code><\/pre>\n
\n2. \u8f93\u5165\u8f93\u51fa\u63a7\u5236\u7cbe\u5ea6<\/h2>\n
iomanip<\/code> \u5934\u6587\u4ef6\u4e2d\u7684\u51fd\u6570\u6765\u63a7\u5236\u6d6e\u70b9\u6570\u7684\u8f93\u51fa\u7cbe\u5ea6\u3002<\/p>\n#include <iostream>\n#include <iomanip> \/\/ \u5305\u542b\u8fd9\u4e2a\u5934\u6587\u4ef6\n\nint main() {\n double pi = 3.1415926535;\n double large_num = 12345.6789;\n double small_num = 0.000000123;\n\n \/\/ 1. \u9ed8\u8ba4\u8f93\u51fa\n std::cout << "Default: " << pi << std::endl; \/\/ 3.14159\n std::cout << "Default: " << large_num << std::endl; \/\/ 12345.7 (\u9ed8\u8ba4\u6709\u6548\u6570\u5b57)\n std::cout << "Default: " << small_num << std::endl; \/\/ 1.23e-07 (\u9ed8\u8ba4\u79d1\u5b66\u8ba1\u6570\u6cd5)\n\n \/\/ 2. \u8bbe\u7f6e\u603b\u6709\u6548\u6570\u5b57\u4f4d\u6570 (precision)\n \/\/ precision \u9ed8\u8ba4\u662f\u603b\u7684\u6709\u6548\u6570\u5b57\u4f4d\u6570\n std::cout << "\\nSet precision (total digits):\\n";\n std::cout << std::setprecision(3) << pi << std::endl; \/\/ 3.14\n std::cout << std::setprecision(5) << large_num << std::endl; \/\/ 12346\n std::cout << std::setprecision(2) << small_num << std::endl; \/\/ 1.2e-07\n\n \/\/ 3. \u8bbe\u7f6e\u5c0f\u6570\u70b9\u540e\u7684\u4f4d\u6570 (\u9700\u8981\u7ed3\u5408 fixed \u6216 scientific)\n \/\/ fixed: \u56fa\u5b9a\u5c0f\u6570\u4f4d\u6570\uff0c\u4e0d\u518d\u4f7f\u7528\u79d1\u5b66\u8ba1\u6570\u6cd5\n std::cout << "\\nSet precision (decimal places with fixed):\\n";\n std::cout << std::fixed << std::setprecision(2) << pi << std::endl; \/\/ 3.14\n std::cout << std::fixed << std::setprecision(4) << pi << std::endl; \/\/ 3.1416\n std::cout << std::fixed << std::setprecision(2) << large_num << std::endl; \/\/ 12345.68\n std::cout << std::fixed << std::setprecision(8) << small_num << std::endl; \/\/ 0.00000012\n\n \/\/ 4. \u4f7f\u7528\u79d1\u5b66\u8ba1\u6570\u6cd5 (scientific)\n std::cout << "\\nSet precision (scientific):\\n";\n std::cout << std::scientific << std::setprecision(5) << pi << std::endl; \/\/ 3.14159e+00\n std::cout << std::scientific << std::setprecision(3) << large_num << std::endl; \/\/ 1.235e+04\n std::cout << std::scientific << std::setprecision(5) << small_num << std::endl; \/\/ 1.23000e-07\n\n \/\/ 5. \u6062\u590d\u9ed8\u8ba4\u683c\u5f0f (\u4e00\u822c\u4e0d\u9700\u8981\uff0c\u4f46\u4e86\u89e3\u4e00\u4e0b)\n std::cout.unsetf(std::ios_base::floatfield); \/\/ \u79fb\u9664 fixed \u6216 scientific\n std::cout << std::setprecision(6); \/\/ \u6062\u590d\u9ed8\u8ba4\u7cbe\u5ea6\n\n std::cout << "\\nBack to default: " << pi << std::endl;\n\n \/\/ C \u98ce\u683c\u7684 printf \u4e5f\u80fd\u63a7\u5236\u7cbe\u5ea6\n printf("\\nUsing printf:\\n");\n printf("pi (2 decimal places): %.2f\\n", pi); \/\/ 3.14\n printf("pi (4 decimal places): %.4f\\n", pi); \/\/ 3.1416\n printf("large_num (no scientific, 2 decimal places): %.2f\\n", large_num); \/\/ 12345.68\n printf("small_num (scientific, 3 digits): %.3e\\n", small_num); \/\/ 1.230e-07\n\n return 0;\n}<\/code><\/pre>\n
\n3. String \u7c7b\u578b\u5e38\u7528\u65b9\u6cd5<\/h2>\n
string<\/code> \u7c7b\u578b\u5728 C++ \u4e2d\u662f\u5904\u7406\u5b57\u7b26\u4e32\u7684\u5f3a\u5927\u5de5\u5177\u3002<\/p>\n#include <iostream>\n#include <string>\n#include <vector> \/\/ for vector example\n\nint main() {\n std::string s1 = "Hello, World!";\n std::string s2 = "C++ Programming";\n std::string s3 = " Trim me ";\n\n \/\/ 1. \u6784\u9020\u51fd\u6570\n std::string empty_s; \/\/ \u7a7a\u5b57\u7b26\u4e32\n std::string copy_s = s1; \/\/ \u62f7\u8d1d\u6784\u9020\n std::string part_s(s1, 7, 5); \/\/ \u4ece s1 \u7684\u7d22\u5f15 7 \u5f00\u59cb\u53d6 5 \u4e2a\u5b57\u7b26 ("World")\n std::string char_s(5, 'x'); \/\/ 5 \u4e2a 'x' ("xxxxx")\n std::cout << "part_s: " << part_s << std::endl;\n std::cout << "char_s: " << char_s << std::endl;\n\n \/\/ 2. \u957f\u5ea6\u548c\u5bb9\u91cf\n std::cout << "s1.length(): " << s1.length() << std::endl; \/\/ 13\n std::cout << "s1.size(): " << s1.size() << std::endl; \/\/ 13 (\u540c length)\n std::cout << "s1.capacity(): " << s1.capacity() << std::endl; \/\/ >= 13 (\u5b9e\u9645\u5206\u914d\u5185\u5b58)\n std::cout << "empty_s.empty(): " << empty_s.empty() << std::endl; \/\/ 1 (true)\n\n \/\/ 3. \u8bbf\u95ee\u5b57\u7b26\n std::cout << "s1[0]: " << s1[0] << std::endl; \/\/ H\n std::cout << "s1.at(1): " << s1.at(1) << std::endl; \/\/ e (at() \u63d0\u4f9b\u8fb9\u754c\u68c0\u67e5)\n\n \/\/ 4. \u5b57\u7b26\u4e32\u62fc\u63a5\n std::string s4 = s1 + " " + s2;\n std::cout << "s4: " << s4 << std::endl; \/\/ "Hello, World! C++ Programming"\n s1.append(" Beautiful"); \/\/ "Hello, World! Beautiful"\n std::cout << "s1 after append: " << s1 << std::endl;\n\n \/\/ 5. \u5b50\u5b57\u7b26\u4e32\n std::string sub = s1.substr(7, 5); \/\/ \u4ece\u7d22\u5f15 7 \u5f00\u59cb\u53d6 5 \u4e2a\u5b57\u7b26\n std::cout << "s1.substr(7, 5): " << sub << std::endl; \/\/ "World"\n\n \/\/ 6. \u67e5\u627e\n size_t pos = s1.find("World");\n if (pos != std::string::npos) {\n std::cout << "'World' found at pos: " << pos << std::endl; \/\/ 7\n } else {\n std::cout << "'World' not found." << std::endl;\n }\n pos = s1.rfind("l"); \/\/ \u4ece\u540e\u5f80\u524d\u627e\n std::cout << "Last 'l' found at pos: " << pos << std::endl; \/\/ 9\n\n \/\/ 7. \u63d2\u5165\u548c\u5220\u9664\n s1.insert(0, "Greetings, "); \/\/ "Greetings, Hello, World! Beautiful"\n std::cout << "s1 after insert: " << s1 << std::endl;\n s1.erase(0, 11); \/\/ \u5220\u9664\u4ece\u7d22\u5f15 0 \u5f00\u59cb\u7684 11 \u4e2a\u5b57\u7b26\n std::cout << "s1 after erase: " << s1 << std::endl; \/\/ "Hello, World! Beautiful"\n\n \/\/ 8. \u66ff\u6362\n s1.replace(7, 5, "Earth"); \/\/ \u4ece\u7d22\u5f15 7 \u5f00\u59cb\u7684 5 \u4e2a\u5b57\u7b26\u66ff\u6362\u4e3a "Earth"\n std::cout << "s1 after replace: " << s1 << std::endl; \/\/ "Hello, Earth! Beautiful"\n\n \/\/ 9. \u6e05\u7a7a\n empty_s.clear();\n std::cout << "empty_s.empty() after clear: " << empty_s.empty() << std::endl;\n\n \/\/ 10. \u5b57\u7b26\u4e32\u4e0e\u6570\u5b57\u8f6c\u6362\n std::string num_str = "123";\n int num_int = std::stoi(num_str); \/\/ string to int\n std::cout << "stoi('123'): " << num_int << std::endl;\n std::string pi_str = "3.14159";\n double pi_double = std::stod(pi_str); \/\/ string to double\n std::cout << "stod('3.14159'): " << pi_double << std::endl;\n\n int another_int = 456;\n std::string another_str = std::to_string(another_int); \/\/ int to string\n std::cout << "to_string(456): " << another_str << std::endl;\n\n \/\/ 11. \u904d\u5386\u5b57\u7b26\u4e32\n std::cout << "Iterating s2: ";\n for (char c : s2) { \/\/ C++11 range-based for loop\n std::cout << c << " ";\n }\n std::cout << std::endl;\n for (size_t i = 0; i < s2.length(); ++i) { \/\/ \u4f20\u7edf for loop\n \/\/ std::cout << s2[i];\n }\n}<\/code><\/pre>\n
\n4. STL \u5bb9\u5668\u76f8\u5173\u65b9\u6cd5\u53ca\u793a\u4f8b<\/h2>\n
4.1
std::vector<\/code> (\u52a8\u6001\u6570\u7ec4)<\/h3>\n#include <iostream>\n#include <vector>\n#include <algorithm> \/\/ for std::sort, std::reverse etc.\n\nint main() {\n \/\/ 1. \u6784\u9020\n std::vector<int> v1; \/\/ \u7a7a vector\n std::vector<int> v2(5); \/\/ 5 \u4e2a\u5143\u7d20\uff0c\u521d\u59cb\u5316\u4e3a 0\n std::vector<int> v3(3, 100); \/\/ 3 \u4e2a\u5143\u7d20\uff0c\u521d\u59cb\u5316\u4e3a 100 -> {100, 100, 100}\n std::vector<int> v4 = {1, 2, 3, 4, 5}; \/\/ \u521d\u59cb\u5316\u5217\u8868\n\n std::cout << "v3: "; for (int x : v3) std::cout << x << " "; std::cout << std::endl; \/\/ 100 100 100\n\n \/\/ 2. \u6dfb\u52a0\/\u5220\u9664\u5143\u7d20\n v1.push_back(10); \/\/ \u5728\u672b\u5c3e\u6dfb\u52a0\n v1.push_back(20);\n v1.push_back(30);\n std::cout << "v1 after push_back: "; for (int x : v1) std::cout << x << " "; std::cout << std::endl; \/\/ 10 20 30\n\n v1.pop_back(); \/\/ \u79fb\u9664\u672b\u5c3e\u5143\u7d20 (30)\n std::cout << "v1 after pop_back: "; for (int x : v1) std::cout << x << " "; std::cout << std::endl; \/\/ 10 20\n\n \/\/ 3. \u8bbf\u95ee\u5143\u7d20\n std::cout << "v1[0]: " << v1[0] << std::endl; \/\/ 10\n std::cout << "v1.at(1): " << v1.at(1) << std::endl; \/\/ 20 (\u5e26\u8fb9\u754c\u68c0\u67e5)\n std::cout << "v1.front(): " << v1.front() << std::endl; \/\/ 10\n std::cout << "v1.back(): " << v1.back() << std::endl; \/\/ 20\n\n \/\/ 4. \u5927\u5c0f\u4e0e\u5bb9\u91cf\n std::cout << "v1.size(): " << v1.size() << std::endl; \/\/ 2\n std::cout << "v1.capacity(): " << v1.capacity() << std::endl; \/\/ >= 2\n std::cout << "v1.empty(): " << v1.empty() << std::endl; \/\/ 0 (false)\n\n \/\/ 5. \u63d2\u5165\u548c\u5220\u9664\uff08\u901a\u8fc7\u8fed\u4ee3\u5668\uff09\n v4 = {1, 2, 3, 4, 5};\n v4.insert(v4.begin() + 2, 99); \/\/ \u5728\u7d22\u5f15 2 \u5904\u63d2\u5165 99 -> {1, 2, 99, 3, 4, 5}\n std::cout << "v4 after insert: "; for (int x : v4) std::cout << x << " "; std::cout << std::endl;\n\n v4.erase(v4.begin() + 2); \/\/ \u5220\u9664\u7d22\u5f15 2 \u5904\u7684\u5143\u7d20 (99) -> {1, 2, 3, 4, 5}\n std::cout << "v4 after erase: "; for (int x : v4) std::cout << x << " "; std::cout << std::endl;\n\n \/\/ 6. \u6e05\u7a7a\n v1.clear();\n std::cout << "v1.size() after clear: " << v1.size() << std::endl; \/\/ 0\n}<\/code><\/pre>\n4.2
std::map<\/code> (\u6709\u5e8f\u952e\u503c\u5bf9)<\/h3>\n#include <iostream>\n#include <map>\n#include <string>\n\nint main() {\n \/\/ 1. \u6784\u9020\n std::map<std::string, int> ages;\n\n \/\/ 2. \u63d2\u5165\u5143\u7d20\n ages["Alice"] = 30; \/\/ \u65b9\u5f0f\u4e00\uff1a\u4f7f\u7528 operator[]\n ages["Bob"] = 25;\n ages.insert({"Charlie", 35}); \/\/ \u65b9\u5f0f\u4e8c\uff1a\u4f7f\u7528 insert (pair \u6216 initializer_list)\n ages.emplace("David", 40); \/\/ \u65b9\u5f0f\u4e09\uff1a\u4f7f\u7528 emplace (\u66f4\u9ad8\u6548\uff0c\u907f\u514d\u4e34\u65f6\u5bf9\u8c61)\n\n \/\/ 3. \u8bbf\u95ee\u5143\u7d20\n std::cout << "Alice's age: " << ages["Alice"] << std::endl; \/\/ 30\n \/\/ \u5982\u679c\u952e\u4e0d\u5b58\u5728\uff0coperator[] \u4f1a\u63d2\u5165\u4e00\u4e2a\u9ed8\u8ba4\u503c\u5143\u7d20\n std::cout << "Eve's age (access via []): " << ages["Eve"] << std::endl; \/\/ 0 (int \u9ed8\u8ba4\u503c)\n \/\/ \u63a8\u8350\u4f7f\u7528 find \u68c0\u67e5\u662f\u5426\u5b58\u5728\uff0c\u907f\u514d\u4e0d\u5fc5\u8981\u7684\u63d2\u5165\n auto it = ages.find("Bob");\n if (it != ages.end()) {\n std::cout << "Bob's age (access via find): " << it->second << std::endl; \/\/ 25\n }\n\n \/\/ 4. \u904d\u5386\n std::cout << "\\nMap contents:\\n";\n for (const auto& pair : ages) { \/\/ C++11 range-based for\n std::cout << pair.first << ": " << pair.second << std::endl;\n }\n \/\/ \u952e\u6309\u5b57\u5178\u5e8f\u6392\u5e8f\u8f93\u51fa\uff1aAlice, Bob, Charlie, David, Eve\n\n \/\/ 5. \u67e5\u627e\u952e\u662f\u5426\u5b58\u5728\n std::cout << "Count for 'Alice': " << ages.count("Alice") << std::endl; \/\/ 1\n std::cout << "Count for 'Frank': " << ages.count("Frank") << std::endl; \/\/ 0\n\n \/\/ 6. \u5220\u9664\u5143\u7d20\n ages.erase("Eve"); \/\/ \u6839\u636e\u952e\u5220\u9664\n it = ages.find("Bob");\n if (it != ages.end()) {\n ages.erase(it); \/\/ \u6839\u636e\u8fed\u4ee3\u5668\u5220\u9664\n }\n std::cout << "\\nMap after erase:\\n";\n for (const auto& pair : ages) {\n std::cout << pair.first << ": " << pair.second << std::endl;\n }\n\n \/\/ 7. \u5927\u5c0f\u4e0e\u6e05\u7a7a\n std::cout << "Map size: " << ages.size() << std::endl; \/\/ 3\n ages.clear();\n std::cout << "Map empty: " << ages.empty() << std::endl; \/\/ 1 (true)\n}<\/code><\/pre>\n4.3
std::set<\/code> (\u6709\u5e8f\u4e0d\u91cd\u590d\u5143\u7d20\u96c6\u5408)<\/h3>\n#include <iostream>\n#include <set>\n\nint main() {\n \/\/ 1. \u6784\u9020\n std::set<int> mySet;\n\n \/\/ 2. \u63d2\u5165\u5143\u7d20\n mySet.insert(10);\n mySet.insert(30);\n mySet.insert(20);\n mySet.insert(10); \/\/ \u91cd\u590d\u5143\u7d20\u4e0d\u4f1a\u88ab\u63d2\u5165\n\n \/\/ 3. \u904d\u5386 (\u5143\u7d20\u81ea\u52a8\u6392\u5e8f)\n std::cout << "Set elements: ";\n for (int x : mySet) {\n std::cout << x << " "; \/\/ Output: 10 20 30\n }\n std::cout << std::endl;\n\n \/\/ 4. \u67e5\u627e\u5143\u7d20\n auto it = mySet.find(20);\n if (it != mySet.end()) {\n std::cout << "Found 20 in set." << std::endl;\n } else {\n std::cout << "20 not found." << std::endl;\n }\n std::cout << "Count for 30: " << mySet.count(30) << std::endl; \/\/ 1\n std::cout << "Count for 50: " << mySet.count(50) << std::endl; \/\/ 0\n\n \/\/ 5. \u5220\u9664\u5143\u7d20\n mySet.erase(10); \/\/ \u6839\u636e\u503c\u5220\u9664\n std::cout << "Set after erasing 10: ";\n for (int x : mySet) {\n std::cout << x << " "; \/\/ Output: 20 30\n }\n std::cout << std::endl;\n\n \/\/ 6. \u5927\u5c0f\u4e0e\u6e05\u7a7a\n std::cout << "Set size: " << mySet.size() << std::endl; \/\/ 2\n mySet.clear();\n std::cout << "Set empty: " << mySet.empty() << std::endl; \/\/ 1 (true)\n}<\/code><\/pre>\n4.4
std::unordered_map<\/code> (\u65e0\u5e8f\u952e\u503c\u5bf9)<\/h3>\n#include <iostream>\n#include <unordered_map>\n#include <string>\n\nint main() {\n \/\/ 1. \u6784\u9020\n std::unordered_map<std::string, int> scores;\n\n \/\/ 2. \u63d2\u5165\u5143\u7d20 (\u4e0e std::map \u7c7b\u4f3c)\n scores["Alice"] = 95;\n scores.insert({"Bob", 88});\n scores.emplace("Charlie", 76);\n\n \/\/ 3. \u8bbf\u95ee\u5143\u7d20 (\u4e0e std::map \u7c7b\u4f3c)\n std::cout << "Alice's score: " << scores["Alice"] << std::endl; \/\/ 95\n\n \/\/ 4. \u904d\u5386 (\u5143\u7d20\u987a\u5e8f\u4e0d\u786e\u5b9a)\n std::cout << "\\nUnordered Map contents:\\n";\n for (const auto& pair : scores) {\n std::cout << pair.first << ": " << pair.second << std::endl;\n }\n\n \/\/ 5. \u67e5\u627e\u952e\u662f\u5426\u5b58\u5728 (\u4e0e std::map \u7c7b\u4f3c)\n if (scores.count("Bob")) {\n std::cout << "Bob is in the map." << std::endl;\n }\n\n \/\/ 6. \u5220\u9664\u5143\u7d20 (\u4e0e std::map \u7c7b\u4f3c)\n scores.erase("Charlie");\n\n \/\/ 7. \u5927\u5c0f\u4e0e\u6e05\u7a7a\n std::cout << "Unordered Map size: " << scores.size() << std::endl; \/\/ 2\n scores.clear();\n}<\/code><\/pre>\n
\n5.
algorithm<\/code> \u5e93\u4e2d\u5e38\u7528\u65b9\u6cd5<\/h2>\nalgorithm<\/code> \u5934\u6587\u4ef6\u5305\u542b\u4e86\u5927\u91cf\u7684\u975e\u6210\u5458\u51fd\u6570\u6a21\u677f\uff0c\u7528\u4e8e\u5bf9\u5404\u79cd\u5bb9\u5668\u8fdb\u884c\u64cd\u4f5c\u3002<\/p>\n#include <iostream>\n#include <vector>\n#include <string>\n#include <algorithm> \/\/ \u6838\u5fc3\u7b97\u6cd5\u5e93\n#include <numeric> \/\/ for std::accumulate\n\nint main() {\n std::vector<int> vec = {5, 2, 8, 1, 9, 3};\n std::string str = "hello";\n\n \/\/ 1. `std::sort()`\n \/\/ \u5bf9\u5bb9\u5668\u7684\u5143\u7d20\u8fdb\u884c\u6392\u5e8f\u3002\u9ed8\u8ba4\u5347\u5e8f\u3002\n std::sort(vec.begin(), vec.end());\n std::cout << "Sorted vec: ";\n for (int x : vec) std::cout << x << " "; \/\/ Output: 1 2 3 5 8 9\n std::cout << std::endl;\n\n \/\/ \u81ea\u5b9a\u4e49\u6392\u5e8f (\u964d\u5e8f)\n std::sort(vec.begin(), vec.end(), std::greater<int>());\n std::cout << "Sorted vec (desc): ";\n for (int x : vec) std::cout << x << " "; \/\/ Output: 9 8 5 3 2 1\n std::cout << std::endl;\n\n \/\/ 2. `std::reverse()`\n \/\/ \u53cd\u8f6c\u5bb9\u5668\u4e2d\u5143\u7d20\u7684\u987a\u5e8f\u3002\n std::reverse(str.begin(), str.end());\n std::cout << "Reversed string: " << str << std::endl; \/\/ Output: olleh\n\n \/\/ 3. `std::min_element()` \/ `std::max_element()`\n \/\/ \u8fd4\u56de\u6307\u5411\u5e8f\u5217\u4e2d\u6700\u5c0f\/\u6700\u5927\u5143\u7d20\u7684\u8fed\u4ee3\u5668\u3002\n auto min_it = std::min_element(vec.begin(), vec.end());\n std::cout << "Min element: " << *min_it << std::endl; \/\/ Output: 1 (after re-sorting ascending first)\n auto max_it = std::max_element(vec.begin(), vec.end());\n std::cout << "Max element: " << *max_it << std::endl; \/\/ Output: 9\n\n \/\/ 4. `std::accumulate()` (\u5728 `<numeric>` \u4e2d)\n \/\/ \u5bf9\u5bb9\u5668\u4e2d\u7684\u5143\u7d20\u8fdb\u884c\u7d2f\u52a0\u3002\n int sum = std::accumulate(vec.begin(), vec.end(), 0); \/\/ 0 \u662f\u521d\u59cb\u503c\n std::cout << "Sum of vec elements: " << sum << std::endl; \/\/ Output: 30 (9+8+5+3+2+1)\n\n \/\/ 5. `std::count()` \/ `std::count_if()`\n \/\/ \u7edf\u8ba1\u67d0\u4e2a\u7279\u5b9a\u503c\u51fa\u73b0\u7684\u6b21\u6570 \/ \u7edf\u8ba1\u6ee1\u8db3\u67d0\u4e2a\u6761\u4ef6\u7684\u5143\u7d20\u6b21\u6570\u3002\n std::vector<int> count_vec = {1, 2, 2, 3, 2, 4};\n int num_twos = std::count(count_vec.begin(), count_vec.end(), 2);\n std::cout << "Number of 2s: " << num_twos << std::endl; \/\/ Output: 3\n\n int num_even = std::count_if(count_vec.begin(), count_vec.end(), [](int x){ return x % 2 == 0; });\n std::cout << "Number of even elements: " << num_even << std::endl; \/\/ Output: 4 (2, 2, 2, 4)\n\n \/\/ 6. `std::find()` \/ `std::find_if()`\n \/\/ \u67e5\u627e\u67d0\u4e2a\u7279\u5b9a\u503c \/ \u67e5\u627e\u6ee1\u8db3\u67d0\u4e2a\u6761\u4ef6\u7684\u7b2c\u4e00\u4e2a\u5143\u7d20\u3002\n auto found_it = std::find(count_vec.begin(), count_vec.end(), 3);\n if (found_it != count_vec.end()) {\n std::cout << "Found 3 at index: " << std::distance(count_vec.begin(), found_it) << std::endl; \/\/ Output: 3\n }\n\n auto found_odd = std::find_if(count_vec.begin(), count_vec.end(), [](int x){ return x % 2 != 0; });\n std::cout << "First odd element: " << *found_odd << std::endl; \/\/ Output: 1\n\n \/\/ 7. `std::lower_bound()` \/ `std::upper_bound()`\n \/\/ \u4ec5\u9002\u7528\u4e8e\u6709\u5e8f\u5e8f\u5217\u3002\n \/\/ lower_bound: \u8fd4\u56de\u6307\u5411\u7b2c\u4e00\u4e2a **\u4e0d\u5c0f\u4e8e** \u67d0\u4e2a\u503c\u7684\u5143\u7d20\u7684\u8fed\u4ee3\u5668\u3002\n \/\/ upper_bound: \u8fd4\u56de\u6307\u5411\u7b2c\u4e00\u4e2a **\u5927\u4e8e** \u67d0\u4e2a\u503c\u7684\u5143\u7d20\u7684\u8fed\u4ee3\u5668\u3002\n std::vector<int> sorted_vec = {1, 2, 2, 3, 4, 5};\n auto lb = std::lower_bound(sorted_vec.begin(), sorted_vec.end(), 2);\n std::cout << "lower_bound for 2: " << *lb << " at index " << std::distance(sorted_vec.begin(), lb) << std::endl; \/\/ Output: 2 at index 1\n\n auto ub = std::upper_bound(sorted_vec.begin(), sorted_vec.end(), 2);\n std::cout << "upper_bound for 2: " << *ub << " at index " << std::distance(sorted_vec.begin(), ub) << std::endl; \/\/ Output: 3 at index 3\n\n \/\/ 8. `std::fill()`\n \/\/ \u5c06\u6307\u5b9a\u8303\u56f4\u5185\u7684\u5143\u7d20\u586b\u5145\u4e3a\u67d0\u4e2a\u503c\u3002\n std::vector<int> fill_vec(5);\n std::fill(fill_vec.begin(), fill_vec.end(), 7);\n std::cout << "Filled vector: ";\n for (int x : fill_vec) std::cout << x << " "; \/\/ Output: 7 7 7 7 7\n std::cout << std::endl;\n\n \/\/ 9. `std::unique()`\n \/\/ \u79fb\u9664\u76f8\u90bb\u7684\u91cd\u590d\u5143\u7d20\uff08\u5e76\u4e0d\u80fd\u771f\u6b63\u6539\u53d8\u5bb9\u5668\u5927\u5c0f\uff0c\u53ea\u5c06\u4e0d\u91cd\u590d\u5143\u7d20\u79fb\u5230\u524d\u9762\uff0c\u8fd4\u56de\u4e00\u4e2a\u8fed\u4ee3\u5668\u6307\u5411\u65b0\u5e8f\u5217\u7684\u5c3e\u540e\uff09\u3002\n \/\/ \u901a\u5e38\u9700\u8981\u914d\u5408 `erase()` \u6765\u771f\u6b63\u5220\u9664\u3002\n std::vector<int> unique_vec = {1, 2, 2, 3, 3, 3, 4, 5, 5};\n auto last = std::unique(unique_vec.begin(), unique_vec.end());\n unique_vec.erase(last, unique_vec.end());\n std::cout << "Unique elements: ";\n for (int x : unique_vec) std::cout << x << " "; \/\/ Output: 1 2 3 4 5\n std::cout << std::endl;\n\n \/\/ 10. `std::next_permutation()` \/ `std::prev_permutation()`\n \/\/ \u751f\u6210\u5e8f\u5217\u7684\u4e0b\u4e00\u4e2a\/\u4e0a\u4e00\u4e2a\u5b57\u5178\u5e8f\u6392\u5217\u3002\n std::string p_str = "bac";\n std::sort(p_str.begin(), p_str.end()); \/\/ \u5fc5\u987b\u5148\u6392\u5e8f\u5230\u6700\u5c0f\u6392\u5217\n std::cout << "Permutations of 'bac':\\n";\n do {\n std::cout << p_str << std::endl;\n } while (std::next_permutation(p_str.begin(), p_str.end()));\n \/\/ Output: abc, acb, bac, bca, cab, cba\n\n \/\/ 11. `std::swap()`\n \/\/ \u4ea4\u6362\u4e24\u4e2a\u53d8\u91cf\u7684\u503c\u3002\n int a = 10, b = 20;\n std::swap(a, b);\n std::cout << "a: " << a << ", b: " << b << std::endl; \/\/ Output: a: 20, b: 10\n}<\/code><\/pre>\n\u8865\u5145<\/h2>\n
#include <vector> \/\/ \u5305\u542bvector\u5bb9\u5668\n#include <string> \/\/ \u5305\u542bstring\u7c7b\u578b\n#include <iostream> \/\/ \u5305\u542b\u8f93\u5165\u8f93\u51fa\u6d41\uff0c\u7528\u4e8e\u793a\u4f8b\u6216\u8c03\u8bd5\n\/**\n * @brief \u8ba1\u7b97KMP\u7b97\u6cd5\u7684LPS (Longest Proper Prefix which is also a Suffix) \u6570\u7ec4\u3002\n * LPS\u6570\u7ec4\uff08\u4e5f\u79f0\u4e3a\u524d\u7f00\u51fd\u6570\u6216\u90e8\u5206\u5339\u914d\u8868\uff09\u662fKMP\u7b97\u6cd5\u7684\u6838\u5fc3\uff0c\n * \u5b83\u5e2e\u52a9\u6211\u4eec\u5728\u53d1\u751f\u4e0d\u5339\u914d\u65f6\u77e5\u9053\u5e94\u8be5\u201c\u8df3\u8fc7\u201d\u591a\u5c11\u5b57\u7b26\uff0c\u907f\u514d\u91cd\u590d\u6bd4\u8f83\u3002\n * lps[i] \u8868\u793a pattern[0...i] \u8fd9\u4e2a\u5b50\u4e32\u7684\u6700\u957f\u76f8\u7b49\u524d\u7f00\u548c\u540e\u7f00\u7684\u957f\u5ea6\u3002\n *\n * @param pattern \u8981\u8ba1\u7b97LPS\u6570\u7ec4\u7684\u6a21\u5f0f\u5b57\u7b26\u4e32\u3002\n * @return vector<int> LPS\u6570\u7ec4\u3002\n *\/\nvector<int> computeLPS(string pattern) {\n int m = pattern.length(); \/\/ \u83b7\u53d6\u6a21\u5f0f\u5b57\u7b26\u4e32\u7684\u957f\u5ea6\n vector<int> lps(m, 0); \/\/ \u521d\u59cb\u5316LPS\u6570\u7ec4\uff0c\u5927\u5c0f\u4e0e\u6a21\u5f0f\u5b57\u7b26\u4e32\u76f8\u540c\uff0c\u6240\u6709\u5143\u7d20\u521d\u59cb\u4e3a0\n\n \/\/ len \u53d8\u91cf\u8868\u793a\u5f53\u524d\u5df2\u5339\u914d\u7684\u6700\u957f\u516c\u5171\u524d\u7f00\u548c\u540e\u7f00\u7684\u957f\u5ea6\u3002\n \/\/ \u5728\u6784\u5efaLPS\u6570\u7ec4\u65f6\uff0c\u5b83\u4e5f\u4ee3\u8868\u7740 pattern[0...len-1] \u662f pattern[0...i] \u7684\u4e00\u4e2a\u524d\u7f00\uff0c\n \/\/ \u5e76\u4e14\u8fd9\u4e2a\u524d\u7f00\u4e5f\u7b49\u4e8e pattern[i - len + 1 ... i] \u8fd9\u4e2a\u540e\u7f00\u7684\u957f\u5ea6\u3002\n int len = 0; \n\n \/\/ i \u53d8\u91cf\u7528\u4e8e\u904d\u5386\u6a21\u5f0f\u5b57\u7b26\u4e32\uff0c\u4ece\u7d22\u5f151\u5f00\u59cb\uff0c\u56e0\u4e3alps[0]\u59cb\u7ec8\u4e3a0\uff08\u5355\u4e2a\u5b57\u7b26\u6ca1\u6709\u771f\u524d\u7f00\u548c\u771f\u540e\u7f00\uff09\u3002\n int i = 1; \n\n \/\/ \u904d\u5386\u6a21\u5f0f\u5b57\u7b26\u4e32\u7684\u6bcf\u4e2a\u5b57\u7b26\u6765\u586b\u5145LPS\u6570\u7ec4\n while (i < m) {\n \/\/ \u60c5\u51b51\uff1a\u5f53\u524d\u5b57\u7b26 pattern[i] \u4e0e pattern[len] \u5339\u914d\n \/\/ \u8fd9\u610f\u5473\u7740\u6211\u4eec\u53ef\u4ee5\u5c06\u5f53\u524d\u7684\u6700\u957f\u516c\u5171\u524d\u7f00\u540e\u7f00\u7684\u957f\u5ea6\u589e\u52a01\n if (pattern[i] == pattern[len]) {\n len++; \/\/ \u957f\u5ea6\u52a01\n lps[i] = len; \/\/ \u66f4\u65b0 lps[i] \u4e3a\u65b0\u7684\u957f\u5ea6\n i++; \/\/ \u79fb\u52a8\u5230\u6a21\u5f0f\u5b57\u7b26\u4e32\u7684\u4e0b\u4e00\u4e2a\u5b57\u7b26\n } \n \/\/ \u60c5\u51b52\uff1a\u5f53\u524d\u5b57\u7b26 pattern[i] \u4e0e pattern[len] \u4e0d\u5339\u914d\n else {\n \/\/ \u5982\u679c len \u4e0d\u4e3a0\uff0c\u8bf4\u660e\u4e4b\u524d\u6709\u5339\u914d\u7684\u524d\u7f00\u540e\u7f00\uff0c\u73b0\u5728\u53d1\u751f\u4e0d\u5339\u914d\uff0c\n \/\/ \u6211\u4eec\u9700\u8981\u201c\u56de\u6eaf\u201dlen\uff0c\u5c06\u5176\u8bbe\u7f6e\u4e3a pattern[len-1] \u5bf9\u5e94\u7684LPS\u503c\u3002\n \/\/ \u8fd9\u6837\uff0c\u6211\u4eec\u5c1d\u8bd5\u5bfb\u627e\u4e00\u4e2a\u66f4\u77ed\u7684\u3001\u4f46\u662f\u4ecd\u7136\u662fpattern[0...i-1]\u524d\u7f00\u540e\u7f00\u7684\u5b50\u4e32\uff0c\n \/\/ \u6765\u4f5c\u4e3a\u65b0\u7684\u5339\u914d\u8d77\u70b9\u3002\n if (len != 0) {\n len = lps[len - 1]; \n \/\/ \u6ce8\u610f\uff1a\u8fd9\u91cc i \u4e0d\u53d8\uff0c\u56e0\u4e3a\u6211\u4eec\u53ea\u662f\u6539\u53d8\u4e86 len \u7684\u503c\uff0c\n \/\/ \u9700\u8981\u7528\u65b0\u7684 len \u503c\u7ee7\u7eed\u4e0e pattern[i] \u6bd4\u8f83\u3002\n } \n \/\/ \u5982\u679c len \u5df2\u7ecf\u4e3a0\uff08\u5373 pattern[0] \u5c31\u4e0d\u5339\u914d\uff0c\u6216\u8005\u5df2\u7ecf\u56de\u6eaf\u5230\u8d77\u70b9\uff09\uff0c\n \/\/ \u8fd9\u610f\u5473\u7740\u6ca1\u6709\u66f4\u77ed\u7684\u516c\u5171\u524d\u7f00\u540e\u7f00\u4e86\u3002\n else {\n lps[i] = 0; \/\/ lps[i] \u8bbe\u4e3a0\n i++; \/\/ \u79fb\u52a8\u5230\u6a21\u5f0f\u5b57\u7b26\u4e32\u7684\u4e0b\u4e00\u4e2a\u5b57\u7b26\n }\n }\n }\n\n return lps; \/\/ \u8fd4\u56de\u8ba1\u7b97\u597d\u7684LPS\u6570\u7ec4\n}\n\/**\n * @brief \u4f7f\u7528KMP\u7b97\u6cd5\u5728\u6587\u672c\u5b57\u7b26\u4e32\u4e2d\u67e5\u627e\u6a21\u5f0f\u5b57\u7b26\u4e32\u7684\u6240\u6709\u51fa\u73b0\u4f4d\u7f6e\u3002\n * KMP\u7b97\u6cd5\u901a\u8fc7\u5229\u7528\u6a21\u5f0f\u5b57\u7b26\u4e32\u81ea\u8eab\u7684\u7279\u6027\uff08LPS\u6570\u7ec4\uff09\u6765\u907f\u514d\u5728\u5339\u914d\u5931\u8d25\u65f6\n * \u5bf9\u6587\u672c\u5b57\u7b26\u4e32\u6307\u9488\u7684\u56de\u6eaf\uff0c\u4ece\u800c\u5b9e\u73b0\u9ad8\u6548\u7684\u67e5\u627e\u3002\n *\n * @param text \u8981\u641c\u7d22\u7684\u6587\u672c\u5b57\u7b26\u4e32\u3002\n * @param pattern \u8981\u67e5\u627e\u7684\u6a21\u5f0f\u5b57\u7b26\u4e32\u3002\n * @return vector<int> \u5305\u542b\u6a21\u5f0f\u5b57\u7b26\u4e32\u5728\u6587\u672c\u4e2d\u6240\u6709\u8d77\u59cb\u7d22\u5f15\u7684\u5217\u8868\u3002\n *\/\nvector<int> KMP(string text, string pattern) {\n vector<int> result; \/\/ \u5b58\u50a8\u6240\u6709\u627e\u5230\u7684\u5339\u914d\u7684\u8d77\u59cb\u7d22\u5f15\n \/\/ \u8c03\u7528 computeLPS \u51fd\u6570\u9884\u5904\u7406\u6a21\u5f0f\u5b57\u7b26\u4e32\uff0c\u83b7\u53d6LPS\u6570\u7ec4\n vector<int> lps = computeLPS(pattern); \n\n int n = text.length(); \/\/ \u6587\u672c\u5b57\u7b26\u4e32\u7684\u957f\u5ea6\n int m = pattern.length(); \/\/ \u6a21\u5f0f\u5b57\u7b26\u4e32\u7684\u957f\u5ea6\n\n \/\/ i \u662f\u6587\u672c\u5b57\u7b26\u4e32 text \u7684\u5f53\u524d\u5b57\u7b26\u7d22\u5f15\n \/\/ j \u662f\u6a21\u5f0f\u5b57\u7b26\u4e32 pattern \u7684\u5f53\u524d\u5b57\u7b26\u7d22\u5f15\uff08\u4e5f\u8868\u793a\u5df2\u5339\u914d\u7684\u5b57\u7b26\u6570\u91cf\uff09\n int i = 0, j = 0; \n\n \/\/ \u904d\u5386\u6587\u672c\u5b57\u7b26\u4e32\uff0c\u76f4\u5230\u6587\u672c\u6307\u9488\u5230\u8fbe\u672b\u5c3e\n while (i < n) {\n \/\/ \u60c5\u51b51\uff1a\u5f53\u524d\u5b57\u7b26 text[i] \u4e0e pattern[j] \u5339\u914d\n if (pattern[j] == text[i]) {\n i++; \/\/ \u6587\u672c\u6307\u9488\u5411\u524d\u79fb\u52a8\n j++; \/\/ \u6a21\u5f0f\u6307\u9488\u5411\u524d\u79fb\u52a8\n }\n \/\/ \u60c5\u51b52\uff1a\u6a21\u5f0f\u5b57\u7b26\u4e32\u5b8c\u5168\u5339\u914d\uff08j \u8fbe\u5230\u4e86\u6a21\u5f0f\u7684\u957f\u5ea6 m\uff09\n if (j == m) {\n \/\/ \u627e\u5230\u4e00\u4e2a\u5339\u914d\uff0c\u5176\u8d77\u59cb\u7d22\u5f15\u4e3a text[i - j]\n result.push_back(i - j); \n \/\/ \u5229\u7528LPS\u6570\u7ec4\u8fdb\u884c\u6a21\u5f0f\u5b57\u7b26\u4e32\u7684\u201c\u8df3\u8dc3\u201d\uff1a\n \/\/ j \u56de\u6eaf\u5230 lps[j-1] \u7684\u4f4d\u7f6e\uff0c\u8fd9\u610f\u5473\u7740\u6211\u4eec\u5df2\u7ecf\u5339\u914d\u7684\u90e8\u5206\n \/\/ pattern[0...j-1] \u7684\u6700\u957f\u516c\u5171\u524d\u7f00\u540e\u7f00\u662f pattern[0...lps[j-1]-1]\u3002\n \/\/ \u6211\u4eec\u53ef\u4ee5\u76f4\u63a5\u4ece\u8fd9\u4e2a\u4f4d\u7f6e\u7ee7\u7eed\u5339\u914d\uff0c\u65e0\u9700\u4ece\u5934\u5f00\u59cb\u3002\n j = lps[j - 1]; \n } \n \/\/ \u60c5\u51b53\uff1a\u5f53\u524d\u5b57\u7b26\u4e0d\u5339\u914d\uff08pattern[j] != text[i]\uff09\uff0c\u4e14\u6587\u672c\u6307\u9488\u8fd8\u5728\u6587\u672c\u8303\u56f4\u5185\n else if (i < n && pattern[j] != text[i]) {\n \/\/ \u5982\u679c\u6a21\u5f0f\u6307\u9488 j \u4e0d\u4e3a0\uff0c\u8bf4\u660e\u4e4b\u524d\u6709\u90e8\u5206\u5339\u914d\uff0c\u73b0\u5728\u53d1\u751f\u4e0d\u5339\u914d\u3002\n \/\/ \u6211\u4eec\u53ef\u4ee5\u5229\u7528LPS\u6570\u7ec4\u8fdb\u884c\u6a21\u5f0f\u5b57\u7b26\u4e32\u7684\u201c\u8df3\u8dc3\u201d\uff1a\n \/\/ \u5c06\u6a21\u5f0f\u6307\u9488 j \u8bbe\u7f6e\u4e3a lps[j-1]\uff0c\u8fd9\u6837\u53ef\u4ee5\u907f\u514d\u4e0d\u5fc5\u8981\u7684\u56de\u6eaf\u548c\u91cd\u590d\u6bd4\u8f83\u3002\n if (j != 0) {\n j = lps[j - 1];\n } \n \/\/ \u5982\u679c\u6a21\u5f0f\u6307\u9488 j \u5df2\u7ecf\u4e3a0\uff0c\u8fd9\u610f\u5473\u7740 pattern[0] \u5c31\u4e0d\u5339\u914d\u5f53\u524d text[i]\uff0c\n \/\/ \u53ea\u80fd\u7b80\u5355\u5730\u5c06\u6587\u672c\u6307\u9488\u5411\u524d\u79fb\u52a8\uff0c\u6a21\u5f0f\u6307\u9488 j \u4fdd\u63010\u3002\n else {\n i++;\n }\n }\n }\n return result; \/\/ \u8fd4\u56de\u6240\u6709\u5339\u914d\u7684\u8d77\u59cb\u7d22\u5f15\u5217\u8868\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"