01 常用math函数
如果函数要使用，加==#include <math.h>==
返回均为double
1.fabs(double x)
该函数用于对double型变量取绝对值
2.floor(double x)和ceil(double x)
分别用于double型变量的向下取整（<）和向上取整（>）
3.pow(double r, double p)
返回rp
4.sqrt(double x)
返回算数平方根
5.log(double x)
返回ln(x)
6.sin(double x)、cos(double x)、tan(double x)
7.asin(double x)、acos(double x)、atan(double x)
返回反正弦等值
8.round(double x)
将x四舍五入
9.gcd(Type a, Type b)
Type gcd(Type a, Type b){
// 返回最大公约数
return b ? gcd(b, a % b) : a;
}
-
Eratosthenes筛法或称埃氏筛法
#include <bits/stdc++.h>
using namespace std;
const int N = 1000002;
bool st[N];
int main(){
vector<int> primerV;
for(int i = 2; i < N; i++){
if(!st[i]){
primerV.push_back(i);
for(int j = i * 2; j < N; j += i)
st[j] = true;
}
}
for(int i = 0; i < primerV.size(); i++)
cout << primerV[i] << '\n';
return 0;
}
02 C++STL介绍
vector、queue（bfs）、deque（双端队列）略
#include <queue>中全为push
Set
- 集合，内部自动有序且不含重复元素的容器
- 底层实现为RB-Tree
insert() O(logN)
find() O(logN)，若未查找到给定的value，则返回迭代器end()
erase() 1.erase(iterator)，可结合find使用：my_set.erase(my_set.find(100));
2.`erase(value)` O(logN)
3.`erase(first_iterator, last_iterator)`，删除[first_iterator, last_iterator)区间的所有元素 O(last_iterator - first_iterator)
主要作用是自动去重并按升序排序，如果需要处理排序且不唯一的情况，则需要使用multiset，C++11提供unordered_set只去重不排序（快），底层实现为散列（哈希表）
String
substr(pos, len) 返回从pos号位开始、长度为len的子串，时间复杂度为O(len)
string::npos 用作find函数失配时的返回值，等于-1或4294967295
find(str) 当str是字符串子串时，返回其在字符串中第一次出现的位置，否则返回string::npos
C++11
std::stoi(str)将字符串转换为十进制
std::stoi(str, 起始位置, n进制)将 n 进制的字符串转化为十进制
std::to_string(num)将int等类型的数转化为字符串
Map
- 将任何基本类型（包括STL容器）映射到任何基本类型（包括STL容器）
- 底层实现为RB-Tree
-
map<key, value> my_map- 如果是字符串到整型的映射，必须使用string而不能使用char数组
- key唯一，赋值将覆盖
- 访问方式
- 通过下标访问：
my_map['a'] = 1 - 通过迭代器访问：iterator->first访问key，iterator->second访问value
- 通过下标访问：
- map键会以从小到大自动排序
函数与set类似
常见用途
- 需要建立字符（或字符串）与整数之间映射的题目，使用map减少代码量
- 判断大整数或者其他类型的数据是否存在
- 字符串和字符串的映射也有可能会遇到
一个键对应多个值使用multimap，只映射不按key排序，C++11提供unordered_map（快），底层实现为散列（哈希表）
Priority_queue
- 底层实现为heap
- 元素优先级设置
- 基本数据类型的优先级设置
-
priority_queue<int> pq; // 从大到小优先级最大的元素在队首 -
priority_queue<int, vector<int>, greater<int>> // 从小到大优先级最小的元素在队首
-
- 结构体的优先级设置
- 通过对 < 进行重载，如果想从小到大，则把 < 中return改为 >
- 基本数据类型的优先级设置
解决贪心问题，也可以对Dijkstra算法进行优化
Pair
pair将两个元素绑在一起作为一个合成元素，利用my_pair.first和my_pair.second进行访问
pair比较可以直接使用==等，比较规则为先以first比较，first相同再判别second大小
常见用途
- 用来代替二元结构体及其构造函数，可以节省编码时间
- 作为map的键值对来进行插入
algorithm常用函数
abs(int i) 返回整数的绝对值
reverse(iter_begin, iter_end) 将[iter_begin, iter_end)之间的元素进行反转（使用指针或迭代器）
fill(first, last, val) 把数组或容器中的[first, last)区间赋为某个相同的值
sort() 对容器vector、string、deque可以使用，其他不能使用
lower_bound(first, last, val) 寻找数组或容器的[first, last)范围内第一个值大于等于val的元素位置，数组返回指针，容器返回迭代器
up_bound(first, last, val) 寻找数组或容器的[first, last)范围内第一个值大于val的元素位置，数组返回指针，容器返回迭代器
lower_bound(first, last, val)、up_bound(first, last, val)未找到元素时，返回可以插入该元素的位置的指针或迭代器
unique 应先sort()后unique()，否则出现错误（不常用）
03 常见单词
commas 逗号
polynomial 多项式
exponent 指数
decimal 十进制
scatter 分散；散点（图等）
pedigree 家谱
seniority 资历；排行
spell 拼写
denote 表示，意味着
product 乘积（cross product、dot product）
coefficient 系数
radix 基数
trophy 杯；奖杯（如世界杯）
odd 奇怪的，奇数的；奇数
transaction 交易
prime 质数
toll 收费；税
chronological 按时间顺序的
palindromic 回文的
acyclic 无环的
symmetric 对称的
grids 网格
even 偶数的
clique 团（maximal clique 最大连通分量）
capital 大写的
case sensitive 区分大小写的
adjacent 相邻的
threshold 起点
forward 转发
factorization 因式分解
quota 定量
interval 区间
terminated 终止的；终结
subset 子集
quadratic probing 平方探测法（separate chaining hash table 拉链法、linear probing 线性探查法、second hash或double hash 双重hash）
Topological Order 拓扑排序
descendant 后代，后裔
difference 差
quotient 商
rational numbers 有理数
numerator 分子
denominator 分母
04 并查集
#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int p[N];
int find(int x) // 返回x的祖宗节点 + 路径压缩
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) p[i] = i;
while (m -- )
{
char op[2];
int a, b;
scanf("%s%d%d", op, &a, &b);
if (op[0] == 'M') p[find(a)] = find(b);
else
{
if (find(a) == find(b)) puts("Yes");
else puts("No");
}
}
return 0;
}
作者：yxc
链接：https://www.acwing.com/activity/content/code/content/280326/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
05 Dijkstra求最短路 I O(|V|^2)
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。
请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 ?1。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。
如果路径不存在，则输出 ?1。
数据范围
1≤n≤500,
1≤m≤105,
图中涉及边长均不超过10000。
输入样例：
3 3
1 2 2
2 3 1
1 3 4
输出样例：
3
#include <bits/stdc++.h>
using namespace std;
const int N = 505;
const int INF = 0x3f3f3f3f;
int n, m;
int g[N][N];
int dist[N];
bool st[N];
int dijkstra(){
dist[1] = 0;
for(int i = 0; i < n; i++){
int k = -1;
for(int j = 1; j <= n; j++)
if(!st[j] && (k == -1 || dist[k] > dist[j]))
k = j;
st[k] = true;
for(int j = 1; j <= n; j++)
dist[j] = min(dist[j], dist[k] + g[k][j]);
}
if(dist[n] < INF) return dist[n];
else return -1;
}
int main(){
memset(g, INF, sizeof(g));
memset(dist, INF, sizeof(dist));
memset(st, false, sizeof(st));
cin >> n >> m;
for(int i = 0; i < m; i++){
int x, y, w;
cin >> x >> y >> w;
if(x == y) continue; // 自环
g[x][y] = min(g[x][y], w);
}
int ret = dijkstra();
cout << ret << endl;
return 0;
}
06 Dijkstra求最短路 II O(|E|log|V|)
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。
请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 ?1。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。
如果路径不存在，则输出 ?1。
数据范围
1≤n,m≤1.5×10^5,
图中涉及边长均不小于 0，且不超过 10000。
数据保证：如果最短路存在，则最短路的长度不超过 10^9。
输入样例：
3 3
1 2 2
2 3 1
1 3 4
输出样例：
3
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 150010;
const int INF = 0x3f3f3f3f;
struct Record{
int ne;
int val;
};
vector<Record> v[N];
int n, m;
int dist[N];
bool st[N];
priority_queue<PII, vector<PII>, greater<PII> > heap;
int dijkstra(){
dist[1] = 0;
heap.push({0, 1});
while(heap.size()){
auto t = heap.top();
heap.pop();
int vertex = t.second, distance = t.first;
if(st[vertex]) continue;
st[vertex] = true;
for(int j = 0; j < v[vertex].size(); j++){
int t_ne = v[vertex][j].ne;
int t_val = v[vertex][j].val;
dist[t_ne] = min(dist[t_ne], distance + t_val);
heap.push({dist[t_ne], t_ne});
}
}
if(dist[n] < 0x3f3f3f3f) return dist[n];
else return -1;
}
int main(){
memset(dist, INF, sizeof(dist));
memset(st, false, sizeof(st));
cin >> n >> m;
for(int i = 0; i < m; i++){
int x, y, w;
cin >> x >> y >> w;
if(x == y) continue;
v[x].push_back({y, w});
}
int ret = dijkstra();
cout << ret << endl;
return 0;
}
07 字符串处理
1.to_string
返回string类型字符串
2.stoi、stoll、stod、stof、stol
返回int、long long、double等类型，最常用的是stoll和stod这两个函数， stoll可以兼容stoi，stol； 而stod可以兼容stof
3.tolower(char c)、toupper(char c)
返回char类型的小写或大写形式
4.transform()
transform(str.begin(), str.end(), str.begin(), ::tolower);：==注意tolower或toupper需要加::==
其中[a~z] 、 [A~Z]会随着::tolower或::toupper改变而其他内容不变
08 排序
1.堆排序简单实现
// 从分支节点也就是n / 2位置down即可建堆
void down(int x){
int tmp = x;
if(x * 2 <= _size && h[x * 2] < h[tmp]) tmp = x * 2;
if(x * 2 + 1 <= _size && h[x * 2 + 1] < h[tmp]) tmp = x * 2 + 1;
if(x != tmp){
swap(h[x], h[tmp]);
down(tmp);
}
}
