#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm> //有sort才用
#include <vector>
#include <cstring> //有memset(f, -1, sizeof f)，memcpy(g, f, sizeof f)才用
cmath库
sqrt()
字符串只能用cin读吗？
include <sstream>
stringstream ssin(s);
while (ssin >> str)
将s形成一个输入流
vector<vector<int>> res = vector<vector<int>>(n);
C++ stl
vector, 变长数组，倍增的思想
size() 返回元素个数
empty() 返回是否为空
clear() 清空
front()/back()
push_back()/pop_back()
begin()/end()
[]
支持比较运算，按字典序
sort(res.begin(), res.end());//排序
string，字符串
size()/length() 返回字符串长度
empty()
clear()
substr(起始下标，(子串长度)) 返回子串
c_str() 返回字符串所在字符数组的起始地址
queue, 队列
size()
empty()
push() 向队尾插入一个元素
front() 返回队头元素
back() 返回队尾元素
pop() 弹出队头元素
priority_queue, 优先队列，默认是大根堆
size()
empty()
push() 插入一个元素
top() 返回堆顶元素
pop() 弹出堆顶元素
定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;
stack, 栈
size()
empty()
push() 向栈顶插入一个元素
top() 返回栈顶元素
pop() 弹出栈顶元素
deque, 双端队列
size()
empty()
clear()
front()/back()
push_back()/pop_back()
push_front()/pop_front()
begin()/end()
[]
set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列
size()
empty()
clear()
begin()/end()
++, -- 返回前驱和后继，时间复杂度 O(logn)
set/multiset
insert() 插入一个数
find() 查找一个数
count() 返回某一个数的个数
erase()
(1) 输入是一个数x，删除所有x O(k + logn)
(2) 输入一个迭代器，删除这个迭代器
lower_bound()/upper_bound()
lower_bound(x) 返回大于等于x的最小的数的迭代器
upper_bound(x) 返回大于x的最小的数的迭代器
map/multimap
insert() 插入的数是一个pair
erase() 输入的参数是pair或者迭代器
find()
[] 注意multimap不支持此操作。 时间复杂度是 O(logn)
lower_bound()/upper_bound()
unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
和上面类似，增删改查的时间复杂度是 O(1)
不支持 lower_bound()/upper_bound()， 迭代器的++，--
循环操作
for (auto p : primes) cout << p.first << " " << p.second << endl;
bitset, 圧位
bitset<10000> s;
~, &, |, ^
>>, <<
==, !=
[]
count() 返回有多少个1
any() 判断是否至少有一个1
none() 判断是否全为0
set() 把所有位置成1
set(k, v) 将第k位变成v
reset() 把所有位变成0
flip() 等价于~
flip(k) 把第k位取反
结构体排序
struct Edge
{
int a, b, w;
bool operator < (const Edge &o) const
{
return w < o.w;//不能写成w - o.w
}
}edge[M];
传数组写法
void spfa(int u, int dist[])
这数组的初始化只能是memset(d, INF, N * 4);
一行一行读入
#include <sstream>
string line;
getline(cin, line);
while (m -- )
{
getline(cin, line);
stringstream ssin(line);
int cnt = 0, p;
while (ssin >> p) stop[cnt ++ ] = p;
for (int j = 0; j < cnt; j ++ )
for (int k = j + 1; k < cnt; k ++ )
g[stop[j]][stop[k]] = true;
}
常用语法归纳
vector
在LeetCode中创建长度是n，m的数组
vector<vector<bool>> st(n, vector<bool>(m));
如果用bool st[n][m]创建时，里面的st[i][j]是固定的非false值
vector<int> ans;
ans.push_bcak(1);//从尾端插入
ans.pop_back();//从尾端pop出
reverse(ans.begin(), ans.end());
ans.resize(n + 1, 0);//设置ans的长度，并且所有位置初始化为0，也可以将后面的参数去掉，默认是0
stack
stack<int > stk;
stk.push(1);
stk.top();
stk.pop();
priority_queue
priority_queue, 优先队列，默认是大根堆
size()
empty()
push() 插入一个元素
top() 返回堆顶元素
pop() 弹出堆顶元素
定义成小根堆的方式：
priority_queue<int, vector<int>, greater<int>> q;
typedef pair<int, int> PII; 排序时是按照first从小到大排序的
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, 1});
queue, 队列
size()
empty()
push() 向队尾插入一个元素
front() 返回队头元素
back() 返回队尾元素
pop() 弹出队头元素
哈希
unordered_map<int, int> has;
for(auto x : nums) has[x] ++;
for(auto[k, v] : has) cout << k << " " << v << endl; //枚举所有元素
#include <unordered_map>
unordered_map<int, int> has;
has.count(val - b[i])// 判断是否有该元素
int main()
{
//字符串转数字
string a1 = "12";
int b1 = atoi(a1.c_str());
cout << b1 + 1 << endl;
//数字转字符串
int a2 = 34;
string b2 = to_string(a2);
cout << b2 << endl;
//字符转字符串
char c = '(';
string s(1, c);
cout << s << endl;
//字符串转字符
char c2 = s[0];
cout << c2 << endl;
return 0;
}
pair
#define x first
#define y second;
typedef pair<int, int> PII;
q.push({0, 0});
int a = t.first + dx[i], b = t.second + dy[i];
int a = t.x + dx[i] , b = t.y + dy[i];
