概述
C++ 标准模板库(Standard Template Library,STL)是一套功能强大的 C++ 模板类和函数的集合,它提供了一系列通用的、可复用的算法和数据结构。
本文将讲解 C++11 中最常用的 STL 及其用法,附带例题。
算法部分
一、sort
- 作用:对指定范围内的元素进行排序,默认按升序排列,也可通过自定义比较器指定排序规则
- 模板:
sort(iterator begin, iterator end, function comp)
本文系统讲解了 C++ STL 标准模板库的核心内容,涵盖常用算法(如 sort、nth_element、lower_bound 等)和容器(如 vector、queue、stack、map 等)的用法。通过代码示例和洛谷例题,帮助读者掌握 STL 在实际编程中的应用,适合非零基础开发者复习提升。
C++ 标准模板库(Standard Template Library,STL)是一套功能强大的 C++ 模板类和函数的集合,它提供了一系列通用的、可复用的算法和数据结构。
本文将讲解 C++11 中最常用的 STL 及其用法,附带例题。
sort(iterator begin, iterator end, function comp)greater<>(),用于实现降序排序#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> v1 = {9, 5, 1, 2, 4, 6, 8, 3, 0, 7};
vector<int> v2 = {9, 5, 1, 2, 4, 6, 8, 3, 0, 7};
vector<int> v3 = {9, 5, 1, 2, 4, 6, 8, 3, 0, 7};
// 1. 默认从小到大的升序排序
sort(v1.begin(), v1.end());
for (auto& x : v1){ cout << x << " "; }
cout << endl;
// 2. 使用预定义函数对象实现降序排序
sort(v2.begin(), v2.end(), greater<int>());
for (auto& x : v2){ cout << x << " "; }
cout << endl;
// 3. 使用自定义函数实现任意排序
sort(v3.begin(), v3.end(), [](int a, int b) {
if ((a % 2) != (b % 2)) {
return (a % 2) > (b % 2);
}
return a < b;
});
for (auto& x : v3){ cout << x << " "; }
cout << endl;
}
nth_element(Iterator begin, Iterator nth, Iterator end, function comp)greater<>(),用于实现降序排序#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> v1 = {5, 2, 8, 1, 9, 3, 6, 4, 7, 0};
vector<int> v2 = {5, 2, 8, 1, 9, 3, 6, 4, 7, 0};
vector<int> v3 = {5, 2, 8, 1, 9, 3, 6, 4, 7, 0};
vector<int> v4 = {5, 2, 8, 1, 9, 3, 6, 4, 7, 0};
// 1. 查询第五小的元素
nth_element(v1.begin(), v1.begin() + 4, v1.end());
cout << "第 5 小的元素是:" << v1[4] << endl;
// 2. 查找前 k 个最小元素
nth_element(v2.begin(), v2.begin() + 3, v2.end());
cout << "前 3 小的元素:";
for (int i = 0; i < 3; i++) { cout << v2[i] << " "; }
cout << endl;
// 3. 使用自定义预定义函数对象
nth_element(v3.begin(), v3.begin() + 2, v3.end(), greater<int>());
cout << "第 3 大的元素是:" << v3[2] << endl;
// 4. 寻找中位数
int nums = v4.size();
if(nums % 2 != 0){
nth_element(v4.begin(), v4.begin() + nums/2, v4.end());
}else{
nth_element(v4.begin(), v4.begin() + nums/2, v4.end());
int right_mid = v4[nums/2];
nth_element(v4.begin(), v4.begin() + nums/2 - 1, v4.begin() + nums/2);
int left_mid = v4[nums/2 - 1];
double median = (left_mid + right_mid) / 2.0;
cout << "中位数:" << median << endl;
}
}
lower_bound(Iterator begin, Iterator end, Type v, Function comp) / upper_bound(Iterator begin, Iterator end, Type v, Function comp)greater<>(),用于实现降序排序#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> v = {1, 2, 2, 2, 3, 4, 4, 5, 7, 9};
// 1. lower_bound: 查找第一个 >= target 的元素位置
int target1 = 3;
auto lb1 = lower_bound(v.begin(), v.end(), target1);
cout << " 第一个 >= 3 的元素位置:索引 " << (lb1 - v.begin()) << endl;
cout << " 对应元素值:" << *lb1 << endl << endl;
// 2. upper_bound: 查找第一个 > target 的元素位置
int target2 = 3;
auto ub2 = upper_bound(v.begin(), v.end(), target2);
cout << " 第一个 > 3 的元素位置:索引 " << (ub2 - v.begin()) << endl;
cout << " 对应元素值:" << *ub2 << endl << endl;
// 3. 查找重复元素的范围
int target3 = 2;
auto lb3 = lower_bound(v.begin(), v.end(), target3);
auto ub3 = upper_bound(v.begin(), v.end(), target3);
cout << " 元素 2 的范围:[" << (lb3 - v.begin()) << ", " << (ub3 - v.begin()) << ")" << endl;
cout << " 元素 2 的个数:" << (ub3 - lb3) << endl << endl;
// 4. 在降序数组中查找
vector<int> v_desc = {9, 7, 5, 5, 5, 3, 1};
int target5 = 5;
auto lb5 = lower_bound(v_desc.begin(), v_desc.end(), target5, greater<int>());
auto ub5 = upper_bound(v_desc.begin(), v_desc.end(), target5, greater<int>());
cout << " lower_bound(5) 位置:索引 " << (lb5 - v_desc.begin()) << endl;
cout << " upper_bound(5) 位置:索引 " << (ub5 - v_desc.begin()) << endl;
cout << " 元素 5 的个数:" << (ub5 - lb5) << endl << endl;
// 5. 检查元素是否存在
int target6 = 4;
cout << "5. 检查元素 4 是否存在:" << endl;
auto it = lower_bound(v.begin(), v.end(), target6);
if (it != v.end() && *it == target6) {
cout << " 元素 4 存在,位置:索引 " << (it - v.begin()) << endl;
} else {
cout << " 元素 4 不存在" << endl;
}
cout << endl;
// 6. 查找插入位置保持有序
int new_element = 6;
auto insert_pos = lower_bound(v.begin(), v.end(), new_element);
cout << "插入元素 " << new_element << " 保持有序:" << endl;
cout << " 应该插入在索引:" << (insert_pos - v.begin()) << endl;
v.insert(insert_pos, new_element);
cout << " 插入后数组:";
for (auto& x : v) { cout << x << " "; }
cout << endl;
return 0;
}
false。bool 是 next_permutation 和 prev_permutation 函数的返回值类型,用来表示是否成功生成了下一个/上一个排列。next_permutation(Iterator begin, Iterator end) prev_permutation(Iterator begin, Iterator end)#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> v1 = {1, 2, 3};
vector<int> v2 = {1, 2, 3};
vector<int> v3 = {1, 2, 3};
// 1. 使用 next_permutation 生成所有排列
cout << "1. 使用 next_permutation 生成所有排列:" << endl;
int count1 = 1;
do {
cout << "第" << count1 << "个排列:";
for (auto& x : v1) { cout << x << " "; }
cout << endl;
count1++;
} while (next_permutation(v1.begin(), v1.end()));
cout << endl;
// 2. 使用 prev_permutation 生成所有排列
sort(v2.begin(), v2.end(), greater<int>());
cout << "2. 使用 prev_permutation 生成所有排列:" << endl;
cout << " (先降序排序:";
for (auto& x : v2) cout << x << " ";
cout << ")" << endl;
int count2 = 1;
do {
cout << " 第" << count2 << "个排列:";
for (auto& x : v2) { cout << x << " "; }
cout << endl;
count2++;
} while (prev_permutation(v2.begin(), v2.end()));
cout << endl;
// 3. 只生成下一个排列
cout << "3. 只生成下一个排列:" << endl;
cout << "当前排列:";
for (auto& x : v3) { cout << x << " "; }
cout << endl;
bool has_next = next_permutation(v3.begin(), v3.end());
cout << " 下一个排列:";
for (auto& x : v3) { cout << x << " "; }
cout << endl;
has_next = next_permutation(v3.begin(), v3.end());
cout << " 下一个排列:";
for (auto& x : v3) { cout << x << " "; }
cout << endl;
cout << endl;
// 4. 处理有重复元素的数组
vector<int> v4 = {1, 2, 2};
cout << "4. 有重复元素 {1, 2, 2} 的排列:" << endl;
sort(v4.begin(), v4.end());
int count3 = 0;
do {
cout << " 排列" << ++count3 << ": ";
for (auto& x : v4) { cout << x << " "; }
cout << endl;
} while (next_permutation(v4.begin(), v4.end()));
cout << endl;
}
unique(iterator begin, iterator end, function matcher)#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> v1 = {1, 1, 2, 2, 2, 3, 3, 4, 4, 4, 5};
vector<int> v2 = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
vector<int> v3 = {1, 3, 2, 4, 6, 5, 7, 9, 8};
vector<int> v4 = {12, 15, 18, 23, 25, 34, 37, 45, 48};
// 1. 默认用法:去除相邻重复元素
cout << "1. 默认用法(去除相邻重复元素):" << endl;
vector<int> temp1 = v1;
auto new_end1 = unique(temp1.begin(), temp1.end());
cout << " 去重后:";
for (auto it = temp1.begin(); it != new_end1; it++) { cout << *it << " "; }
cout << endl;
// 2. 配合 sort 去除所有重复元素
cout << "2. 配合 sort 去除所有重复元素:" << endl;
vector<int> temp2 = v2;
sort(temp2.begin(), temp2.end());
auto new_end2 = unique(temp2.begin(), temp2.end());
temp2.erase(new_end2, temp2.end());
cout << " 去重后:";
for (auto& x : temp2) cout << x << " ";
cout << endl;
// 3. 使用自定义比较函数
cout << "3. 使用自定义比较函数(按十位数分组):" << endl;
sort(v4.begin(), v4.end(), [](int a, int b) { return a < b; });
auto new_end4 = unique(v4.begin(), v4.end(), [](int a, int b) { return (a / 10) == (b / 10); });
cout << " 去重后(每个十位数组保留第一个):";
for (auto it = v4.begin(); it != new_end4; it++) { cout << *it << " "; }
cout << endl;
}
minmax_element(iterator begin, iterator end, function comp)#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> v1 = {9, 5, 1, 2, 4, 6, 8, 3, 0, 7};
vector<int> v2 = {9, 5, 1, 2, 4, 6, 8, 3, 0, 7};
vector<int> v3 = {-9, 5, 1, 2, 4, 6, 8, 3, 0, 7};
// 1. 查找最大元素
auto max_it = max_element(v1.begin(), v1.end());
cout << " 最大值:" << *max_it << endl;
cout << " 最大值位置:索引 " << (max_it - v1.begin()) << endl;
cout << endl;
// 2. 查找最小元素
auto min_it = min_element(v2.begin(), v2.end());
cout << " 最小值:" << *min_it << endl;
cout << " 最小值位置:索引 " << (min_it - v2.begin()) << endl;
cout << endl;
// 3. 使用自定义比较函数
auto abs_max_it = max_element(v3.begin(), v3.end(), [](int a, int b) { return abs(a) < abs(b); });
cout << " 绝对值最大的元素:" << *abs_max_it << endl;
cout << " 绝对值:" << abs(*abs_max_it) << endl;
cout << " 位置:索引 " << (abs_max_it - v3.begin()) << endl;
cout << endl;
// 4. 同时查找最小和最大值(C++11)
auto [min_it2, max_it2] = minmax_element(v1.begin(), v1.end());
cout << " 最小值:" << *min_it2 << " (索引:" << (min_it2 - v1.begin()) << ")" << endl;
cout << " 最大值:" << *max_it2 << " (索引:" << (max_it2 - v1.begin()) << ")" << endl;
cout << endl;
// 5. 在子范围中查找
auto sub_min = min_element(v1.begin() + 2, v1.begin() + 7);
auto sub_max = max_element(v1.begin() + 2, v1.begin() + 7);
cout << " 子数组:";
for (int i = 2; i < 7; i++) { cout << v1[i] << " "; }
cout << endl;
cout << " 子数组最小值:" << *sub_min << " (相对索引:" << (sub_min - v1.begin()) << ")" << endl;
cout << " 子数组最大值:" << *sub_max << " (相对索引:" << (sub_max - v1.begin()) << ")" << endl;
return 0;
}
accumulate(iterator begin, iterator end, type init, function operator)multiplies<int>()#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> v1 = {1, 2, 3, 4, 5};
vector<int> v2 = {1, 2, 3, 4, 5};
vector<int> v3 = {1, 2, 3, 4, 5};
// 1. 默认累加(求和)
int sum = accumulate(v1.begin(), v1.end(), 0);
cout << " 1+2+3+4+5 = " << sum << endl;
cout << endl;
// 2. 使用预定义函数对象(乘法累加)
int product = accumulate(v2.begin(), v2.end(), 1, multiplies<int>());
cout << " 1×2×3×4×5 = " << product << endl;
cout << endl;
// 3. 使用自定义函数(绝对值累加)
vector<int> nums = {1, -2, 3, -4, 5};
int abs_sum = accumulate(nums.begin(), nums.end(), 0, [](int total, int x) { return total + abs(x); });
cout << " 数组:";
for (auto& x : nums) cout << x << " ";
cout << endl;
cout << " |1| + |-2| + |3| + |-4| + |5| = " << abs_sum << endl;
cout << endl;
return 0;
}
count() 统计容器中等于指定值的元素个数。find() 在容器中查找指定值第一次出现的位置,返回迭代器。fill() 将容器中指定范围内的所有元素赋值为指定值。swap() 交换两个变量的值。reverse() 反转容器中指定范围的元素顺序。shuffle() 随机重排容器中元素的顺序。max()/ min() 返回两个值中的较大值/较小值。abs() 计算绝对值。exp() 计算自然指数 e^x。log()/ log10()/ log2() 计算对数。pow() 计算幂运算。sqrt() 计算平方根。sin()/ cos()/ tan() 三角函数。asin()/ acos()/ atan() 反三角函数。sinh()/ cosh()/ tanh() 双曲函数。asinh()/ acosh()/ atanh() 反双曲函数。ceil()/ floor() 向上/向下取整。round() 四舍五入取整。iota()(C++11) 用连续递增的值填充容器。vector<类型名> 变量名vector<int> v0(5); // 创建包含 5 个元素的 vector
vector<int> v1(5, 1); // 创建包含 5 个元素的 vector,每个元素为 1
vector<int> v2{1, 2, 3}; // 用花括号初始化列表
vector<int> v3(v1); // 用 v1 初始化 v3
vector<int> v4(move(v1)); // 移动 v1 到 v4
vector<vector<int>> v4(2, vector<int>(8, 3)); // 创建 2×8 的二维 vector
int arr[] = {1, 2, 3, 4, 5};
vector<int> v7(arr, arr + 5); // 从数组范围初始化
vector<int> v8(v2.begin(), v2.begin() + 2); // 结果:1 2
for (int i = 0; i < n; i++) {
int x;
cin >> x;
vi.push_back(x);
}
// 索引遍历
for (int i = 0; i < vi.size(); i++) {
cout << vi[i] << endl;
}
// 使用范围 for 循环
for (auto& x : vi) {
cout << x << endl;
}
// 迭代器
for (auto it = vi.begin(); it != vi.end(); it++) {
cout << *it << endl;
}
at():带边界检查的访问,如果索引越界会抛出异常operator[]:快速访问元素,不检查边界front():访问第一个元素back():访问最后一个元素begin():返回指向第一个元素的迭代器end():返回指向最后一个元素之后的迭代器empty():检查 vector 是否为空size():返回当前元素个数clear():清空所有元素reserve():预留空间,避免频繁重新分配内存insert():在指定位置插入元素erase():删除指定位置或范围的元素resize():改变 vector 的大小push_back():在末尾添加元素emplace_back():在末尾直接构造元素,避免拷贝pop_back():移除末尾元素vector 支持以下比较运算符:==, !=, <, <=, >, >=。比较按照字典序进行。
insert 和 erase 的复杂度为 O(n),非必要不使用push_back 时间复杂度可能会卡常,数据多不建议使用queue<类型名> 变量名front():访问队首元素back():访问队尾元素empty():检查队列是否为空size():返回队列中元素的个数push():在队尾插入元素emplace():在队尾直接构造元素pop():移除队首元素swap():交换两个队列的内容stack<类型名> 变量名top():访问栈顶元素empty():检查栈是否为空size():返回栈中元素的个数push():在栈顶插入元素emplace():在栈顶直接构造元素pop():移除栈顶元素swap():交换两个栈的内容deque<类型名> 变量名at():带边界检查的访问operator[]:下标访问front():访问第一个元素back():访问最后一个元素begin() / end()rbegin() / rend():反向迭代器empty() / size() / clear()insert() / erase() / resize()push_front() / emplace_front() / pop_front()push_back() / emplace_back() / pop_back()swap()deque 支持比较运算符,比较规则与 vector 类似(字典序)。
priority_queue<类型名> 变量名top():访问顶部(优先级最高)的元素empty() / size()push():插入元素emplace():直接构造元素pop():移除顶部元素swap():交换两个优先队列的内容set<类型名> 变量名empty() / size()insert() / emplace() / erase() / clear()find() / count() / lower_bound() / upper_bound() / equal_range()begin() / end() / rbegin() / rend()set 支持比较运算符,比较规则与 vector 类似(字典序)。
multiset<类型名> 变量名与 set 类似,但允许重复元素。
multiset 的成员函数与 set 基本相同,但有以下区别:
count() 可以返回大于 1 的值erase(key) 会删除所有等于 key 的元素equal_range() 在 multiset 中更有用unordered_set<类型名> 变量名与 set 类似,但输出顺序不确定。
unordered_set 的成员函数与 set 类似,但缺少排序相关函数,增加哈希相关函数。
unordered_set 只支持 == 和 !=,不支持 <、<=、>、>=。
map<键类型,值类型> 变量名empty() / size()insert() / emplace() / erase() / clear()operator[]:访问或插入元素at():带边界检查的访问find() / count() / lower_bound() / upper_bound() / equal_range()begin() / end() / rbegin() / rend()map 支持比较运算符,比较规则与 vector 类似(字典序,按键比较)。
multimap<键类型,值类型> 变量名与 map 类似,但允许重复键。
multimap 的成员函数与 map 基本相同,但有重要区别:
operator[] 和 at()insert() 总是成功count() 可以返回大于 1 的值equal_range() 在 multimap 中更有用operator[] 和 at()unordered_map<键类型,值类型> 变量名与 map 类似,但输出顺序不确定。
unordered_map 的成员函数与 map 类似,但缺少排序相关函数,增加哈希相关函数。
unordered_map 只支持 == 和 !=,不支持 <、<=、>、>=。
原题链接:B3614 【模板】栈 - 洛谷 题解:
#include <bits/stdc++.h>
using namespace std;
int main() {
int T;
cin >> T;
while (T--) {
stack<unsigned long long> stk;
int n;
cin >> n;
while (n--) {
char op[6];
unsigned long long x;
scanf("%s", op);
if (strcmp(op, "push") == 0) {
scanf("%llu", &x);
stk.push(x);
} else if (strcmp(op, "pop") == 0) {
if (stk.empty()) {
cout << "Empty" << endl;
} else {
stk.pop();
}
} else if (strcmp(op, "query") == 0) {
if (stk.empty()) {
cout << "Anguei!" << endl;
} else {
cout << stk.top() << endl;
}
} else {
cout << stk.size() << endl;
}
}
}
}
原题链接:B3616 【模板】队列 - 洛谷 题解:
#include <bits/stdc++.h>
using namespace std;
int main() {
queue<int> que;
int n;
cin >> n;
while (n--) {
int op, x;
cin >> op;
if (op == 1) {
cin >> x;
que.push(x);
} else if (op == 2) {
if (que.empty()) {
cout << "ERR_CANNOT_POP" << endl;
} else {
que.pop();
}
} else if (op == 3) {
if (que.empty()) {
cout << "ERR_CANNOT_QUERY" << endl;
} else {
cout << que.front() << endl;
}
} else {
cout << que.size() << endl;
}
}
}
#include <bits/stdc++.h>
using namespace std;
int main() {
using u64 = unsigned long long;
multiset<u64> coins;
int n;
cin >> n;
while (n--) {
u64 coin;
cin >> coin;
coins.insert(coin);
}
u64 p1 = 0, p2 = 0;
auto select = [&](u64 &sum) {
auto iter = coins.upper_bound(sum);
if (iter != coins.begin()) iter--;
sum += *iter;
coins.erase(iter);
};
while (!coins.empty()) {
select(p1);
if (coins.empty()) break;
select(p2);
}
cout << p1 << ' ' << p2 << endl;
}
原题链接:B3745 [语言月赛 202304] 你的牌太多了 - 洛谷 题解:
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m, r;
cin >> n >> m >> r;
vector<pair<int, int>> p1(n), p2(n);
for (auto &[x, _] : p1) cin >> x;
for (auto &[_, x] : p1) cin >> x;
for (auto &[x, _] : p2) cin >> x;
for (auto &[_, x] : p2) cin >> x;
multiset<pair<int, int>> ms(p2.begin(), p2.end());
while (n--) {
int id;
cin >> id;
auto &card = p1[id - 1];
auto iter = ms.upper_bound(card);
if (iter != ms.end() && iter->first == card.first) {
ms.erase(iter);
}
}
cout << ms.size() << endl;
}
原题链接:B3746 [语言月赛 202304] 洛谷评测机模拟器 - 洛谷 题解:
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> ans(n);
using pli = pair<long long, int>;
set<pli> s;
for (int i = 0; i < n; i ++) {
s.emplace(0, i);
}
for (int i = 1; i <= m; i ++) {
int time;
cin >> time;
auto [total, id] = *s.begin();
s.erase(s.begin());
ans[id].push_back(i);
s.emplace(total + time, id);
}
for (auto &line : ans) {
if (line.size() == 0) {
cout << "0" << endl;
continue;
}
for (auto &x: line) {
cout << x << ' ';
}
cout << endl;
}
}
原题链接:B3911 [语言月赛 202312] 铅球杯 - 洛谷 题解:
#include <bits/stdc++.h>
using namespace std;
int main() {
unordered_map<string, int> mp;
int n, k;
cin >> n >> k;
while (n--) {
string key;
int val;
cin >> key >> val;
mp.emplace(key, val);
}
string str;
getline(cin, str);
while (k --) {
getline(cin, str);
for (int i = 0; i < str.length(); i ++) {
if (str[i] == '{') {
int r = str.find('}', i + 1);
string key = str.substr(i + 1, r - i - 1);
int val = mp[key];
str.replace(i, r - i + 1, to_string(val));
}
}
cout << str << endl;
}
}
原题链接:P1102 A-B 数对 - 洛谷 题解:
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, c;
cin >> n >> c;
unordered_map<int, int> ump;
long long ans = 0;
while (n--) {
int x;
cin >> x;
ans += ump[x + c];
ans += ump[x - c];
ump[x]++;
}
cout << ans << endl;
}
原题链接:P1165 日志分析 - 洛谷 题解:
#include <bits/stdc++.h>
using namespace std;
int main() {
multiset<int> values;
stack<int> stk;
int n;
cin >> n;
while (n--) {
int op, val;
cin >> op;
if(op == 0) {
cin >> val;
stk.push(val);
values.insert(val);
} else if (op == 1){
if (stk.empty()) continue;
int top = stk.top();
stk.pop();
values.erase(top);
} else {
if (values.size() == 0) {
cout << 0 << endl;
continue;
}
cout << *values.rbegin() << endl;
}
}
}
原题链接:P1334 瑞瑞的木板 - 洛谷 题解:
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
using u64 = unsigned long long;
priority_queue<u64, vector<u64>, greater<u64>> q;
while (n--) {
int x;
cin >> x;
q.push(x);
}
u64 ans = 0;
while (q.size() > 1) {
u64 top1 = q.top();
q.pop();
u64 top2 = q.top();
q.pop();
ans += top1 + top2;
q.push(top1 + top2);
}
cout << ans << endl;
}
原题链接:P1571 眼红的 Medusa - 洛谷 题解:
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> vec(n);
unordered_set<int> s;
for (auto &x : vec) cin >> x;
while (m--) {
int x;
cin >> x;
s.insert(x);
}
for (auto &x : vec) {
if (s.count(x)) {
cout << x << ' ';
}
}
cout << endl;
}
原题链接:P1706 全排列问题 - 洛谷 题解:
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; i++) arr[i] = i + 1;
do {
for (int i = 0; i < n; i ++) {
cout.width(5);
cout << arr[i];
}
cout << endl;
} while (next_permutation(arr.begin(), arr.end()));
}
原题链接:P1923 【深基 9.例 4】求第 k 小的数 - 洛谷 题解:
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<int> arr(n);
for (auto &x : arr) scanf("%d", &x);
nth_element(arr.begin(), arr.begin() + k, arr.end());
cout << arr[k] << endl;
}
原题链接:P1996 约瑟夫问题 - 洛谷 题解:
#include <bits/stdc++.h>
using namespace std;
int main() {
queue<int> que;
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i ++) que.push(i);
int cnt = 1;
while (!que.empty()) {
int id = que.front();
que.pop();
if (cnt == m) {
cout << id << ' ';
cnt = 1;
} else {
cnt ++;
que.push(id);
}
}
}
原题链接:P2249 【深基 13.例 1】查找 - 洛谷 题解:
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> arr(n);
for (auto &x : arr) scanf("%d", &x);
while (m--) {
int x;
scanf("%d", &x);
auto iter = ranges::lower_bound(arr, x);
if (iter != arr.end() && *iter == x) {
cout << (iter - arr.begin() + 1) << ' ';
} else {
cout << -1 << ' ';
}
}
cout << endl;
}
原题链接:P3378 【模板】堆 - 洛谷 题解:
#include <bits/stdc++.h>
using namespace std;
int main() {
multiset<int> s;
int n;
cin >> n;
while (n--) {
int op, x;
cin >> op;
if (op == 1) {
cin >> x;
s.insert(x);
} else if (op == 2) {
cout << *s.begin() << endl;
} else {
s.erase(s.begin());
}
}
}
原题链接:P3613 【深基 15.例 2】寄包柜 - 洛谷 题解:
#include <bits/stdc++.h>
using namespace std;
int main() {
unordered_map<pair<int, int>, int, decltype([](const pair<int, int> &index) { return (size_t)index.first * 1e5 + index.second; })> mp;
int n, q;
cin >> n >> q;
while (q--) {
int op , i, j, k;
cin >> op;
if (op == 1) {
cin >> i >> j >> k;
mp[{i, j}] = k;
} else {
cin >> i >> j;
cout << mp[{i, j}] << endl;
}
}
}
原题链接:P3879 [TJOI2010] 阅读理解 - 洛谷 题解:
#include <bits/stdc++.h>
using namespace std;
int main() {
unordered_map<string, set<int>> mp;
int n;
cin >> n;
for (int i = 1; i <= n; i ++) {
int m;
cin >> m;
while (m--) {
string str;
cin >> str;
mp[str].insert(i);
}
}
int q;
cin >> q;
while (q--) {
string str;
cin >> str;
for (auto &x : mp[str]) {
cout << x << ' ';
}
cout << endl;
}
}
原题链接:P4305 [JLOI2011] 不重复数字 - 洛谷 题解
#include <bits/stdc++.h>
using namespace std;
int main() {
int T;
cin >> T;
while (T--) {
set<int> us;
int n;
cin >> n;
while (n--) {
int x;
scanf("%d", &x);
if (!us.count(x)) {
us.insert(x);
printf("%d ", x);
}
}
cout << endl;
}
}
原题链接:P4387 【深基 15.习 9】验证栈序列 - 洛谷 解题思路: 题解:
#include <bits/stdc++.h>
using namespace std;
int main() {
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<int> pushed(n), poped(n);
for (auto &x : pushed) cin >> x;
for (auto &x : poped) cin >> x;
stack<int> stk;
int index = 0;
for (auto &x : pushed) {
stk.push(x);
while (!stk.empty() && poped[index] == stk.top()) {
stk.pop();
index ++;
}
}
cout << (stk.empty() ? "Yes" : "No") << endl;
}
}
原题链接:P8755 [蓝桥杯 2021 省 AB2] 负载均衡 - 洛谷 题解:
#include <bits/stdc++.h>
using namespace std;
int main() {
using pli = pair<long long, int>;
using pq = priority_queue<pli, vector<pli>, greater<pli>>;
int n, m;
cin >> n >> m;
vector<pair<long long, pq>> computes(n);
for (auto &[v, _] : computes) cin >> v;
while (m--) {
int a, b, c, d;
cin >> a >> b >> c >> d;
auto &[v, q] = computes[b - 1];
while (!q.empty() && q.top().first <= a) {
v += q.top().second;
q.pop();
}
if (d > v) {
cout << -1 << endl;
continue;
}
v -= d;
q.emplace(a + c, d);
cout << v << endl;
}
}

微信公众号「极客日志」,在微信中扫描左侧二维码关注。展示文案:极客日志 zeeklog
使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML 转 Markdown 互为补充。 在线工具,Markdown 转 HTML在线工具,online
将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML 转 Markdown在线工具,online
通过删除不必要的空白来缩小和压缩JSON。 在线工具,JSON 压缩在线工具,online