CSP 考试资料

黎 浩然/ 12 10 月, 2023/ 算法/ALGORITHMS/ 0 comments

CLion 用户：2018112061@email.szu.edu.cn

CLion 密码：——————————————-

CLion 密码：——————————————-

1. Vector（向量）

#include <vector>

std::vector<int> v;
v.push_back(1);  // 在末尾添加元素
v.pop_back();    // 删除末尾元素
v.size();        // 获取元素个数
v.empty();       // 检查是否为空
v[0];            // 访问第一个元素

2. List（双向链表）

#include <list>

std::list<int> lst;
lst.push_back(1);   // 在末尾添加元素
lst.push_front(2);  // 在开头添加元素
lst.pop_back();     // 删除末尾元素
lst.pop_front();    // 删除开头元素
lst.size();         // 获取元素个数
lst.empty();        // 检查是否为空

3. Queue（队列）

#include <queue>

std::queue<int> q;
q.push(1);  // 入队
q.pop();    // 出队
q.front();  // 查看队首元素
q.empty();  // 检查是否为空
q.size();   // 获取元素个数

4. Stack（栈）

#include <stack>

std::stack<int> s;
s.push(1);  // 入栈
s.pop();    // 出栈
s.top();    // 查看栈顶元素
s.empty();  // 检查是否为空
s.size();   // 获取元素个数

5. Set（集合）

#include <set>

std::set<int> s;
s.insert(1);  // 添加元素
s.erase(1);   // 删除元素
s.find(1);    // 查找元素
s.empty();    // 检查是否为空
s.size();     // 获取元素个数

6. Map（映射）

#include <map>

std::map<int, int> m;
m[1] = 2;      // 添加键值对
m.erase(1);    // 删除键值对
m.find(1);     // 查找键值对
m.empty();     // 检查是否为空
m.size();      // 获取元素个数

7. Priority Queue（优先队列）

#include <queue>

std::priority_queue<int> pq;
pq.push(1);  // 添加元素
pq.pop();    // 删除最大元素（默认）
pq.top();    // 查看最大元素（默认）
pq.empty();  // 检查是否为空
pq.size();   // 获取元素个数

8. Unordered Set（无序集合）

#include <unordered_set>

std::unordered_set<int> us;
us.insert(1);  // 添加元素
us.erase(1);   // 删除元素
us.find(1);    // 查找元素
us.empty();    // 检查是否为空
us.size();     // 获取元素个数

9. Unordered Map（无序映射）

#include <unordered_map>

std::unordered_map<int, int> um;
um[1] = 2;      // 添加键值对
um.erase(1);    // 删除键值对
um.find(1);     // 查找键值对
um.empty();     // 检查是否为空
um.size();      // 获取元素个数

排序

1. sort: 对一个区间的元素进行排序。 #include <algorithm> #include <vector> std::vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6, 5}; std::sort(vec.begin(), vec.end());
2. partial_sort: 对一个区间的前N个元素进行排序。 std::partial_sort(vec.begin(), vec.begin() + 3, vec.end());
3. nth_element: 对一个区间进行部分排序，使得某个位置的元素在排序后应该在的位置上。 std::nth_element(vec.begin(), vec.begin() + 5, vec.end());

搜索

1. binary_search: 在已排序的区间中搜索元素。 bool found = std::binary_search(vec.begin(), vec.end(), 5);
2. find: 在未排序的区间中搜索元素。 auto it = std::find(vec.begin(), vec.end(), 5);
3. lower_bound / upper_bound: 在已排序的区间中找到第一个不小于（或大于）给定值的元素。 auto lb = std::lower_bound(vec.begin(), vec.end(), 5); auto ub = std::upper_bound(vec.begin(), vec.end(), 5);

集合操作

1. set_union: 计算两个已排序集合的并集。 #include <set> #include <algorithm> #include <iterator> std::set<int> a = {1, 2, 3, 4}; std::set<int> b = {3, 4, 5, 6}; std::set<int> result; std::set_union(a.begin(), a.end(), b.begin(), b.end(), std::inserter(result, result.end()))
2. set_intersection: 计算两个已排序集合的交集。 std::set<int> intersect; std::set_intersection(a.begin(), a.end(), b.begin(), b.end(), std::inserter(intersect, intersect.end()));
3. set_difference: 计算两个已排序集合的差集。 std::set<int> difference; std::set_difference(a.begin(), a.end(), b.begin(), b.end(), std::inserter(difference, difference.end()));
4. set_symmetric_difference: 计算两个已排序集合的对称差集。 std::set<int> symm_diff; std::set_symmetric_difference(a.begin(), a.end(), b.begin(), b.end(), std::inse

转换

1. transform: 对区间内的每一个元素应用一个给定的函数，并将结果存储在另一个区间。 #include <algorithm> #include <vector> std::vector<int> vec = {1, 2, 3, 4}; std::vector<int> out(vec.size()); std::transform(vec.begin(), vec.end(), out.begin(), [](int x) { return x * x; });

合并

1. merge: 合并两个已排序的序列。 #include <algorithm> #include <vector> std::vector<int> a = {1, 3, 5}; std::vector<int> b = {2, 4, 6}; std::vector<int> result(a.size() + b.size()); std::merge(a.begin(), a.end(), b.begin(), b.end(), result.begin())
2. inplace_merge: 在一个区间内，合并两个相邻的已排序序列。 std::vector<int> vec = {1, 3, 5, 2, 4, 6}; std::inplace_merge(vec.begin(), vec.begin() + 3, vec.end());

分割

1. partition: 根据一个谓词函数，把一个区间分成两部分。 #include <algorithm> #include <vector> std::vector<int> vec = {1, 2, 3, 4, 5, 6}; auto it = std::partition(vec.begin(), vec.end(), [](int x) { return x % 2 == 0; });
2. stable_partition: 类似于**partition**，但保持相等元素的相对顺序。 auto it = std::stable_partition(vec.begin(), vec.end(), [](int x) { return x % 2 == 0; });
3. nth_element: 使序列中的某个元素位于它最终排序后应该在的位置上，并保证它左边的所有元素都小于等于它，它右边的所有元素都大于等于它。 std::nth_element(vec.begin(), vec.begin() + 3, vec.end());

三角函数

• sin: 正弦函数 #include <cmath>double angle = M_PI / 4; // 45 degrees double result = std::sin(angle);
• cos: 余弦函数 double result = std::cos(angle);
• tan: 正切函数 double result = std::tan(angle);
• asin: 反正弦函数 double result = std::asin(0.5);
• acos: 反余弦函数 double result = std::acos(0.5);
• atan: 反正切函数 double result = std::atan(1.0);
• atan2: 反正切函数（两个参数） double result = std::atan2(1.0, 1.0);

平方、开方

• sqrt: 开平方函数 double result = std::sqrt(16.0);
• cbrt: 开立方函数 double result = std::cbrt(27.0);
• pow: 指数函数 double result = std::pow(2.0, 3.0);

对数函数

• log: 自然对数 double result = std::log(2.71828);
• log10: 以10为底的对数 double result = std::log10(100.0);
• exp: 指数函数 double result = std::exp(1.0);

其他数学函数

• ceil: 向上取整 double result = std::ceil(2.3);
• floor: 向下取整 double result = std::floor(2.7);
• round: 四舍五入 double result = std::round(2.5);
• abs: 绝对值 double result = std::abs(-2.5);
• fmod: 取余 double result = std::fmod(5.3, 2.0);

十进制与其他数制转换

1. std::stoi / std::stol / std::stoll: 字符串到整数 #include <string>int num = std::stoi("42");
2. std::to_string: 整数到字符串 std::string str = std::to_string(42);
3. std::hex: 十六进制流操作 #include <iostream>int num = 42; std::cout << std::hex << num; // 输出：2a