📚 C++的世界

C++ 基础知识与常用库函数 一、输入输出 1.1 cin 与 cout cin 和 cout 是 C++ 标准库提供的输入输出流对象。 cin 读取字符串：遇到空格或回车停止，只读取一个单词。 1 2 string s; cin >> s; // 输入 "hello world"，s = "hello" 读取整行字符串：使用 getline(cin, s)。 1 2 string s; getline(cin, s); // 输入 "hello world"，s = "hello world" 混合输入：cin >> n 后使用 getline 需要清除缓冲区。 1 2 3 4 5 int n; cin >> n; cin.ignore(); // 清除换行符 string s; getline(cin, s); 1.2 输出精度控制 使用 <iomanip> 库的 fixed 和 setprecision 控制浮点数输出精度。 1 2 3 #include <iomanip> double res = 3.1415926; cout << fixed << setprecision(2) << res << endl; // 3.14（四舍五入） 二、常见基础知识 2.1 ASCII 码 字符 ASCII 值 ‘0’ 48 ‘A’ 65 ‘a’ 97 大小写转换：大小写字母 ASCII 值相差 32。 ...

vector - 动态数组 std::vector 是算法竞赛中最常用的序列容器，提供O(1) 随机访问和均摊 O(1) 尾部插入。掌握 C++11 特性，能让你的代码更快更简洁，且在蓝桥杯考场上编译通过。 竞赛中的核心考点 操作 时间复杂度 竞赛要点 随机访问 O(1) 替代普通数组，支持动态扩容 尾部 push/pop 均摊 O(1) 用作栈 (stack) 中间插入/删除 O(n) 避免在循环中频繁使用 reserve O(n) 预处理避免 reallocation lower_bound O(log n) 配合 sort 实现二分查找 一、初始化与构造 1.1 竞赛常用初始化 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 方法1: 指定大小并初始化（最常用） vector<int> a(n); // n个0 vector<int> b(n, -1); // n个-1，常用于初始化DP数组 // 方法2: C++11 极简读入（推荐！） int n; cin >> n; vector<int> c(n); for (auto& x : c) { cin >> x; // 引用读入，避免拷贝 } // 方法3: 从数组构造 int arr[] = {1, 2, 3, 4, 5}; vector<int> d(arr, arr + 5); // 方法4: C++11 列表初始化 vector<int> e = {1, 2, 3, 4, 5}; vector<pair<int, int>> edges = {{1, 2}, {2, 3}, {3, 4}}; // 方法5: 二维vector（邻接表、矩阵） vector<vector<int>> g(n); // n个空vector，用于邻接表 vector<vector<int>> mat(n, vector<int>(m)); // n×m矩阵，默认0初始化 return 0; } 1.2 预分配空间 - 避免 TLE 1 2 3 4 5 6 7 8 9 10 11 12 13 14 // 错误示范：频繁push_back导致多次reallocation vector<int> v; for (int i = 0; i < 1e6; i++) { v.push_back(i); // 可能触发多次扩容，浪费时间 } // 正确做法：预先reserve vector<int> v; v.reserve(1e6); // 一次性分配足够空间 for (int i = 0; i < 1e6; i++) { v.push_back(i); // 不会触发reallocation } 二、emplace_back vs push_back 2.1 性能对比 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 struct Node { int x, y, w; Node(int _x, int _y, int _w) : x(_x), y(_y), w(_w) {} }; vector<Node> v; v.reserve(100000); // push_back: 构造临时对象 + 移动/拷贝 for (int i = 0; i < n; i++) { v.push_back(Node(i, i+1, i+2)); // 2次操作 } // emplace_back: 原地构造，减少一次移动 for (int i = 0; i < n; i++) { v.emplace_back(i, i+1, i+2); // 1次操作，更快 } 2.2 竞赛建议 对于基本类型 (int, long long)：两者无差别 对于自定义结构体：使用 emplace_back 减少开销 对于 pair 和 tuple：emplace_back 可以直接传参数 1 2 3 vector<pair<int, int>> edges; edges.emplace_back(u, v); // 优于 push_back({u, v}) edges.emplace_back(u, v, w); // 适用于 tuple<int,int,int> 三、遍历技巧 3.1 竞赛常用遍历方式 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 vector<int> a = {1, 2, 3, 4, 5}; // 方式1: 索引遍历（需要下标时） for (int i = 0; i < (int)a.size(); i++) { std::cout << a[i]; if (i < (int)a.size() - 1) { std::cout << " "; } else { std::cout << "\n"; } } // 方式2: 范围for（只读，最简洁） for (const auto& x : a) { std::cout << x << " "; } // 方式3: 引用遍历（需要修改） for (auto& x : a) { x *= 2; // 原地修改 } 3.2 倒序遍历 1 2 3 4 5 6 7 8 9 10 11 12 13 vector<int> a = {1, 2, 3, 4, 5}; // 方法1: 反向迭代器 for (auto it = a.rbegin(); it != a.rend(); ++it) { std::cout << *it << " "; } // 方法2: 索引倒序（常用） for (int i = (int)a.size() - 1; i >= 0; i--) { std::cout << a[i] << " "; } 四、算法配合 (C++11 写法) 4.1 C++11 排序与去重 1 2 3 4 5 6 7 8 9 10 11 12 13 vector<int> a = {3, 1, 4, 1, 5, 9, 2, 6}; // C++11 sort（使用 all 宏） sort(all(a)); // 升序 sort(all(a), greater<int>()); // 降序 sort(all(a), [](int x, int y) { return x % 10 < y % 10; // 按个位数排序 }); // C++11 去重（必须先排序） sort(all(a)); a.erase(unique(all(a)), a.end()); 4.2 C++11 二分查找 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 vector<int> a = {1, 3, 5, 7, 9}; // C++11 lower_bound auto it = lower_bound(all(a), 5); if (it != a.end() && *it == 5) { std::cout << "找到，下标: " << (it - a.begin()); } // upper_bound it = upper_bound(all(a), 5); std::cout << *it; // 7 // binary_search bool exists = binary_search(all(a), 5); 4.3 前缀和 1 2 3 4 5 6 7 8 9 10 11 12 13 vector<int> a = {1, 2, 3, 4, 5}; int n = (int)a.size(); // 构造前缀和数组 vector<long long> pref(n + 1, 0); for (int i = 0; i < n; i++) { pref[i + 1] = pref[i] + a[i]; } // 查询区间和 [l, r] int l = 1, r = 3; long long sum = pref[r + 1] - pref[l]; // a[1]+a[2]+a[3] = 9 五、C++11 安全删除法 (O(N) 性能) 5.1 为什么 erase + 循环是 O(N²) 陷阱 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 // ❌ 致命错误！每次 erase 后移 O(N) 元素，总共 O(N²) vector<int> v = {1, 2, 3, 4, 5}; for (auto it = v.begin(); it != v.end(); ) { if (*it % 2 == 0) { v.erase(it); // 删除后，后面的元素全部前移！ } else { ++it; } } // ❌ 倒序删除也是 O(N²)! for (int i = (int)v.size() - 1; i >= 0; i--) { if (v[i] % 2 == 0) { v.erase(v.begin() + i); // 每次 erase 都是 O(N) } } 5.2 C++11 Erase-Remove 惯用法 (O(N) 性能秒杀) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #include <vector> #include <algorithm> vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; // ✅ C++11 推荐：O(N) 删除所有偶数！ v.erase(remove_if(all(v), [](int x) { return x % 2 == 0; }), v.end()); // ✅ 删除所有小于5的元素 v.erase(remove_if(all(v), [](int x) { return x < 5; }), v.end()); // ✅ 删除特定值 v.erase(remove(all(v), 5), v.end()); // 删除所有值为5的元素 5.3 多条件删除 1 2 3 4 5 6 7 8 9 10 11 12 13 14 vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; // 删除既能被2整除又能被3整除的数 (即能被6整除) v.erase(remove_if(all(v), [](int x) { return x % 2 == 0 && x % 3 == 0; }), v.end()); // 删除区间 [3, 7) 内的元素 int L = 3, R = 7; v.erase(remove_if(all(v), [&](int x) { return x >= L && x < R; }), v.end()); 六、vector 性能天坑 6.1 为什么不推荐使用 vector 1 2 3 4 5 6 7 8 9 10 11 12 13 14 // ❌ 致命错误！vector<bool> 是特化版本，有严重性能问题 vector<bool> flags(n); // 问题1: 无法返回真正引用，只能返回代理对象 flags[0] = true; // 实际是代理对象赋值，有额外开销 // 问题2: 动态位压缩导致缓存不友好 // 访问 flags[i] 需要位运算提取，实际常数远大于 vector<char> // 问题3: 无法取地址，兼容性差 // &flags[0] 返回的是代理对象指针，不是真正地址 // 问题4: 并行化不友好 // 位操作天然有依赖，难以向量化 6.2 正确替代方案 1 2 3 4 5 6 7 8 9 10 11 12 // ✅ 推荐1: vector<char>（1字节，效率最高） vector<char> flags(n, 0); flags[i] = 1; // ✅ 推荐2: vector<uint8_t> / vector<unsigned char> vector<uint8_t> flags2(n); // ✅ 推荐3: vector<int>（如果需要布尔运算） vector<int> flags3(n); // ✅ 布尔数组用 std::vector<bool>::reference 的替代方案 // 使用 deque<bool> 或自己封装 6.3 性能对比 类型 访问时间 内存 适用场景 vector<bool> 最慢 1 bit ❌ 不推荐 vector<char> 最快 1 byte ✅ 竞赛首选 vector<uint8_t> 快 1 byte ✅ 明确语义 vector<int> 快 4 byte 需要位运算时 七、迭代器失效问题 7.1 失效场景 1 2 3 4 5 vector<int> v = {1, 2, 3, 4, 5}; auto it = v.begin() + 2; // 指向3 v.push_back(6); // 可能触发reallocation，it失效！ // *it; // 危险！未定义行为 7.2 安全删除元素 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; // ✅ C++11 推荐：使用 Erase-Remove 惯用法，O(N) v.erase(remove_if(all(v), [](int x) { return x % 2 == 0; }), v.end()); // ✅ 传统正确做法：使用 erase 返回值 for (auto it = v.begin(); it != v.end(); ) { if (*it % 2 == 0) { it = v.erase(it); // erase返回下一个有效迭代器 } else { ++it; } } 八、竞赛实战技巧 8.1 用 vector 实现栈 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 vector<int> stk; // 入栈 stk.push_back(x); // 出栈 int top = stk.back(); stk.pop_back(); // 判空 if (stk.empty()) { ... } // 栈大小（C++11） int sz = (int)stk.size(); 8.2 邻接表存图 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 int n, m; // n个点，m条边 cin >> n >> m; vector<vector<pair<int, int>>> g(n); // g[u] = {(v, w), ...} for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; u--; v--; // 转0-indexed g[u].emplace_back(v, w); // 无向图：g[v].emplace_back(u, w); } // 遍历u的邻接点 (C++11) for (auto& p : g[u]) { int to = p.first; int w = p.second; // to是邻接点，w是边权 } 8.3 动态规划中的滚动数组 1 2 3 4 5 6 7 8 9 10 11 12 13 // 优化前：二维DP vector<vector<int>> dp(n, vector<int>(m, 0)); // 优化后：滚动数组（只保留两行） vector<int> dp(m), newdp(m); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { newdp[j] = ...; // 计算 } swap(dp, newdp); // C++11 swap } 8.4 离散化 1 2 3 4 5 6 7 8 9 10 11 12 13 vector<int> a = {100, 50, 200, 50, 100, 300}; vector<int> vals = a; // 拷贝 // C++11 离散化 sort(all(vals)); vals.erase(unique(all(vals)), vals.end()); // 映射 for (auto& x : a) { x = lower_bound(all(vals), x) - vals.begin(); } // a 变为 {2, 0, 3, 0, 2, 4} 九、常见错误与注意事项 错误 说明 解决方案 v[i] 越界 未检查 i < v.size() 使用 at() 或先检查 迭代器失效 push_back后迭代器失效 重新获取迭代器 erase + 循环 O(N²) 复杂度导致 TLE 使用 Erase-Remove 惯用法 使用 vector<bool> 常数巨大，无法返回引用 使用 vector<char> size() - 1 溢出 无符号减法溢出 使用 (int)v.size() - 1 未 reserve 导致 TLE 频繁扩容 预先 reserve 十、C++11 完整竞赛模板 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; // C++11 极简读入 vector<int> a(n); for (auto& x : a) { cin >> x; } // C++11 排序去重 sort(all(a)); a.erase(unique(all(a)), a.end()); // C++11 二分查找 int x; cin >> x; auto it = lower_bound(all(a), x); if (it != a.end() && *it == x) { // 找到x } // C++11 删除元素（O(N)） a.erase(remove_if(all(a), [](int v) { return v < 0; }), a.end()); return 0; } 总结：C++11 竞赛要点 删除元素：只用 Erase-Remove 惯用法 (O(N))，永远不要 erase + 循环 布尔数组：只用 vector<char> 或 vector<uint8_t> 输入读入：使用 for (auto& x : v) cin >> x 排序二分：使用 sort(all(v)) 和 lower_bound(all(v), x) 长度计算：使用 (int)v.size() - 1 代替 v.size() - 1 宏定义：使用 #define all(x) x.begin(), x.end() 提高打字速度 原地构造：对于自定义类型，使用 emplace_back 减少开销

map/set - 有序关联容器 std::map 和 std::set 是基于红黑树实现的有序关联容器，提供O(log n) 的查找、插入和删除操作。在算法竞赛中，它们常用于需要有序性或自动去重的场景。 竞赛中的核心考点 操作 时间复杂度 竞赛要点 查找 (find) O(log n) 快速判断元素是否存在 插入 (insert) O(log n) 自动维护有序性 删除 (erase) O(log n) 高效删除元素 范围查询 (lower_bound/upper_bound) O(log n) 二分查找有序序列 遍历 O(n) 按序访问所有元素 一、map - 键值对容器 1.1 基本用法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 初始化 map<string, int> mp; // 插入元素 mp["apple"] = 100; mp.insert({"banana", 80}); mp.emplace("orange", 120); // C++11 // 查找元素 auto it = mp.find("apple"); if (it != mp.end()) { cout << "apple: " << it->second << endl; } // 遍历 for (const auto& pair : mp) // C++11 { cout << pair.first << ": " << pair.second << endl; } // 删除元素 mp.erase("banana"); // 大小 cout << "size: " << mp.size() << endl; return 0; } 1.2 竞赛常用技巧 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 // 统计频率 map<int, int> freq; for (int x : a) { freq[x]++; } // 按频率排序（需要转换为 vector） vector<pair<int, int>> vec(freq.begin(), freq.end()); sort(vec.begin(), vec.end(), [](const auto& a, const auto& b) { return a.second > b.second; // 按频率降序 }); // 查找第一个大于等于 x 的键 auto it = mp.lower_bound(x); if (it != mp.end()) { cout << "第一个 >= " << x << " 的键: " << it->first << endl; } // 查找第一个大于 x 的键 auto it = mp.upper_bound(x); if (it != mp.end()) { cout << "第一个 > " << x << " 的键: " << it->first << endl; } 二、set - 有序集合 2.1 基本用法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 初始化 set<int> s; // 插入元素（自动去重） s.insert(10); s.insert(20); s.insert(10); // 重复元素，会被忽略 // 查找元素 auto it = s.find(10); if (it != s.end()) { cout << "找到: " << *it << endl; } // 遍历（自动按升序） for (int x : s) { cout << x << " "; } cout << endl; // 删除元素 s.erase(10); // 大小 cout << "size: " << s.size() << endl; return 0; } 2.2 竞赛常用技巧 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 // 去重并排序 vector<int> a = {3, 1, 4, 1, 5, 9, 2, 6}; set<int> s(a.begin(), a.end()); vector<int> sorted_unique(s.begin(), s.end()); // 查找第一个大于等于 x 的元素 auto it = s.lower_bound(x); if (it != s.end()) { cout << "第一个 >= " << x << " 的元素: " << *it << endl; } // 查找第一个大于 x 的元素 auto it = s.upper_bound(x); if (it != s.end()) { cout << "第一个 > " << x << " 的元素: " << *it << endl; } // 反向遍历 for (auto it = s.rbegin(); it != s.rend(); ++it) { cout << *it << " "; } 三、multimap/multiset - 允许重复元素 3.1 基本用法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); // multimap: 允许重复键 multimap<int, string> mmp; mmp.insert({1, "one"}); mmp.insert({1, "uno"}); mmp.insert({2, "two"}); // 查找所有键为1的元素 auto range = mmp.equal_range(1); for (auto it = range.first; it != range.second; ++it) { cout << it->first << ": " << it->second << endl; } // multiset: 允许重复元素 multiset<int> ms; ms.insert(10); ms.insert(20); ms.insert(10); // 允许重复 // 统计元素出现次数 cout << "10出现的次数: " << ms.count(10) << endl; return 0; } 3.2 竞赛应用 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 // 统计频率（multiset 版） multiset<int> ms(a.begin(), a.end()); for (int x : set<int>(a.begin(), a.end())) { cout << x << ": " << ms.count(x) << endl; } // 区间查询（multiset + lower_bound/upper_bound） int L = 5, R = 15; auto left = ms.lower_bound(L); auto right = ms.upper_bound(R); for (auto it = left; it != right; ++it) { cout << *it << " "; } 四、C++11 现代特性 4.1 自定义比较器 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 自定义比较器：按字符串长度排序 struct CompareByLength { bool operator()(const string& a, const string& b) const { if (a.size() != b.size()) { return a.size() < b.size(); } return a < b; } }; // 使用自定义比较器 set<string, CompareByLength> s; s.insert("apple"); s.insert("banana"); s.insert("pear"); // 遍历（按长度排序） for (const string& str : s) { cout << str << " "; // pear apple banana } cout << endl; return 0; } 4.2 Lambda 表达式排序 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); set<int> s = {3, 1, 4, 1, 5, 9, 2, 6}; // 转换为 vector 后排序 vector<int> vec(s.begin(), s.end()); sort(vec.begin(), vec.end(), greater<int>()); // 遍历排序后的结果 for (int x : vec) { cout << x << " "; // 9 6 5 4 3 2 1 } cout << endl; return 0; } 五、竞赛实战技巧 5.1 离散化 + map 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 // 离散化 vector<int> a = {100000, 50000, 200000, 50000, 100000, 300000}; map<int, int> rank_map; set<int> unique_vals(a.begin(), a.end()); int r = 0; for (int x : unique_vals) { rank_map[x] = r++; } // 映射 for (int& x : a) { x = rank_map[x]; } // a 变为 {2, 0, 3, 0, 2, 4} 5.2 区间维护 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 // 维护区间的活跃状态（例如，会议室预约） map<int, int> intervals; // start -> end // 添加区间 [start, end) void add_interval(int start, int end) { // 查找重叠区间 auto it = intervals.lower_bound(start); while (it != intervals.end() && it->first < end) { start = min(start, it->first); end = max(end, it->second); intervals.erase(it++); } intervals[start] = end; } // 检查区间是否空闲 bool is_free(int start, int end) { auto it = intervals.lower_bound(start); if (it != intervals.begin()) { auto prev = prev(it); if (prev->second > start) { return false; } } return it == intervals.end() || it->first >= end; } 5.3 滑动窗口 + set 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 // 滑动窗口找最大值（使用 multiset） vector<int> max_sliding_window(vector<int>& nums, int k) { vector<int> res; multiset<int, greater<int>> ms; for (int i = 0; i < nums.size(); i++) { ms.insert(nums[i]); if (i >= k - 1) { res.push_back(*ms.begin()); ms.erase(ms.find(nums[i - k + 1])); } } return res; } 六、性能优化 6.1 避免频繁插入删除 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 // 错误示范：频繁修改导致红黑树频繁重构 map<int, int> mp; for (int i = 0; i < 1e5; i++) { mp[i] = i; mp.erase(i); } // 正确做法：批量操作 vector<pair<int, int>> data; for (int i = 0; i < 1e5; i++) { data.emplace_back(i, i); } map<int, int> mp(data.begin(), data.end()); 6.2 合理选择容器 场景 推荐容器 原因 需要键值对且有序 map O(log n) 操作，自动排序 需要自动去重且有序 set O(log n) 操作，自动排序去重 需要允许重复元素 multimap/multiset 保留重复元素，仍有序 只需要哈希表（无序） unordered_map/unordered_set O(1) 平均操作时间 需要频繁修改元素 map/set 红黑树结构支持高效修改 七、常见错误与注意事项 错误 说明 解决方案 直接修改 map 的键 map 的键是 const 的，不能修改 先删除旧键，再插入新键 使用 operator[] 查找不存在的键 会自动插入该键，值为默认构造 使用 find() 或 count() 查找 遍历中修改容器 可能导致迭代器失效 使用 erase() 的返回值更新迭代器 比较自定义类型时未定义 operator< map/set 需要比较器 定义 operator< 或提供自定义比较器 性能瓶颈 对于不需要有序的场景，map/set 不如 unordered 容器 评估是否需要有序性，选择合适的容器 八、C++11 完整竞赛模板 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); // map 统计频率 int n; cin >> n; vector<int> a(n); for (auto& x : a) { cin >> x; } map<int, int> freq; for (int x : a) { freq[x]++; } // 按频率排序 vector<pair<int, int>> vec(freq.begin(), freq.end()); sort(all(vec), [](const pair<int, int>& a, const pair<int, int>& b) { return a.second > b.second; }); // set 去重排序 set<int> s(a.begin(), a.end()); // 查找操作 int x; cin >> x; auto it = s.lower_bound(x); if (it != s.end()) { cout << "第一个 >= " << x << " 的元素: " << *it << endl; } return 0; } 总结：竞赛要点 有序性：map/set 自动维护有序性，适合需要排序的场景 去重：set 自动去重，multiset 允许重复 范围查询：lower_bound/upper_bound 是竞赛中的常用操作 时间复杂度：所有操作都是 O(log n)，稳定可靠 现代 C++：使用 C++11 auto 类型推导和 Lambda 表达式 性能考量：对于不需要有序的场景，考虑使用 unordered 容器 实战技巧：离散化、区间维护、滑动窗口等高级应用 map/set 是算法竞赛中处理有序数据的强大工具，掌握它们的使用技巧能大大提升解题效率。

unordered_map/unordered_set - 哈希关联容器 std::unordered_map 和 std::unordered_set 是基于哈希表实现的无序关联容器，提供平均 O(1) 的查找、插入和删除操作。在算法竞赛中，它们是处理不需要有序性场景的首选容器。 竞赛中的核心考点 操作 时间复杂度 竞赛要点 查找 (find) 平均 O(1) 快速判断元素是否存在 插入 (insert) 平均 O(1) 高效插入元素 删除 (erase) 平均 O(1) 高效删除元素 遍历 O(n) 无序访问所有元素 哈希冲突 O(n) 最坏 避免哈希冲突影响性能 一、unordered_map - 哈希键值对容器 1.1 基本用法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 初始化 unordered_map<string, int> ump; // 插入元素 ump["apple"] = 100; ump.insert({"banana", 80}); ump.emplace("orange", 120); // C++11 // 查找元素 auto it = ump.find("apple"); if (it != ump.end()) { cout << "apple: " << it->second << endl; } // 遍历（无序） for (const auto& pair : ump) // C++11 { cout << pair.first << ": " << pair.second << endl; } // 删除元素 ump.erase("banana"); // 大小 cout << "size: " << ump.size() << endl; // 清空 ump.clear(); return 0; } 1.2 竞赛常用技巧 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 // 统计频率（比 map 更快） unordered_map<int, int> freq; for (int x : a) { freq[x]++; } // 检查元素是否存在 if (ump.count("apple")) { cout << "apple exists" << endl; } // 遍历所有键值对 for (const auto& pair : ump) { int key = pair.first; int val = pair.second; // 处理键值对 } // 批量插入 vector<pair<string, int>> data = {{"a", 1}, {"b", 2}, {"c", 3}}; unordered_map<string, int> ump(data.begin(), data.end()); 二、unordered_set - 哈希集合 2.1 基本用法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 初始化 unordered_set<int> us; // 插入元素（自动去重） us.insert(10); us.insert(20); us.insert(10); // 重复元素，会被忽略 // 查找元素 auto it = us.find(10); if (it != us.end()) { cout << "找到: " << *it << endl; } // 遍历（无序） for (int x : us) { cout << x << " "; } cout << endl; // 删除元素 us.erase(10); // 大小 cout << "size: " << us.size() << endl; return 0; } 2.2 竞赛常用技巧 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 // 快速去重（比 set 更快） vector<int> a = {3, 1, 4, 1, 5, 9, 2, 6}; unordered_set<int> us(a.begin(), a.end()); vector<int> unique_vals(us.begin(), us.end()); // 检查元素是否存在 if (us.count(5)) { cout << "5 exists" << endl; } // 清空并重新填充 us.clear(); for (int x : b) { us.insert(x); } 三、自定义哈希函数 3.1 基本类型的哈希 1 2 3 4 // 基本类型自动支持哈希 unordered_map<int, string> ump1; unordered_map<string, int> ump2; unordered_map<long long, double> ump3; 3.2 自定义类型的哈希 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; // 自定义结构体 struct Point { int x, y; bool operator==(const Point& other) const { return x == other.x && y == other.y; } }; // 自定义哈希函数 namespace std { template<> struct hash<Point> { size_t operator()(const Point& p) const { // 组合哈希值 size_t h1 = hash<int>()(p.x); size_t h2 = hash<int>()(p.y); return h1 ^ (h2 << 1); } }; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); unordered_set<Point> us; us.insert({1, 2}); us.insert({3, 4}); if (us.count({1, 2})) { cout << "Point (1,2) exists" << endl; } return 0; } 3.3 使用 boost 哈希（竞赛中不推荐） 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 // 注意：竞赛环境通常不支持 boost #include <boost/functional/hash.hpp> struct Point { int x, y; bool operator==(const Point& other) const { return x == other.x && y == other.y; } }; namespace std { template<> struct hash<Point> { size_t operator()(const Point& p) const { size_t seed = 0; boost::hash_combine(seed, p.x); boost::hash_combine(seed, p.y); return seed; } }; } 四、C++11 现代特性 4.1 高效查找方法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); unordered_set<string> us; us.insert("apple"); // C++11: 使用 find 方法查找 if (us.find("apple") != us.end()) { cout << "apple exists" << endl; } // 或者使用 count 方法 if (us.count("apple")) { cout << "apple exists" << endl; } return 0; } 4.2 批量操作 1 2 3 4 5 6 7 8 9 10 11 12 // C++11: 批量插入 vector<pair<string, int>> data = { {"a", 1}, {"b", 2}, {"c", 3} }; unordered_map<string, int> ump(data.begin(), data.end()); // 批量遍历 for (const auto& pair : ump) { cout << pair.first << ": " << pair.second << endl; } // 批量删除 ump.erase(ump.begin(), ump.end()); 五、竞赛实战技巧 5.1 快速查找 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 // 查找是否存在重复元素 bool has_duplicate(const vector<int>& nums) { unordered_set<int> seen; for (int x : nums) { if (seen.count(x)) { return true; } seen.insert(x); } return false; } // 两数之和 vector<int> two_sum(const vector<int>& nums, int target) { unordered_map<int, int> val_to_idx; for (int i = 0; i < nums.size(); i++) { int complement = target - nums[i]; if (val_to_idx.count(complement)) { return {val_to_idx[complement], i}; } val_to_idx[nums[i]] = i; } return {}; } 5.2 缓存优化 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 // 记忆化搜索（斐波那契） unordered_map<int, long long> memo; long long fib(int n) { if (n <= 1) { return n; } if (memo.count(n)) { return memo[n]; } memo[n] = fib(n-1) + fib(n-2); return memo[n]; } // 缓存计算结果 unordered_map<string, int> cache; int compute(const string& key) { if (cache.count(key)) { return cache[key]; } int result = /* 复杂计算 */; cache[key] = result; return result; } 5.3 字符串处理 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 // 单词频率统计 unordered_map<string, int> word_freq; string word; while (cin >> word) { word_freq[word]++; } // 查找重复的子字符串 unordered_set<string> seen; for (int i = 0; i < s.size() - k + 1; i++) { string substr = s.substr(i, k); if (seen.count(substr)) { return substr; } seen.insert(substr); } 六、性能优化 6.1 预分配空间 1 2 3 4 5 6 7 8 9 10 11 12 13 14 // 错误示范：频繁扩容 unordered_map<int, int> ump; for (int i = 0; i < 1e6; i++) { ump[i] = i; } // 正确做法：预分配空间 unordered_map<int, int> ump; ump.reserve(1e6); // 预分配足够的桶 for (int i = 0; i < 1e6; i++) { ump[i] = i; } 6.2 避免哈希冲突 1 2 3 4 5 6 7 8 9 10 11 12 13 14 // 自定义哈希函数时避免冲突 struct MyHash { size_t operator()(int x) const { // 更好的哈希函数 x = ((x >> 16) ^ x) * 0x45d9f3b; x = ((x >> 16) ^ x) * 0x45d9f3b; x = (x >> 16) ^ x; return x; } }; unordered_map<int, int, MyHash> ump; 6.3 合理选择容器 场景 推荐容器 原因 需要键值对且无序 unordered_map O(1) 平均操作时间 需要自动去重且无序 unordered_set O(1) 平均操作时间 需要有序性 map/set 自动排序 数据量小 任意 性能差异不明显 数据量大且频繁查找 unordered_map/unordered_set 性能优势明显 七、常见错误与注意事项 错误 说明 解决方案 自定义类型未定义 operator== 哈希容器需要比较元素是否相等 为自定义类型定义 operator== 自定义类型未提供哈希函数 编译器无法为自定义类型生成哈希值 特化 std::hash 或提供哈希函数 哈希冲突严重 导致 O(n) 时间复杂度 使用更好的哈希函数或增大桶数 内存使用过高 哈希表需要额外空间 权衡时间和空间，考虑使用其他容器 遍历顺序依赖 代码依赖于遍历顺序 不要依赖哈希容器的遍历顺序 频繁重哈希 影响性能 预先 reserve 足够空间 八、C++11 完整竞赛模板 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); // unordered_map 统计频率 int n; cin >> n; vector<int> a(n); for (auto& x : a) { cin >> x; } unordered_map<int, int> freq; freq.reserve(n); // 预分配空间 for (int x : a) { freq[x]++; } // 查找元素 int x; cin >> x; if (freq.find(x) != freq.end()) // C++11 { cout << x << " 出现了 " << freq[x] << " 次" << endl; } else { cout << x << " 不存在" << endl; } // unordered_set 去重 unordered_set<int> us(a.begin(), a.end()); cout << "去重后大小: " << us.size() << endl; return 0; } 总结：竞赛要点 性能优势：平均 O(1) 的操作时间，比有序容器快 无序性：不保证元素顺序，不要依赖遍历顺序 哈希冲突：注意哈希函数的质量，避免严重冲突 内存使用：哈希表需要额外空间，权衡时间和空间 现代 C++：使用 C++11 auto 类型推导和范围 for 循环 预分配空间：使用 reserve 避免频繁扩容 自定义类型：需要提供 operator== 和哈希函数 实战应用：快速查找、频率统计、缓存、字符串处理等 unordered_map 和 unordered_set 是算法竞赛中处理不需要有序性场景的最佳选择，掌握它们的使用技巧能显著提升代码性能。

priority_queue - 优先队列 std::priority_queue 是基于堆实现的优先队列，默认是最大堆，提供O(log n) 的插入和删除操作。在算法竞赛中，它是实现贪心算法和最短路径算法（如 Dijkstra）的核心工具。 竞赛中的核心考点 操作 时间复杂度 竞赛要点 插入 (push) O(log n) 向堆中添加元素 删除 (pop) O(log n) 删除堆顶元素 访问堆顶 (top) O(1) 获取优先级最高的元素 判空 (empty) O(1) 检查队列是否为空 大小 (size) O(1) 获取队列大小 一、基本用法 1.1 最大堆（默认） 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 默认是最大堆 priority_queue<int> pq; // 插入元素 pq.push(3); pq.push(1); pq.push(4); pq.push(1); pq.push(5); // 访问堆顶（最大元素） cout << "堆顶: " << pq.top() << endl; // 5 // 删除堆顶 pq.pop(); cout << "删除后堆顶: " << pq.top() << endl; // 4 // 遍历（会破坏堆结构） while (!pq.empty()) { cout << pq.top() << " "; pq.pop(); } // 输出: 4 3 1 1 return 0; } 1.2 最小堆 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 最小堆 priority_queue<int, vector<int>, greater<int>> pq; // 插入元素 pq.push(3); pq.push(1); pq.push(4); pq.push(1); pq.push(5); // 访问堆顶（最小元素） cout << "堆顶: " << pq.top() << endl; // 1 // 遍历 while (!pq.empty()) { cout << pq.top() << " "; pq.pop(); } // 输出: 1 1 3 4 5 return 0; } 二、自定义类型 2.1 结构体作为元素 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; struct Node { int val, priority; Node(int v, int p) : val(v), priority(p) {} // 重载 < 运算符，用于最大堆 bool operator<(const Node& other) const { return priority < other.priority; // 大的优先级优先 } }; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); priority_queue<Node> pq; pq.emplace(1, 10); pq.emplace(2, 5); pq.emplace(3, 15); while (!pq.empty()) { Node top = pq.top(); cout << "val: " << top.val << ", priority: " << top.priority << endl; pq.pop(); } // 输出: // val: 3, priority: 15 // val: 1, priority: 10 // val: 2, priority: 5 return 0; } 2.2 自定义比较器 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; struct Node { int val, cost; Node(int v, int c) : val(v), cost(c) {} }; // 自定义比较器（最小堆，按 cost 排序） struct Compare { bool operator()(const Node& a, const Node& b) { return a.cost > b.cost; // 小的 cost 优先 } }; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); priority_queue<Node, vector<Node>, Compare> pq; pq.emplace(1, 100); pq.emplace(2, 50); pq.emplace(3, 150); while (!pq.empty()) { Node top = pq.top(); cout << "val: " << top.val << ", cost: " << top.cost << endl; pq.pop(); } // 输出: // val: 2, cost: 50 // val: 1, cost: 100 // val: 3, cost: 150 return 0; } 三、竞赛实战应用 3.1 Dijkstra 算法（最短路径） 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; using ll = long long; using pii = pair<ll, int>; // (距离, 节点) const ll INF = 1e18; vector<ll> dijkstra(int start, const vector<vector<pii>>& g) { int n = g.size(); vector<ll> dist(n, INF); dist[start] = 0; // 最小堆，按距离排序 priority_queue<pii, vector<pii>, greater<pii>> pq; pq.emplace(0, start); while (!pq.empty()) { pair<ll, int> top = pq.top(); ll d = top.first; int u = top.second; pq.pop(); if (d > dist[u]) { continue; // 旧的路径，跳过 } for (const auto& edge : g[u]) { int v = edge.first; ll w = edge.second; if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; pq.emplace(dist[v], v); } } } return dist; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, start; cin >> n >> m >> start; vector<vector<pii>> g(n); for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; g[u].emplace_back(v, w); } vector<ll> dist = dijkstra(start, g); for (int i = 0; i < n; i++) { if (dist[i] == INF) { cout << "INF "; } else { cout << dist[i] << " "; } } return 0; } 3.2 贪心算法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 // 活动选择问题（最大不重叠区间） struct Interval { int start, end; bool operator<(const Interval& other) const { return end > other.end; // 按结束时间排序（最小堆） } }; int max_non_overlapping(vector<Interval>& intervals) { sort(intervals.begin(), intervals.end(), [](const Interval& a, const Interval& b) { return a.start < b.start; }); priority_queue<Interval> pq; int count = 0; for (const auto& interval : intervals) { while (!pq.empty() && pq.top().end <= interval.start) { pq.pop(); } pq.push(interval); count = max(count, (int)pq.size()); } return count; } // 合并 k 个有序链表 struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; struct CompareNode { bool operator()(ListNode* a, ListNode* b) { return a->val > b->val; // 最小堆 } }; ListNode* merge_k_lists(vector<ListNode*>& lists) { priority_queue<ListNode*, vector<ListNode*>, CompareNode> pq; for (ListNode* node : lists) { if (node) { pq.push(node); } } ListNode dummy(0); ListNode* tail = &dummy; while (!pq.empty()) { ListNode* node = pq.top(); pq.pop(); tail->next = node; tail = tail->next; if (node->next) { pq.push(node->next); } } return dummy.next; } 3.3 滑动窗口最大值 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 vector<int> max_sliding_window(vector<int>& nums, int k) { vector<int> res; // 最大堆，存储 (值, 索引) priority_queue<pair<int, int>> pq; for (int i = 0; i < nums.size(); i++) { pq.emplace(nums[i], i); // 移除窗口外的元素 while (pq.top().second <= i - k) { pq.pop(); } if (i >= k - 1) { res.push_back(pq.top().first); } } return res; } 四、C++11 现代特性 4.1 高效访问优先队列元素 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); priority_queue<pair<int, string>> pq; pq.emplace(10, "apple"); pq.emplace(5, "banana"); pq.emplace(15, "orange"); while (!pq.empty()) { pair<int, string> top = pq.top(); int priority = top.first; string name = top.second; cout << "priority: " << priority << ", name: " << name << endl; pq.pop(); } return 0; } 4.2 使用函数对象作为比较器 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; // 自定义比较器（最小堆） struct Compare { bool operator()(int a, int b) { return a > b; // 小的优先 } }; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); // C++11: 使用函数对象作为比较器 priority_queue<int, vector<int>, Compare> pq; pq.push(3); pq.push(1); pq.push(4); while (!pq.empty()) { cout << pq.top() << " "; pq.pop(); } // 输出: 1 3 4 return 0; } 五、性能优化 5.1 预分配空间 1 2 3 4 5 6 // 预分配堆的底层容器空间 priority_queue<int> pq; // 无法直接 reserve，但可以通过构造函数传入预分配的 vector vector<int> data; data.reserve(100000); priority_queue<int> pq2(data.begin(), data.end()); 5.2 避免不必要的拷贝 1 2 3 4 5 6 7 8 // 使用 emplace 避免拷贝 priority_queue<Node> pq; pq.emplace(1, 10); // 原地构造，比 push(Node(1, 10)) 更高效 // 使用移动语义 priority_queue<vector<int>> pq; vector<int> v = {1, 2, 3}; pq.push(move(v)); // 移动而非拷贝 5.3 合理选择堆类型 场景 推荐堆类型 原因 找最大值 最大堆（默认） 直接取堆顶 找最小值 最小堆（greater<>） 直接取堆顶 自定义优先级 自定义比较器 灵活控制排序规则 频繁插入删除 priority_queue O(log n) 时间复杂度 静态数据 一次性建堆 使用 make_heap + pop_heap 六、常见错误与注意事项 错误 说明 解决方案 访问空队列的 top 未定义行为 先检查 empty() 比较器方向错误 得到错误的堆类型 仔细检查比较器逻辑 自定义类型未重载比较运算符 编译错误 为自定义类型重载 operator< 或提供比较器 性能瓶颈 频繁的插入删除 考虑批量操作或使用其他数据结构 内存使用过高 堆存储所有元素 权衡时间和空间，考虑是否需要全部存储 Dijkstra 算法中的重复节点 影响性能 检查当前距离是否大于已记录的距离 七、C++11 完整竞赛模板 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; using ll = long long; using pii = pair<ll, int>; const ll INF = 1e18; // Dijkstra 算法模板 vector<ll> dijkstra(int start, const vector<vector<pii>>& g) { int n = g.size(); vector<ll> dist(n, INF); dist[start] = 0; priority_queue<pii, vector<pii>, greater<pii>> pq; pq.emplace(0, start); while (!pq.empty()) { pii top = pq.top(); ll d = top.first; int u = top.second; pq.pop(); if (d > dist[u]) { continue; } for (const auto& edge : g[u]) { int v = edge.first; ll w = edge.second; if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; pq.emplace(dist[v], v); } } } return dist; } // 贪心算法：最大不重叠区间 struct Interval { int start, end; }; int max_non_overlapping(vector<Interval>& intervals) { sort(intervals.begin(), intervals.end(), [](const Interval& a, const Interval& b) { return a.start < b.start; }); priority_queue<int, vector<int>, greater<int>> pq; // 存储结束时间 int count = 0; for (const auto& interval : intervals) { while (!pq.empty() && pq.top() <= interval.start) { pq.pop(); } pq.push(interval.end); count = max(count, (int)pq.size()); } return count; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 测试 Dijkstra int n, m, start; cin >> n >> m >> start; vector<vector<pii>> g(n); for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; g[u].emplace_back(v, w); } vector<ll> dist = dijkstra(start, g); for (ll d : dist) { cout << (d == INF ? "INF" : to_string(d)) << " "; } cout << endl; return 0; } 总结：竞赛要点 默认最大堆：priority_queue 默认是最大堆，需要最小堆时使用 greater<> 比较器 Dijkstra 算法：优先队列是实现 Dijkstra 算法的标准工具 贪心算法：优先队列常用于贪心策略，如活动选择、任务调度等 自定义比较器：通过重载 operator< 或提供自定义比较器来控制优先级 性能优化：使用 emplace 避免拷贝，合理预分配空间 现代 C++11：使用 auto 类型推导、范围 for 循环、lambda 表达式和函数对象比较器 注意事项：检查队列是否为空，避免重复节点，合理处理比较器逻辑 实战应用：最短路径、最小生成树、滑动窗口、合并有序序列等 priority_queue 是算法竞赛中解决优先级问题的强大工具，掌握它的使用技巧能让你在处理贪心和图论问题时更加得心应手。

string - 字符串处理 std::string 是 C++ 中最常用的字符串类，提供了丰富的字符串操作方法。在算法竞赛中，字符串处理是一个常见的考点，掌握 string 的使用技巧能大大提升解题效率。 竞赛中的核心考点 操作 时间复杂度 竞赛要点 访问单个字符 O(1) 随机访问 字符串拼接 O(n) 注意内存分配 子串提取 O(n) 提取子字符串 查找 O(n) 查找子串或字符 替换 O(n) 替换子串 插入/删除 O(n) 注意性能影响 比较 O(n) 字典序比较 一、基本用法 1.1 初始化 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 默认构造 string s1; // 字符串字面量构造 string s2 = "hello"; string s3("world"); // 重复构造 string s4(5, 'a'); // "aaaaa" // 从 C 风格字符串构造 const char* c_str = "test"; string s5(c_str); // 从其他 string 构造 string s6(s2); string s7(s2, 1, 3); // 从索引1开始，长度3: "ell" // 从迭代器构造 string s8(s2.begin(), s2.end()); return 0; } 1.2 基本操作 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); string s = "hello"; // 访问字符 char c = s[0]; // 'h' char d = s.at(1); // 'e'（带边界检查） // 修改字符 s[0] = 'H'; // "Hello" // 长度 int len = s.size(); // 5 int length = s.length(); // 5 // 判空 bool is_empty = s.empty(); // false // 清空 s.clear(); // 容量 int cap = s.capacity(); s.reserve(100); // 预分配空间 return 0; } 二、常用方法 2.1 字符串拼接 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 string s = "hello"; // 方法1: 使用 += s += " world"; // 方法2: 使用 append s.append("!"); s.append(3, '?'); // 添加3个问号 // 方法3: 使用 + 运算符 string s1 = "hello"; string s2 = "world"; string s3 = s1 + " " + s2; // 方法4: 使用 insert s.insert(s.end(), '!'); 2.2 子串操作 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 string s = "Hello, world!"; // substr(pos, length) string sub1 = s.substr(7, 5); // "world" string sub2 = s.substr(7); // "world!" // 查找子串 size_t pos = s.find("world"); // 7 if (pos != string::npos) { cout << "Found at position: " << pos << endl; } // 查找字符 pos = s.find('o'); // 4 // 从指定位置开始查找 pos = s.find('o', 5); // 8 // 反向查找 pos = s.rfind('o'); // 8 // 查找第一个符合条件的字符 pos = s.find_first_of("aeiou"); // 1 ('e') // 查找第一个不符合条件的字符 pos = s.find_first_not_of("Helo "); // 5 (',') 2.3 替换操作 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 string s = "Hello, world!"; // replace(pos, length, replacement) s.replace(7, 5, "C++"); // "Hello, C++!" // 使用迭代器范围替换 s.replace(s.begin() + 7, s.end() - 1, "programming"); // 替换所有匹配的子串 string s = "ababab"; size_t pos = 0; while ((pos = s.find("ab", pos)) != string::npos) { s.replace(pos, 2, "CD"); pos += 2; } // s 变为 "CDCDCD" 2.4 插入和删除 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 string s = "Hello"; // 插入字符串 s.insert(5, " world"); // "Hello world" // 插入字符 s.insert(s.begin(), '!'); // "!Hello world" // 删除字符 s.erase(s.begin()); // "Hello world" // 删除子串 s.erase(5, 6); // "Hello" // 删除迭代器范围 s.erase(s.begin() + 2, s.end()); // "He" 三、字符串比较 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 string s1 = "apple"; string s2 = "banana"; // 运算符比较 if (s1 < s2) // 字典序比较 { cout << "s1 comes before s2" << endl; } // compare 方法 int result = s1.compare(s2); if (result < 0) cout << "s1 < s2" << endl; else if (result == 0) cout << "s1 == s2" << endl; else cout << "s1 > s2" << endl; // 比较子串 result = s1.compare(0, 3, s2, 0, 3); // 比较前3个字符 四、C++11 现代特性 4.1 字符串前缀和后缀检查 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; // C++11: 检查字符串前缀 bool starts_with(const string& s, const string& prefix) { return s.size() >= prefix.size() && s.compare(0, prefix.size(), prefix) == 0; } // C++11: 检查字符前缀 bool starts_with(const string& s, char c) { return !s.empty() && s[0] == c; } // C++11: 检查字符串后缀 bool ends_with(const string& s, const string& suffix) { return s.size() >= suffix.size() && s.compare(s.size() - suffix.size(), suffix.size(), suffix) == 0; } // C++11: 检查字符后缀 bool ends_with(const string& s, char c) { return !s.empty() && s.back() == c; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); string s = "Hello, world!"; if (starts_with(s, "Hello")) { cout << "Starts with Hello" << endl; } if (starts_with(s, 'H')) { cout << "Starts with H" << endl; } if (ends_with(s, "!")) { cout << "Ends with !" << endl; } if (ends_with(s, "world!")) { cout << "Ends with world!" << endl; } return 0; } 4.2 字符串包含检查 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; // C++11: 检查字符串包含 bool contains(const string& s, const string& substr) { return s.find(substr) != string::npos; } // C++11: 检查字符包含 bool contains(const string& s, char c) { return s.find(c) != string::npos; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); string s = "Hello, world!"; if (contains(s, "world")) { cout << "Contains 'world'" << endl; } if (contains(s, 'o')) { cout << "Contains 'o'" << endl; } return 0; } 五、字符串输入读取 核心要点 场景 方法 关键代码 单个单词 cin >> s 遇空格停止 整行读取 getline(cin, s) 包含空格 数字+字符串 先 cin >> n 再 getline 必须 cin.ignore() 关键代码示例 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 // 混合输入：数字 + 字符串（重点！） int n; cin >> n; cin.ignore(); // 清除换行符，否则 getline 会读空行 string s; getline(cin, s); // 正确读取整行 // 读取多行 int n; cin >> n; cin.ignore(); while (n--) { string line; getline(cin, line); // 处理 line } // 读取到文件结束 string line; while (getline(cin, line)) { // 处理 line } 六、竞赛实战技巧 5.1 字符串反转 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 string reverse_string(string s) { reverse(s.begin(), s.end()); return s; } // 原地反转 void reverse_inplace(string& s) { int n = s.size(); for (int i = 0; i < n / 2; i++) { swap(s[i], s[n - 1 - i]); } } 5.2 字符串分割 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 vector<string> split(const string& s, char delimiter) { vector<string> tokens; string token; istringstream tokenStream(s); while (getline(tokenStream, token, delimiter)) { tokens.push_back(token); } return tokens; } // 分割多个空格 vector<string> split_whitespace(const string& s) { vector<string> tokens; string token; istringstream tokenStream(s); while (tokenStream >> token) { tokens.push_back(token); } return tokens; } 5.3 字符串转数字 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 // 字符串转整数 int str_to_int(const string& s) { return stoi(s); } // 字符串转长整型 long long str_to_ll(const string& s) { return stoll(s); } // 字符串转浮点数 double str_to_double(const string& s) { return stod(s); } // 数字转字符串 string int_to_str(int n) { return to_string(n); } string ll_to_str(long long n) { return to_string(n); } 5.4 回文串判断 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 bool is_palindrome(const string& s) { int n = s.size(); for (int i = 0; i < n / 2; i++) { if (s[i] != s[n - 1 - i]) { return false; } } return true; } // 使用双指针 bool is_palindrome2(const string& s) { int left = 0, right = s.size() - 1; while (left < right) { if (s[left] != s[right]) { return false; } left++; right--; } return true; } 5.5 子串查找 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 // KMP 算法（高效查找子串） vector<int> compute_lps(const string& pattern) { int n = pattern.size(); vector<int> lps(n, 0); for (int i = 1, len = 0; i < n; ) { if (pattern[i] == pattern[len]) { lps[i++] = ++len; } else if (len > 0) { len = lps[len - 1]; } else { lps[i++] = 0; } } return lps; } vector<int> kmp_search(const string& text, const string& pattern) { vector<int> result; int n = text.size(), m = pattern.size(); if (m == 0) return result; vector<int> lps = compute_lps(pattern); for (int i = 0, j = 0; i < n; ) { if (pattern[j] == text[i]) { i++; j++; if (j == m) { result.push_back(i - j); j = lps[j - 1]; } } else if (j > 0) { j = lps[j - 1]; } else { i++; } } return result; } 六、性能优化 6.1 预分配空间 1 2 3 4 5 6 7 8 9 10 11 12 13 14 // 错误示范：频繁扩容 string s; for (int i = 0; i < 1e5; i++) { s += 'a'; } // 正确做法：预分配空间 string s; s.reserve(1e5); for (int i = 0; i < 1e5; i++) { s += 'a'; } 6.2 避免不必要的拷贝 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 // 错误示范：不必要的拷贝 string process_string(string s) // 值传递，会拷贝 { // 处理 s return s; } // 正确做法：使用引用 string process_string(const string& s) // 常量引用，无拷贝 { string result = s; // 处理 result return result; } // 使用移动语义 string create_large_string() { string s(1e5, 'a'); return s; // 移动语义，无拷贝 } 6.3 字符串拼接优化 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 // 错误示范：多次拼接导致多次拷贝 string s; for (int i = 0; i < 1000; i++) { s += to_string(i); } // 正确做法：使用 ostringstream ostringstream oss; for (int i = 0; i < 1000; i++) { oss << i; } string s = oss.str(); // 或者使用 reserve string s; s.reserve(10000); for (int i = 0; i < 1000; i++) { s += to_string(i); } 七、常见错误与注意事项 错误 说明 解决方案 越界访问 访问超出字符串长度的索引 使用 at() 或先检查长度 字符串拼接性能 频繁拼接导致多次内存分配 使用 reserve() 或 ostringstream 比较字符串和字面量 直接比较可能导致意外结果 确保类型匹配 字符编码问题 处理非 ASCII 字符时出错 注意编码格式，使用 wstring 处理宽字符 内存使用过高 存储过长的字符串 考虑使用 string_view 或流式处理 查找返回值处理 未检查 string::npos 总是检查查找结果 八、C++11 完整竞赛模板 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; // 字符串分割 vector<string> split(const string& s, char delimiter) { vector<string> tokens; string token; istringstream tokenStream(s); while (getline(tokenStream, token, delimiter)) { tokens.push_back(token); } return tokens; } // 检查字符串前缀 bool starts_with(const string& s, const string& prefix) { return s.size() >= prefix.size() && s.compare(0, prefix.size(), prefix) == 0; } // 检查字符串后缀 bool ends_with(const string& s, const string& suffix) { return s.size() >= suffix.size() && s.compare(s.size() - suffix.size(), suffix.size(), suffix) == 0; } // 检查字符串包含 bool contains(const string& s, const string& substr) { return s.find(substr) != string::npos; } // 回文串判断 bool is_palindrome(const string& s) { int left = 0, right = s.size() - 1; while (left < right) { if (s[left] != s[right]) { return false; } left++; right--; } return true; } // KMP 算法 vector<int> kmp_search(const string& text, const string& pattern) { vector<int> result; int n = text.size(), m = pattern.size(); if (m == 0) return result; vector<int> lps(m, 0); for (int i = 1, len = 0; i < m; ) { if (pattern[i] == pattern[len]) { lps[i++] = ++len; } else if (len > 0) { len = lps[len - 1]; } else { lps[i++] = 0; } } for (int i = 0, j = 0; i < n; ) { if (pattern[j] == text[i]) { i++; j++; if (j == m) { result.push_back(i - j); j = lps[j - 1]; } } else if (j > 0) { j = lps[j - 1]; } else { i++; } } return result; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 读取字符串 string s; getline(cin, s); // 分割 vector<string> tokens = split(s, ' '); for (const string& token : tokens) { cout << token << endl; } // 检查回文 string palindrome_candidate = "racecar"; if (is_palindrome(palindrome_candidate)) { cout << palindrome_candidate << " is a palindrome" << endl; } // KMP 查找 string text = "ABABDABACDABABCABAB"; string pattern = "ABABCABAB"; vector<int> positions = kmp_search(text, pattern); cout << "Pattern found at positions: "; for (int pos : positions) { cout << pos << " "; } cout << endl; // C++11 字符串检查 string test = "Hello, C++11!"; if (starts_with(test, "Hello")) { cout << "Starts with Hello" << endl; } if (ends_with(test, "!")) { cout << "Ends with !" << endl; } if (contains(test, "C++")) { cout << "Contains 'C++'" << endl; } return 0; } 总结：竞赛要点 基本操作：掌握字符串的基本操作，如访问、修改、拼接、查找等 性能优化：使用 reserve() 预分配空间，避免频繁拼接 现代 C++11：使用 auto 类型推导、范围 for 循环、lambda 表达式和自定义字符串检查函数 实战技巧：字符串分割、反转、回文判断、KMP 算法等 类型转换：字符串与数字之间的转换 内存管理：避免不必要的拷贝，使用引用和移动语义 边界处理：注意字符串索引的边界检查 编码问题：处理特殊字符和编码格式 string 是算法竞赛中最基础的工具之一，掌握它的使用技巧能让你在处理字符串相关问题时更加得心应手。

queue - 队列 std::queue 是基于先进先出 (FIFO) 原则的容器适配器，默认底层使用 deque 实现。在算法竞赛中，队列是实现广度优先搜索 (BFS) 的核心工具。 竞赛中的核心考点 操作 时间复杂度 竞赛要点 入队 (push) O(1) 向队尾添加元素 出队 (pop) O(1) 从队首移除元素 访问队首 (front) O(1) 获取队首元素 访问队尾 (back) O(1) 获取队尾元素 判空 (empty) O(1) 检查队列是否为空 大小 (size) O(1) 获取队列大小 一、基本用法 1.1 初始化 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 默认构造 queue<int> q; // 使用自定义容器（必须支持 front(), back(), push_back(), pop_front()） queue<int, list<int>> q_list; queue<int, deque<int>> q_deque; return 0; } 1.2 基本操作 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); queue<int> q; // 入队 q.push(10); q.push(20); q.push(30); // 访问队首和队尾 cout << "队首: " << q.front() << endl; // 10 cout << "队尾: " << q.back() << endl; // 30 // 出队 q.pop(); cout << "出队后队首: " << q.front() << endl; // 20 // 大小和判空 cout << "队列大小: " << q.size() << endl; // 2 cout << "队列是否为空: " << (q.empty() ? "是" : "否") << endl; // 否 // 清空队列 while (!q.empty()) { q.pop(); } cout << "清空后队列是否为空: " << (q.empty() ? "是" : "否") << endl; // 是 return 0; } 二、BFS 算法实现 2.1 基本 BFS 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; void bfs(int start, const vector<vector<int>>& adj) { int n = adj.size(); vector<bool> visited(n, false); queue<int> q; // 初始化 q.push(start); visited[start] = true; while (!q.empty()) { int u = q.front(); q.pop(); cout << u << " "; // 处理节点 // 访问邻接点 for (int v : adj[u]) { if (!visited[v]) { visited[v] = true; q.push(v); } } } } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 构建邻接表 int n = 6; vector<vector<int>> adj(n); adj[0] = {1, 2}; adj[1] = {0, 3, 4}; adj[2] = {0, 5}; adj[3] = {1}; adj[4] = {1}; adj[5] = {2}; cout << "BFS 遍历结果: "; bfs(0, adj); // 0 1 2 3 4 5 cout << endl; return 0; } 2.2 BFS 求最短路径 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; vector<int> shortest_path(int start, int end, const vector<vector<int>>& adj) { int n = adj.size(); vector<int> dist(n, -1); vector<int> parent(n, -1); queue<int> q; q.push(start); dist[start] = 0; while (!q.empty()) { int u = q.front(); q.pop(); if (u == end) { break; // 找到终点 } for (int v : adj[u]) { if (dist[v] == -1) { dist[v] = dist[u] + 1; parent[v] = u; q.push(v); } } } // 重建路径 vector<int> path; if (dist[end] == -1) { return path; // 无路径 } for (int v = end; v != -1; v = parent[v]) { path.push_back(v); } reverse(path.begin(), path.end()); return path; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n = 6; vector<vector<int>> adj(n); adj[0] = {1, 2}; adj[1] = {0, 3, 4}; adj[2] = {0, 5}; adj[3] = {1}; adj[4] = {1}; adj[5] = {2}; vector<int> path = shortest_path(0, 5, adj); cout << "最短路径: "; for (int v : path) { cout << v << " "; // 0 2 5 } cout << endl; return 0; } 三、竞赛实战应用 3.1 层序遍历 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 // 二叉树层序遍历 struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; vector<vector<int>> level_order(TreeNode* root) { vector<vector<int>> result; if (!root) { return result; } queue<TreeNode*> q; q.push(root); while (!q.empty()) { int level_size = q.size(); vector<int> level; for (int i = 0; i < level_size; i++) { TreeNode* node = q.front(); q.pop(); level.push_back(node->val); if (node->left) { q.push(node->left); } if (node->right) { q.push(node->right); } } result.push_back(level); } return result; } 3.2 多源 BFS 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 // 多源 BFS 求最短距离 vector<vector<int>> multi_source_bfs(int n, int m, const vector<pair<int, int>>& sources) { vector<vector<int>> dist(n, vector<int>(m, -1)); queue<pair<int, int>> q; // 初始化多个源点 for (const auto& source : sources) { int x = source.first; int y = source.second; dist[x][y] = 0; q.emplace(x, y); } // 四个方向 int dx[] = {-1, 1, 0, 0}; int dy[] = {0, 0, -1, 1}; while (!q.empty()) { pair<int, int> front = q.front(); int x = front.first; int y = front.second; q.pop(); for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx >= 0 && nx < n && ny >= 0 && ny < m && dist[nx][ny] == -1) { dist[nx][ny] = dist[x][y] + 1; q.emplace(nx, ny); } } } return dist; } 3.3 0-1 BFS 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 // 0-1 BFS 处理边权为 0 或 1 的图 vector<int> zero_one_bfs(int start, const vector<vector<pair<int, int>>>& adj) { int n = adj.size(); vector<int> dist(n, INT_MAX); deque<int> dq; // 使用双端队列 dist[start] = 0; dq.push_front(start); while (!dq.empty()) { int u = dq.front(); dq.pop_front(); for (const auto& edge : adj[u]) { int v = edge.first; int w = edge.second; if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; if (w == 0) { dq.push_front(v); // 权值为 0 放在队首 } else { dq.push_back(v); // 权值为 1 放在队尾 } } } } return dist; } 四、C++11 现代特性 4.1 使用 pair 元素访问 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); queue<pair<int, int>> q; q.emplace(1, 2); q.emplace(3, 4); while (!q.empty()) { pair<int, int> front = q.front(); int x = front.first; int y = front.second; cout << "x: " << x << ", y: " << y << endl; q.pop(); } return 0; } 4.2 使用列表初始化 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 可以通过 deque 初始化 queue deque<int> d = {1, 2, 3, 4, 5}; queue<int> q(d); while (!q.empty()) { cout << q.front() << " "; q.pop(); } // 输出: 1 2 3 4 5 return 0; } 五、性能优化 5.1 预分配空间 1 2 3 4 5 6 7 8 9 // 对于底层容器为 deque 的情况 queue<int> q; // 无法直接 reserve，但可以通过 deque 预分配 // 更好的做法：如果知道大致大小，使用 deque 预分配 int expected_size = 100000; deque<int> d; d.reserve(expected_size); queue<int> q(d); 5.2 避免不必要的拷贝 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 // 错误示范：值传递 void process_queue(queue<int> q) // 会拷贝整个队列 { // 处理 q } // 正确做法：使用引用 void process_queue(queue<int>& q) // 引用传递，无拷贝 { // 处理 q } // 使用移动语义 queue<int> create_queue() { queue<int> q; // 填充 q return q; // 移动语义，无拷贝 } 5.3 合理选择底层容器 底层容器 优点 缺点 适用场景 deque（默认） 两端操作高效 内存碎片 一般 BFS list 内存分配灵活 缓存不友好 频繁插入删除 vector 缓存友好 需要手动管理大小 固定大小的队列 六、常见错误与注意事项 错误 说明 解决方案 访问空队列 未定义行为 先检查 empty() BFS 中重复访问 导致无限循环 使用 visited 数组标记 内存使用过高 队列过大 考虑剪枝或优化算法 效率问题 频繁的 push/pop 选择合适的底层容器 路径重建错误 父节点指针未正确设置 确保每个节点都记录父节点 七、C++11 完整竞赛模板 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; // 基本 BFS void bfs(int start, const vector<vector<int>>& adj) { int n = adj.size(); vector<bool> visited(n, false); queue<int> q; q.push(start); visited[start] = true; while (!q.empty()) { int u = q.front(); q.pop(); cout << u << " "; for (int v : adj[u]) { if (!visited[v]) { visited[v] = true; q.push(v); } } } cout << endl; } // BFS 求最短路径 vector<int> shortest_path(int start, int end, const vector<vector<int>>& adj) { int n = adj.size(); vector<int> dist(n, -1); vector<int> parent(n, -1); queue<int> q; q.push(start); dist[start] = 0; while (!q.empty()) { int u = q.front(); q.pop(); if (u == end) { break; } for (int v : adj[u]) { if (dist[v] == -1) { dist[v] = dist[u] + 1; parent[v] = u; q.push(v); } } } vector<int> path; if (dist[end] == -1) { return path; } for (int v = end; v != -1; v = parent[v]) { path.push_back(v); } reverse(path.begin(), path.end()); return path; } // 多源 BFS vector<vector<int>> multi_source_bfs(int n, int m, const vector<pair<int, int>>& sources) { vector<vector<int>> dist(n, vector<int>(m, -1)); queue<pair<int, int>> q; for (const auto& source : sources) { int x = source.first; int y = source.second; dist[x][y] = 0; q.emplace(x, y); } int dx[] = {-1, 1, 0, 0}; int dy[] = {0, 0, -1, 1}; while (!q.empty()) { pair<int, int> front = q.front(); int x = front.first; int y = front.second; q.pop(); for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx >= 0 && nx < n && ny >= 0 && ny < m && dist[nx][ny] == -1) { dist[nx][ny] = dist[x][y] + 1; q.emplace(nx, ny); } } } return dist; } // 0-1 BFS vector<int> zero_one_bfs(int start, const vector<vector<pair<int, int>>>& adj) { int n = adj.size(); vector<int> dist(n, INT_MAX); deque<int> dq; dist[start] = 0; dq.push_front(start); while (!dq.empty()) { int u = dq.front(); dq.pop_front(); for (const auto& edge : adj[u]) { int v = edge.first; int w = edge.second; if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; if (w == 0) { dq.push_front(v); } else { dq.push_back(v); } } } } return dist; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 测试基本 BFS int n = 6; vector<vector<int>> adj(n); adj[0] = {1, 2}; adj[1] = {0, 3, 4}; adj[2] = {0, 5}; adj[3] = {1}; adj[4] = {1}; adj[5] = {2}; cout << "BFS 遍历: "; bfs(0, adj); // 测试最短路径 vector<int> path = shortest_path(0, 5, adj); cout << "最短路径: "; for (int v : path) { cout << v << " "; } cout << endl; // 测试多源 BFS int rows = 3, cols = 3; vector<pair<int, int>> sources = {{0, 0}, {2, 2}}; vector<vector<int>> dist = multi_source_bfs(rows, cols, sources); cout << "多源 BFS 距离矩阵: " << endl; for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { cout << dist[i][j] << " "; } cout << endl; } return 0; } 总结：竞赛要点 FIFO 特性：队列的先进先出特性是 BFS 的基础 BFS 算法：队列是实现 BFS 的标准工具 层序遍历：适用于树和图的层序访问 最短路径：在无权图中求最短路径 多源 BFS：处理多个起点的情况 0-1 BFS：处理边权为 0 或 1 的图 性能优化：选择合适的底层容器，避免不必要的拷贝 现代 C++11：使用 auto 类型推导、范围 for 循环和 emplace 原地构造 边界处理：注意队列判空，避免访问空队列 实战应用：图遍历、迷宫求解、网络流等 queue 是算法竞赛中解决广度优先搜索问题的核心工具，掌握它的使用技巧能让你在处理图论和搜索问题时更加得心应手。

deque - 双端队列 std::deque 是双端队列（double-ended queue）的缩写，支持在两端进行高效的插入和删除操作。在算法竞赛中，deque 是实现滑动窗口等高级算法的核心工具。 竞赛中的核心考点 操作 时间复杂度 竞赛要点 两端插入/删除 均摊 O(1) 高效的两端操作 随机访问 O(1) 支持索引访问 中间插入/删除 O(n) 避免在中间操作 大小操作 O(1) 快速获取大小和判空 一、基本用法 1.1 初始化 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 默认构造 deque<int> dq; // 大小构造 deque<int> dq1(5); // 5个默认值（0） deque<int> dq2(5, 10); // 5个值为10的元素 // 迭代器构造 vector<int> v = {1, 2, 3, 4, 5}; deque<int> dq3(v.begin(), v.end()); // 拷贝构造 deque<int> dq4(dq3); // 移动构造 deque<int> dq5(move(dq4)); return 0; } 1.2 基本操作 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); deque<int> dq; // 两端插入 dq.push_back(10); // 队尾插入 dq.push_front(20); // 队首插入 dq.emplace_back(30); // 原地构造 dq.emplace_front(40); // 原地构造 // dq: [40, 20, 10, 30] // 两端删除 dq.pop_back(); // 删除队尾 dq.pop_front(); // 删除队首 // dq: [20, 10] // 访问元素 cout << "队首: " << dq.front() << endl; // 20 cout << "队尾: " << dq.back() << endl; // 10 cout << "索引1: " << dq[1] << endl; // 10 cout << "索引1: " << dq.at(1) << endl; // 10（带边界检查） // 大小和判空 cout << "大小: " << dq.size() << endl; // 2 cout << "是否为空: " << (dq.empty() ? "是" : "否") << endl; // 否 // 清空 dq.clear(); cout << "清空后大小: " << dq.size() << endl; // 0 return 0; } 二、滑动窗口算法 2.1 滑动窗口最大值 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; vector<int> max_sliding_window(vector<int>& nums, int k) { vector<int> result; deque<int> dq; // 存储索引，维护单调递减队列 for (int i = 0; i < nums.size(); i++) { // 移除窗口外的元素 if (!dq.empty() && dq.front() == i - k) { dq.pop_front(); } // 维护单调递减队列 while (!dq.empty() && nums[dq.back()] <= nums[i]) { dq.pop_back(); } dq.push_back(i); // 窗口形成后开始记录结果 if (i >= k - 1) { result.push_back(nums[dq.front()]); } } return result; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7}; int k = 3; vector<int> result = max_sliding_window(nums, k); cout << "滑动窗口最大值: "; for (int x : result) { cout << x << " "; // 3 3 5 5 6 7 } cout << endl; return 0; } 2.2 滑动窗口最小值 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 vector<int> min_sliding_window(vector<int>& nums, int k) { vector<int> result; deque<int> dq; // 存储索引，维护单调递增队列 for (int i = 0; i < nums.size(); i++) { // 移除窗口外的元素 if (!dq.empty() && dq.front() == i - k) { dq.pop_front(); } // 维护单调递增队列 while (!dq.empty() && nums[dq.back()] >= nums[i]) { dq.pop_back(); } dq.push_back(i); // 窗口形成后开始记录结果 if (i >= k - 1) { result.push_back(nums[dq.front()]); } } return result; } 三、竞赛实战应用 3.1 双端队列实现栈和队列 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 // 使用 deque 实现栈 class MyStack { private: deque<int> dq; public: void push(int x) { dq.push_back(x); } int pop() { int x = dq.back(); dq.pop_back(); return x; } int top() { return dq.back(); } bool empty() { return dq.empty(); } }; // 使用 deque 实现队列 class MyQueue { private: deque<int> dq; public: void push(int x) { dq.push_back(x); } int pop() { int x = dq.front(); dq.pop_front(); return x; } int front() { return dq.front(); } bool empty() { return dq.empty(); } }; 3.2 0-1 BFS 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 // 0-1 BFS 处理边权为 0 或 1 的图 vector<int> zero_one_bfs(int start, const vector<vector<pair<int, int>>>& adj) { int n = adj.size(); vector<int> dist(n, INT_MAX); deque<int> dq; dist[start] = 0; dq.push_front(start); while (!dq.empty()) { int u = dq.front(); dq.pop_front(); for (const auto& edge : adj[u]) { int v = edge.first; int w = edge.second; if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; if (w == 0) { dq.push_front(v); // 权值为 0 放在队首 } else { dq.push_back(v); // 权值为 1 放在队尾 } } } } return dist; } 3.3 滑动窗口中位数 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 // 滑动窗口中位数（使用双端队列辅助） vector<double> median_sliding_window(vector<int>& nums, int k) { vector<double> result; multiset<int> window(nums.begin(), nums.begin() + k); auto mid = next(window.begin(), k / 2); for (int i = k; ; i++) { // 计算中位数 if (k % 2 == 0) { result.push_back((*mid + *prev(mid)) / 2.0); } else { result.push_back(*mid); } if (i == nums.size()) { break; } // 移除窗口左端元素 window.insert(nums[i]); if (nums[i] < *mid) { mid--; } // 插入新元素 if (nums[i - k] <= *mid) { mid++; } window.erase(window.lower_bound(nums[i - k])); } return result; } 四、C++11 现代特性 4.1 使用 pair 元素访问 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); deque<pair<int, string>> dq; dq.emplace_back(1, "apple"); dq.emplace_back(2, "banana"); for (const auto& p : dq) { int id = p.first; string name = p.second; cout << "id: " << id << ", name: " << name << endl; } return 0; } 4.2 使用标准算法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); deque<int> dq = {3, 1, 4, 1, 5, 9, 2, 6}; // C++11: sort sort(dq.begin(), dq.end()); // C++11: find auto it = find(dq.begin(), dq.end(), 5); if (it != dq.end()) { cout << "找到 5 在位置: " << distance(dq.begin(), it) << endl; } // C++11: 过滤偶数 cout << "偶数: "; for (int x : dq) { if (x % 2 == 0) { cout << x << " "; } } cout << endl; return 0; } 五、性能优化 5.1 预分配空间 1 2 3 4 5 6 7 // 预分配空间 int expected_size = 100000; deque<int> dq; dq.reserve(expected_size); // 注意：deque 的 reserve 只是一个提示 // 更有效的方式：直接构造足够大的 deque deque<int> dq(expected_size); 5.2 避免中间操作 1 2 3 4 5 6 7 // 错误示范：在中间插入元素 deque<int> dq = {1, 2, 3, 4, 5}; dq.insert(dq.begin() + 2, 10); // O(n) 操作 // 正确做法：优先在两端操作 dq.push_front(0); // O(1) dq.push_back(6); // O(1) 5.3 合理选择容器 容器 优点 缺点 适用场景 deque 两端操作高效，支持随机访问 内存碎片，中间操作慢 滑动窗口，双端操作 vector 缓存友好，随机访问快 两端操作慢 随机访问频繁，大小稳定 list 中间插入删除快 不支持随机访问，缓存不友好 频繁中间操作 六、常见错误与注意事项 错误 说明 解决方案 越界访问 访问超出范围的索引 使用 at() 或先检查大小 中间插入删除 导致性能下降 优先在两端操作 内存使用过高 deque 内存碎片 考虑使用 vector 或 list 迭代器失效 插入删除操作后迭代器失效 注意保存有效的迭代器 滑动窗口逻辑错误 窗口边界处理不当 仔细检查窗口大小和边界条件 七、C++11 完整竞赛模板 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; // 滑动窗口最大值 vector<int> max_sliding_window(vector<int>& nums, int k) { vector<int> result; deque<int> dq; for (int i = 0; i < nums.size(); i++) { // 移除窗口外的元素 if (!dq.empty() && dq.front() == i - k) { dq.pop_front(); } // 维护单调递减队列 while (!dq.empty() && nums[dq.back()] <= nums[i]) { dq.pop_back(); } dq.push_back(i); // 窗口形成后开始记录结果 if (i >= k - 1) { result.push_back(nums[dq.front()]); } } return result; } // 0-1 BFS vector<int> zero_one_bfs(int start, const vector<vector<pair<int, int>>>& adj) { int n = adj.size(); vector<int> dist(n, INT_MAX); deque<int> dq; dist[start] = 0; dq.push_front(start); while (!dq.empty()) { int u = dq.front(); dq.pop_front(); for (const auto& edge : adj[u]) { int v = edge.first; int w = edge.second; if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; if (w == 0) { dq.push_front(v); } else { dq.push_back(v); } } } } return dist; } // 双端队列实现栈 class MyStack { private: deque<int> dq; public: void push(int x) { dq.push_back(x); } int pop() { int x = dq.back(); dq.pop_back(); return x; } int top() { return dq.back(); } bool empty() { return dq.empty(); } }; // 双端队列实现队列 class MyQueue { private: deque<int> dq; public: void push(int x) { dq.push_back(x); } int pop() { int x = dq.front(); dq.pop_front(); return x; } int front() { return dq.front(); } bool empty() { return dq.empty(); } }; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 测试滑动窗口最大值 vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7}; int k = 3; vector<int> result = max_sliding_window(nums, k); cout << "滑动窗口最大值: "; for (int x : result) { cout << x << " "; } cout << endl; // 测试 0-1 BFS int n = 4; vector<vector<pair<int, int>>> adj(n); adj[0] = {{1, 0}, {2, 1}}; adj[1] = {{0, 0}, {3, 1}}; adj[2] = {{0, 1}, {3, 0}}; adj[3] = {{1, 1}, {2, 0}}; vector<int> dist = zero_one_bfs(0, adj); cout << "0-1 BFS 距离: "; for (int d : dist) { cout << d << " "; } cout << endl; // 测试栈实现 MyStack stack; stack.push(1); stack.push(2); stack.push(3); cout << "栈顶: " << stack.top() << endl; // 3 cout << "弹出: " << stack.pop() << endl; // 3 cout << "栈顶: " << stack.top() << endl; // 2 // 测试队列实现 MyQueue queue; queue.push(1); queue.push(2); queue.push(3); cout << "队首: " << queue.front() << endl; // 1 cout << "弹出: " << queue.pop() << endl; // 1 cout << "队首: " << queue.front() << endl; // 2 return 0; } 总结：竞赛要点 双端操作：deque 支持在两端进行高效的插入和删除操作 滑动窗口：deque 是实现滑动窗口算法的最佳选择 随机访问：支持 O(1) 的随机访问，比 list 更灵活 0-1 BFS：利用双端队列优化边权为 0 或 1 的图的最短路径 数据结构实现：可以用 deque 实现栈和队列 性能优化：优先在两端操作，避免中间插入删除 现代 C++11：使用 auto 类型推导、范围 for 循环和 emplace 原地构造 边界处理：注意迭代器失效和越界访问 实战应用：滑动窗口最大值、最小值、中位数等 deque 是算法竞赛中处理需要双端操作场景的强大工具，掌握它的使用技巧能让你在解决滑动窗口等问题时更加得心应手。

stack - 栈 std::stack 是基于后进先出 (LIFO) 原则的容器适配器，默认底层使用 deque 实现。在算法竞赛中，栈是实现深度优先搜索 (DFS) 和表达式求值的核心工具。 竞赛中的核心考点 操作 时间复杂度 竞赛要点 入栈 (push) O(1) 向栈顶添加元素 出栈 (pop) O(1) 从栈顶移除元素 访问栈顶 (top) O(1) 获取栈顶元素 判空 (empty) O(1) 检查栈是否为空 大小 (size) O(1) 获取栈大小 一、基本用法 1.1 初始化 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 默认构造 stack<int> s; // 使用自定义容器（必须支持 back(), push_back(), pop_back()） stack<int, vector<int>> s_vec; stack<int, deque<int>> s_deque; stack<int, list<int>> s_list; return 0; } 1.2 基本操作 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); stack<int> s; // 入栈 s.push(10); s.push(20); s.push(30); // 访问栈顶 cout << "栈顶: " << s.top() << endl; // 30 // 出栈 s.pop(); cout << "出栈后栈顶: " << s.top() << endl; // 20 // 大小和判空 cout << "栈大小: " << s.size() << endl; // 2 cout << "栈是否为空: " << (s.empty() ? "是" : "否") << endl; // 否 // 清空栈 while (!s.empty()) { s.pop(); } cout << "清空后栈是否为空: " << (s.empty() ? "是" : "否") << endl; // 是 return 0; } 二、DFS 算法实现 2.1 基本 DFS 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; void dfs(int start, const vector<vector<int>>& adj) { int n = adj.size(); vector<bool> visited(n, false); stack<int> s; // 初始化 s.push(start); visited[start] = true; while (!s.empty()) { int u = s.top(); s.pop(); cout << u << " "; // 处理节点 // 访问邻接点（注意顺序，栈是后进先出，所以反序入栈） for (auto it = adj[u].rbegin(); it != adj[u].rend(); ++it) { int v = *it; if (!visited[v]) { visited[v] = true; s.push(v); } } } } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 构建邻接表 int n = 6; vector<vector<int>> adj(n); adj[0] = {1, 2}; adj[1] = {0, 3, 4}; adj[2] = {0, 5}; adj[3] = {1}; adj[4] = {1}; adj[5] = {2}; cout << "DFS 遍历结果: "; dfs(0, adj); // 0 1 3 4 2 5 cout << endl; return 0; } 2.2 DFS 求路径 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; bool dfs_path(int start, int end, const vector<vector<int>>& adj, vector<bool>& visited, vector<int>& path) { visited[start] = true; path.push_back(start); if (start == end) { return true; } for (int v : adj[start]) { if (!visited[v]) { if (dfs_path(v, end, adj, visited, path)) { return true; } } } path.pop_back(); // 回溯 return false; } vector<int> find_path(int start, int end, const vector<vector<int>>& adj) { vector<int> path; vector<bool> visited(adj.size(), false); dfs_path(start, end, adj, visited, path); return path; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n = 6; vector<vector<int>> adj(n); adj[0] = {1, 2}; adj[1] = {0, 3, 4}; adj[2] = {0, 5}; adj[3] = {1}; adj[4] = {1}; adj[5] = {2}; vector<int> path = find_path(0, 5, adj); cout << "DFS 路径: "; for (int v : path) { cout << v << " "; // 0 2 5 } cout << endl; return 0; } 三、竞赛实战应用 3.1 表达式求值 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 // 计算后缀表达式 int evaluate_postfix(const vector<string>& tokens) { stack<int> s; for (const string& token : tokens) { if (token == "+" || token == "-" || token == "*" || token == "/") { int b = s.top(); s.pop(); int a = s.top(); s.pop(); if (token == "+") s.push(a + b); else if (token == "-") s.push(a - b); else if (token == "*") s.push(a * b); else if (token == "/") s.push(a / b); } else { s.push(stoi(token)); } } return s.top(); } // 中缀表达式转后缀表达式 vector<string> infix_to_postfix(const string& expr) { vector<string> postfix; stack<char> op_stack; unordered_map<char, int> precedence = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}, {'^', 3}}; for (int i = 0; i < expr.size(); i++) { char c = expr[i]; if (isdigit(c)) { string num; while (i < expr.size() && isdigit(expr[i])) { num += expr[i++]; } i--; postfix.push_back(num); } else if (c == '(') { op_stack.push(c); } else if (c == ')') { while (!op_stack.empty() && op_stack.top() != '(') { postfix.push_back(string(1, op_stack.top())); op_stack.pop(); } op_stack.pop(); // 弹出 '(' } else if (precedence.count(c)) { while (!op_stack.empty() && precedence.count(op_stack.top()) && precedence[op_stack.top()] >= precedence[c]) { postfix.push_back(string(1, op_stack.top())); op_stack.pop(); } op_stack.push(c); } } while (!op_stack.empty()) { postfix.push_back(string(1, op_stack.top())); op_stack.pop(); } return postfix; } 3.2 括号匹配 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 bool is_valid_parentheses(const string& s) { stack<char> stk; unordered_map<char, char> mapping = {{')', '('}, {']', '['}, {'}', '{'}}; for (char c : s) { if (mapping.count(c)) { char top_element = stk.empty() ? '#' : stk.top(); stk.pop(); if (top_element != mapping[c]) { return false; } } else { stk.push(c); } } return stk.empty(); } 3.3 单调栈 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 // 每日温度 vector<int> daily_temperatures(vector<int>& temperatures) { int n = temperatures.size(); vector<int> result(n, 0); stack<int> stk; // 存储索引 for (int i = n - 1; i >= 0; i--) { while (!stk.empty() && temperatures[stk.top()] <= temperatures[i]) { stk.pop(); } result[i] = stk.empty() ? 0 : stk.top() - i; stk.push(i); } return result; } // 下一个更大元素 vector<int> next_greater_element(vector<int>& nums) { int n = nums.size(); vector<int> result(n, -1); stack<int> stk; for (int i = n - 1; i >= 0; i--) { while (!stk.empty() && stk.top() <= nums[i]) { stk.pop(); } result[i] = stk.empty() ? -1 : stk.top(); stk.push(nums[i]); } return result; } 3.4 二叉树遍历 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 // 二叉树结构 struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; // 前序遍历（非递归） vector<int> preorder_traversal(TreeNode* root) { vector<int> result; if (!root) { return result; } stack<TreeNode*> stk; stk.push(root); while (!stk.empty()) { TreeNode* node = stk.top(); stk.pop(); result.push_back(node->val); // 先压右子树，再压左子树 if (node->right) { stk.push(node->right); } if (node->left) { stk.push(node->left); } } return result; } // 中序遍历（非递归） vector<int> inorder_traversal(TreeNode* root) { vector<int> result; stack<TreeNode*> stk; TreeNode* current = root; while (current || !stk.empty()) { while (current) { stk.push(current); current = current->left; } current = stk.top(); stk.pop(); result.push_back(current->val); current = current->right; } return result; } // 后序遍历（非递归） vector<int> postorder_traversal(TreeNode* root) { vector<int> result; if (!root) { return result; } stack<TreeNode*> stk1, stk2; stk1.push(root); while (!stk1.empty()) { TreeNode* node = stk1.top(); stk1.pop(); stk2.push(node); if (node->left) { stk1.push(node->left); } if (node->right) { stk1.push(node->right); } } while (!stk2.empty()) { result.push_back(stk2.top()->val); stk2.pop(); } return result; } 四、C++11 现代特性 4.1 使用 pair 元素访问 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); stack<pair<int, string>> stk; stk.emplace(1, "apple"); stk.emplace(2, "banana"); while (!stk.empty()) { pair<int, string> top = stk.top(); int id = top.first; string name = top.second; cout << "id: " << id << ", name: " << name << endl; stk.pop(); } return 0; } 4.2 使用列表初始化 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 可以通过 deque 初始化 stack deque<int> d = {1, 2, 3, 4, 5}; stack<int> stk(d); while (!stk.empty()) { cout << stk.top() << " "; stk.pop(); } // 输出: 5 4 3 2 1 return 0; } 五、性能优化 5.1 预分配空间 1 2 3 4 5 6 7 8 9 10 11 12 13 // 对于底层容器为 vector 的情况 stack<int, vector<int>> stk; // 可以通过 vector 预分配空间 vector<int> vec; vec.reserve(100000); stack<int, vector<int>> stk2(vec); // 对于底层容器为 deque 的情况 stack<int> stk3; // 无法直接 reserve，但可以通过 deque 预分配 deque<int> dq; dq.reserve(100000); stack<int> stk4(dq); 5.2 避免不必要的拷贝 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 // 错误示范：值传递 void process_stack(stack<int> stk) // 会拷贝整个栈 { // 处理 stk } // 正确做法：使用引用 void process_stack(stack<int>& stk) // 引用传递，无拷贝 { // 处理 stk } // 使用移动语义 stack<int> create_stack() { stack<int> stk; // 填充 stk return stk; // 移动语义，无拷贝 } 5.3 合理选择底层容器 底层容器 优点 缺点 适用场景 deque（默认） 两端操作高效 内存碎片 一般使用 vector 缓存友好 扩容开销 大小稳定 list 内存分配灵活 缓存不友好 频繁插入删除 六、常见错误与注意事项 错误 说明 解决方案 访问空栈 未定义行为 先检查 empty() DFS 中栈溢出 递归深度过大 使用非递归 DFS 单调栈逻辑错误 顺序处理不当 仔细检查入栈出栈条件 表达式求值错误 运算符优先级处理错误 正确实现中缀转后缀 内存使用过高 栈存储过多元素 考虑剪枝或优化算法 七、C++11 完整竞赛模板 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; // 基本 DFS void dfs(int start, const vector<vector<int>>& adj) { int n = adj.size(); vector<bool> visited(n, false); stack<int> s; s.push(start); visited[start] = true; while (!s.empty()) { int u = s.top(); s.pop(); cout << u << " "; for (auto it = adj[u].rbegin(); it != adj[u].rend(); ++it) { int v = *it; if (!visited[v]) { visited[v] = true; s.push(v); } } } cout << endl; } // 括号匹配 bool is_valid_parentheses(const string& s) { stack<char> stk; unordered_map<char, char> mapping = {{')', '('}, {']', '['}, {'}', '{'}}; for (char c : s) { if (mapping.count(c)) { char top_element = stk.empty() ? '#' : stk.top(); stk.pop(); if (top_element != mapping[c]) { return false; } } else { stk.push(c); } } return stk.empty(); } // 每日温度 vector<int> daily_temperatures(vector<int>& temperatures) { int n = temperatures.size(); vector<int> result(n, 0); stack<int> stk; for (int i = n - 1; i >= 0; i--) { while (!stk.empty() && temperatures[stk.top()] <= temperatures[i]) { stk.pop(); } result[i] = stk.empty() ? 0 : stk.top() - i; stk.push(i); } return result; } // 表达式求值 int evaluate_postfix(const vector<string>& tokens) { stack<int> s; for (const string& token : tokens) { if (token == "+" || token == "-" || token == "*" || token == "/") { int b = s.top(); s.pop(); int a = s.top(); s.pop(); if (token == "+" || token == "-") s.push(token == "+" ? a + b : a - b); else s.push(token == "*" ? a * b : a / b); } else { s.push(stoi(token)); } } return s.top(); } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 测试 DFS int n = 6; vector<vector<int>> adj(n); adj[0] = {1, 2}; adj[1] = {0, 3, 4}; adj[2] = {0, 5}; adj[3] = {1}; adj[4] = {1}; adj[5] = {2}; cout << "DFS 遍历: "; dfs(0, adj); // 测试括号匹配 string s = "{[]()}"; cout << "括号匹配: " << (is_valid_parentheses(s) ? "有效" : "无效") << endl; // 测试每日温度 vector<int> temperatures = {73, 74, 75, 71, 69, 72, 76, 73}; vector<int> result = daily_temperatures(temperatures); cout << "每日温度: "; for (int x : result) { cout << x << " "; } cout << endl; // 测试表达式求值 vector<string> tokens = {"2", "1", "+", "3", "*"}; cout << "表达式求值: " << evaluate_postfix(tokens) << endl; // (2+1)*3=9 return 0; } 总结：竞赛要点 LIFO 特性：栈的后进先出特性是 DFS 的基础 DFS 算法：栈是实现非递归 DFS 的标准工具 表达式求值：栈用于处理中缀、后缀表达式 括号匹配：栈是解决括号匹配问题的最佳选择 单调栈：用于解决下一个更大元素、每日温度等问题 二叉树遍历：栈用于实现非递归的树遍历 性能优化：选择合适的底层容器，避免不必要的拷贝 现代 C++11：使用 auto 类型推导、范围 for 循环和 emplace 原地构造 边界处理：注意栈判空，避免访问空栈 实战应用：图遍历、表达式处理、单调栈问题等 stack 是算法竞赛中解决后进先出问题的核心工具，掌握它的使用技巧能让你在处理深度优先搜索和表达式求值等问题时更加得心应手。

bitset - 位运算优化 std::bitset 是一个固定大小的位集合，提供了高效的位操作功能。在算法竞赛中，bitset 是进行位运算优化的强大工具，特别适合处理状态压缩和位掩码等问题。 竞赛中的核心考点 操作 时间复杂度 竞赛要点 位设置 (set) O(1) 设置特定位为 1 位清除 (reset) O(1) 设置特定位为 0 位翻转 (flip) O(1) 翻转特定位 位测试 (test) O(1) 测试特定位是否为 1 位运算 (&, , ^, ~) O(n/w) 按位运算，n 是位数，w 是机器字长 计数 (count) O(n/w) 统计置位的位数 查找 (find_first, find_next) O(n/w) 查找置位的位 一、基本用法 1.1 初始化 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 默认构造（全 0） bitset<8> b1; // 整数构造 bitset<8> b2(42); // 00101010 // 字符串构造 bitset<8> b3("10101010"); // 拷贝构造 bitset<8> b4(b2); // 移动构造 bitset<8> b5(move(b4)); return 0; } 1.2 基本操作 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); bitset<8> b; // 设置位 b.set(0); // 第0位设为1 b.set(2, 1); // 第2位设为1 b.set(); // 所有位设为1 // 清除位 b.reset(0); // 第0位设为0 b.reset(); // 所有位设为0 // 翻转位 b.flip(1); // 翻转第1位 b.flip(); // 翻转所有位 // 测试位 bool is_set = b.test(0); bool any_set = b.any(); // 是否有位为1 bool all_set = b.all(); // 是否所有位为1 bool none_set = b.none(); // 是否所有位为0 // 计数 int count = b.count(); // 置位的位数 // 大小 size_t size = b.size(); // 总位数 // 转换 unsigned long ul = b.to_ulong(); unsigned long long ull = b.to_ullong(); string s = b.to_string(); return 0; } 二、位运算 2.1 基本位运算 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); bitset<4> a("1010"); // 10 bitset<4> b("1100"); // 12 // 按位与 bitset<4> c = a & b; // 1000 (8) // 按位或 bitset<4> d = a | b; // 1110 (14) // 按位异或 bitset<4> e = a ^ b; // 0110 (6) // 按位取反 bitset<4> f = ~a; // 0101 (5) // 左移 bitset<4> g = a << 1; // 0100 (4) // 右移 bitset<4> h = a >> 1; // 0101 (5) cout << "a: " << a << endl; cout << "b: " << b << endl; cout << "a & b: " << c << endl; cout << "a | b: " << d << endl; cout << "a ^ b: " << e << endl; cout << "~a: " << f << endl; cout << "a << 1: " << g << endl; cout << "a >> 1: " << h << endl; return 0; } 2.2 复合赋值运算 1 2 3 4 5 6 7 8 9 bitset<8> a("10101010"); bitset<8> b("11001100"); // 复合赋值 a &= b; // 等价于 a = a & b a |= b; // 等价于 a = a | b a ^= b; // 等价于 a = a ^ b a <<= 2; // 等价于 a = a << 2 a >>= 2; // 等价于 a = a >> 2 三、竞赛实战应用 3.1 状态压缩 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 // 子集枚举 void enumerate_subsets(int n) { for (int mask = 0; mask < (1 << n); mask++) { bitset<32> bits(mask); cout << "Mask " << mask << ": "; for (int i = 0; i < n; i++) { if (bits.test(i)) { cout << i << " "; } } cout << endl; } } // 集合操作 bitset<100> set_union(const bitset<100>& a, const bitset<100>& b) { return a | b; } bitset<100> set_intersection(const bitset<100>& a, const bitset<100>& b) { return a & b; } bitset<100> set_difference(const bitset<100>& a, const bitset<100>& b) { return a & ~b; } 3.2 位掩码优化 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 // 位掩码表示方向 const int UP = 1 << 0; const int DOWN = 1 << 1; const int LEFT = 1 << 2; const int RIGHT = 1 << 3; // 检查是否可以移动 bool can_move(int directions, int dir) { return (directions & dir) != 0; } // 添加方向 int add_direction(int directions, int dir) { return directions | dir; } // 移除方向 int remove_direction(int directions, int dir) { return directions & ~dir; } 3.3 快速统计 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 // 统计二进制中 1 的个数 int count_ones(int x) { bitset<32> bits(x); return bits.count(); } // 检查是否是 2 的幂 bool is_power_of_two(int x) { if (x == 0) { return false; } bitset<32> bits(x); return bits.count() == 1; } // 查找最低位的 1 int find_lowest_set_bit(int x) { bitset<32> bits(x); return bits._Find_first(); } // 查找最高位的 1 int find_highest_set_bit(int x) { bitset<32> bits(x); int pos = -1; for (int i = 31; i >= 0; i--) { if (bits.test(i)) { pos = i; break; } } return pos; } 3.4 动态规划优化 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 // 旅行商问题 (TSP) 状态压缩 DP int tsp(const vector<vector<int>>& dist) { int n = dist.size(); int full_mask = (1 << n) - 1; vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX)); // 初始化：从各个城市出发 for (int i = 0; i < n; i++) { dp[1 << i][i] = 0; } // 状态转移 for (int mask = 0; mask < (1 << n); mask++) { for (int u = 0; u < n; u++) { if (!(mask & (1 << u)) || dp[mask][u] == INT_MAX) { continue; } for (int v = 0; v < n; v++) { if (!(mask & (1 << v)) && dist[u][v] != INT_MAX) { int new_mask = mask | (1 << v); if (dp[new_mask][v] > dp[mask][u] + dist[u][v]) { dp[new_mask][v] = dp[mask][u] + dist[u][v]; } } } } } // 找最小路径 int result = INT_MAX; for (int i = 0; i < n; i++) { if (dp[full_mask][i] != INT_MAX) { result = min(result, dp[full_mask][i] + dist[i][0]); } } return result; } 3.5 位图 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 // 位图实现 class BitMap { private: bitset<1000000> bits; public: void set(int x) { bits.set(x); } void clear(int x) { bits.reset(x); } bool test(int x) { return bits.test(x); } int count() { return bits.count(); } }; // 用于快速去重和存在性检查 void deduplicate(vector<int>& nums) { bitset<1000000> seen; vector<int> result; for (int x : nums) { if (!seen.test(x)) { seen.set(x); result.push_back(x); } } nums.swap(result); } 四、C++11 现代特性 4.1 位操作函数 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); bitset<8> b("10101010"); // 查找第一个置位的位 size_t first = b._Find_first(); cout << "第一个置位的位: " << first << endl; // 查找下一个置位的位 size_t next = b._Find_next(first); cout << "下一个置位的位: " << next << endl; return 0; } 4.2 位掩码与枚举 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; // C++11 强类型枚举 enum class Direction : int { UP = 1 << 0, DOWN = 1 << 1, LEFT = 1 << 2, RIGHT = 1 << 3 }; // 重载位运算符 Direction operator|(Direction a, Direction b) { return static_cast<Direction>(static_cast<int>(a) | static_cast<int>(b)); } Direction operator&(Direction a, Direction b) { return static_cast<Direction>(static_cast<int>(a) & static_cast<int>(b)); } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); Direction dir = Direction::UP | Direction::RIGHT; bool can_go_up = (dir & Direction::UP) != static_cast<Direction>(0); cout << "Can go up: " << can_go_up << endl; return 0; } 五、性能优化 5.1 位操作优化 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 // 错误示范：使用循环进行位操作 int count_ones_slow(int x) { int count = 0; while (x) { count += x & 1; x >>= 1; } return count; } // 正确做法：使用 bitset int count_ones_fast(int x) { return bitset<32>(x).count(); } // 更高效：使用内置函数 int count_ones_builtin(int x) { return __builtin_popcount(x); } 5.2 内存优化 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 // 错误示范：使用 vector<bool> vector<bool> flags(1000000); // 虽然节省空间，但访问慢 // 正确做法：使用 bitset bitset<1000000> flags; // 更高效的位操作 // 或者使用 bitset 数组处理更大的范围 const int MAX_SIZE = 10000000; const int BITSET_SIZE = 1000000; vector<bitset<BITSET_SIZE>> flags(MAX_SIZE / BITSET_SIZE + 1); void set_bit(int x) { int idx = x / BITSET_SIZE; int offset = x % BITSET_SIZE; flags[idx].set(offset); } bool test_bit(int x) { int idx = x / BITSET_SIZE; int offset = x % BITSET_SIZE; return flags[idx].test(offset); } 5.3 运算优化 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 // 利用位运算的短路特性 bool is_subset(bitset<32> a, bitset<32> b) { // 检查 a 是否是 b 的子集 return (a & b) == a; } // 快速计算交集大小 int intersection_size(bitset<100> a, bitset<100> b) { return (a & b).count(); } // 快速计算并集大小 int union_size(bitset<100> a, bitset<100> b) { return (a | b).count(); } 六、常见错误与注意事项 错误 说明 解决方案 越界访问 访问超出 bitset 大小的位 确保位索引在有效范围内 位序理解错误 低位在前还是高位在前 注意 bitset 的位序（从右到左） 性能瓶颈 对于大位数的 bitset 操作 考虑分块处理或使用其他数据结构 内存使用 过大的 bitset 导致栈溢出 使用动态分配或分块处理 类型转换错误 转换为整数时溢出 确保 bitset 大小不超过目标类型 位运算优先级 位运算优先级低于比较运算符 使用括号确保运算顺序 七、C++11 完整竞赛模板 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; // 子集枚举 void enumerate_subsets(int n) { for (int mask = 0; mask < (1 << n); mask++) { bitset<32> bits(mask); cout << "Mask " << mask << ": "; for (int i = 0; i < n; i++) { if (bits.test(i)) { cout << i << " "; } } cout << endl; } } // 快速统计二进制中 1 的个数 int count_ones(int x) { return bitset<32>(x).count(); } // 检查是否是 2 的幂 bool is_power_of_two(int x) { if (x == 0) { return false; } return bitset<32>(x).count() == 1; } // 查找最低位的 1 int find_lowest_set_bit(int x) { if (x == 0) { return -1; } bitset<32> bits(x); return bits._Find_first(); } // 位图类 class BitMap { private: bitset<1000000> bits; public: void set(int x) { bits.set(x); } void clear(int x) { bits.reset(x); } bool test(int x) { return bits.test(x); } int count() { return bits.count(); } }; // 旅行商问题 (TSP) 状态压缩 DP int tsp(const vector<vector<int>>& dist) { int n = dist.size(); int full_mask = (1 << n) - 1; vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX)); for (int i = 0; i < n; i++) { dp[1 << i][i] = 0; } for (int mask = 0; mask < (1 << n); mask++) { for (int u = 0; u < n; u++) { if (!(mask & (1 << u)) || dp[mask][u] == INT_MAX) { continue; } for (int v = 0; v < n; v++) { if (!(mask & (1 << v)) && dist[u][v] != INT_MAX) { int new_mask = mask | (1 << v); if (dp[new_mask][v] > dp[mask][u] + dist[u][v]) { dp[new_mask][v] = dp[mask][u] + dist[u][v]; } } } } } int result = INT_MAX; for (int i = 0; i < n; i++) { if (dp[full_mask][i] != INT_MAX) { result = min(result, dp[full_mask][i] + dist[i][0]); } } return result; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 测试子集枚举 cout << "子集枚举 (n=3): " << endl; enumerate_subsets(3); // 测试位统计 int x = 42; // 101010 cout << "\n二进制 " << bitset<8>(x) << " 中 1 的个数: " << count_ones(x) << endl; cout << "是否是 2 的幂: " << is_power_of_two(x) << endl; cout << "最低位的 1 的位置: " << find_lowest_set_bit(x) << endl; // 测试位图 BitMap bm; bm.set(10); bm.set(20); bm.set(30); cout << "\n位图中 1 的个数: " << bm.count() << endl; cout << "测试位 10: " << bm.test(10) << endl; cout << "测试位 15: " << bm.test(15) << endl; // 测试 TSP vector<vector<int>> dist = { {0, 10, 15, 20}, {10, 0, 35, 25}, {15, 35, 0, 30}, {20, 25, 30, 0} }; int tsp_result = tsp(dist); cout << "\nTSP 最短路径: " << tsp_result << endl; return 0; } 总结：竞赛要点 位操作效率：bitset 提供高效的位操作，比手动位运算更简洁 状态压缩：适用于处理子集、掩码等状态压缩问题 内存节省：bitset 比 bool 数组更节省内存 位运算优化：利用位运算的并行性提高计算效率 集合操作：快速进行集合的并、交、差运算 动态规划：在 TSP 等问题中用于状态表示 位图应用：用于快速去重和存在性检查 现代 C++：使用 C++11 强类型枚举和位运算符重载 性能优化：结合内置函数和分块处理提高性能 实战应用：子集枚举、位掩码、状态压缩 DP 等 bitset 是算法竞赛中进行位运算优化的强大工具，掌握它的使用技巧能让你在处理状态压缩和位操作问题时更加得心应手。