首先声明！！！

  • 1、这为本人总结内容，主观性比较强，可以部分借鉴但不建议完全效仿；
  • 2、如有使用或转载请注明出处；
  • 3、如有不足，欢迎批评指正；

时间复杂度 *

空间复杂度

* 补充1：ASCII码表大全

ASCII表

* 补充2：C++ 运算符优先级总表

来自 C++ 运算符优先级 - Oi-Wiki ，有修改。

运算符 描述 例子 可重载性
第一级别
:: 作用域解析符 Class::age = 2; 不可重载
第二级别
++ 后自增运算符 for (int i = 0; i < 10; i++) cout << i; 可重载
– 后自减运算符 for (int i = 10; i > 0; i–) cout << i; 可重载
type() type{} 强制类型转换 unsigned int a = unsigned(3.14); 可重载
() 函数调用 isdigit(‘1’) 可重载
[] 数组数据获取 array[4] = 2; 可重载
. 对象型成员调用 obj.age = 34; 不可重载
-> 指针型成员调用 ptr->age = 34; 可重载
第三级别 （从右向左结合）
++ 前自增运算符 for (i = 0; i < 10; ++i) cout << i; 可重载
– 前自减运算符 for (i = 10; i > 0; --i) cout << i; 可重载
+ 正号 int i = +1; 可重载
- 负号 int i = -1; 可重载
! 逻辑取反 if (!done) … 可重载
~ 按位取反 flags = ~flags; 可重载
(type) C 风格强制类型转换 int i = (int) floatNum; 可重载
* 指针取值 int data = *intPtr; 可重载
& 值取指针 int *intPtr = &data; 可重载
sizeof 返回类型内存 int size = sizeof floatNum; 不可重载
第四级别
.* 类对象成员引用 obj.*var = 24; 不可重载
->* 类指针成员引用 ptr->*var = 24; 可重载
第五级别
* 乘法 int i = 2 * 4; 可重载
/ 除法 float f = 10.0 / 3.0; 可重载
% 取余数（模运算） int rem = 4 % 3; 可重载
第六级别
+ 加法 int i = 2 + 3; 可重载
- 减法 int i = 5 - 1; 可重载
第七级别
<< 位左移 int flags = 33 << 1; 可重载
>> 位右移 int flags = 33 >> 1; 可重载
第八级别
< 小于 if (i < 42) … 可重载
<= 小于等于 if (i <= 42) … 可重载
> 大于 if (i > 42) … 可重载
>= 大于等于 if (i >= 42) … 可重载
第九级别
== 等于 if (i == 42) … 可重载
!= 不等于 if (i != 42) … 可重载
第十级别
& 位与运算 flags = flags & 42; 可重载
^ 位异或运算 flags = flags ^ 42; 可重载
| 位或运算 flags = flags | 42; 可重载
第十一级别
&& 逻辑与运算 if (conditionA && conditionB) … 可重载
|| 逻辑或运算 if (conditionA || conditionB) … 可重载
第十二级别 （从右向左结合）
? : 条件运算符 int i = a > b ? a : b; 不可重载
= 赋值 int a = b; 可重载
+= 加赋值运算 a += 3; 可重载
-= 减赋值运算 b -= 4; 可重载
*= 乘赋值运算 a *= 5; 可重载
/= 除赋值运算 a /= 2; 可重载
%= 模赋值运算 a %= 3; 可重载
<<= 位左移赋值运算 flags <<= 2; 可重载
>>= 位右移赋值运算 flags >>= 2; 可重载
&= 位与赋值运算 flags &= new_flags; 可重载
^= 位异或赋值运算 flags ^= new_flags; 可重载
|= 位或赋值运算 flags |= new_flags; 可重载
第十三级别
, 逗号分隔符 for (i = 0, j = 0; i < 10; i++, j++) … 可重载

小技巧

一、初始板子：

  • 这是我的初始模板，里面的点已经写在注释上了，有需要的可以参考喔！
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 x first    // pair类型为了方便二维平面上表示(x,y)坐标
#define y second

#define int long long  // 经典！我是那种比较粗心的会经常忘记开longlong，
                  // 所以直接把所有int变为longlong，但是这样有时可能会常数过大从而导致TLE或MLE
using namespace std;

typedef pair<int,int> PII;  // pair在树和图上经常用到，也经常在二维平面上表示(x,y)坐标

typedef long long ll;   // 可以ll代替longlong类型，少写一些字母

const int N=1e6+10;  // 数组开到1e6可以应付绝大部分题目的数据量
                     // 从而保证不会RE和忘记修改数据，但是要注意空间复杂度
int a[N],b[N];
int T,n,m,k;         // 可以事先列出常用的几个固定变量和数组


void solve()
{
    // 此处解题
}


signed main()   // 如果用了define int long long这里要改成signed
{
    ios::sync_with_stdio(false);
    // 关闭同步流固定写法，优化cin和cout的时间，在数据1e6以上就非常需要
    cin.tie(nullptr),cout.tie(nullptr);
	
    cin>>T;
    // 现在遇到很多题目都是T组数据，写成函数的形式方便把每一组数据区分开
    while(T--) solve();    // 如果没有T组数据就只写solve()
	
    return 0;
}

二、常用STL容器：

1、vector（变长数组）

首先 vector 是一个非常好用的东西，他俗名也叫【变长数组】，那就是说，它是一种空间可以灵活变通的类似于数组的一种数据结构。下面就来介绍几种 vector 的常见用法：

  • 定义：
1
2
3
4
5
6
7
8
// 一维
vector<int> c;   // vector<类型名> 变量名;
vector<int> c(n+1);  // 固定长度

// 二维
vector<int> c[N];  // vector<类型名> 数组;
vector<vector<int>> c;  // vector<vector<类型名>> 变量名;
vector<vector<int>> c(n+1,vector<int>(m+1));  // 二维n*m固定长度
  • 基本用法：
1
2
3
4
5
6
7
8
9
vector<int> c;    // 以容器变量为c举例
c.size()          // c容器的长度
c.push_back(x);   // 从vector后面存进去元素x
c.pop_back(x);    // 从vector后面弹出元素x
c.back();         // 取出容器最后的元素
for(int i=0;i<c.size();i++)  // 遍历c中所有元素
for(auto t:c)     // 遍历vector内所有元素赋值到t里
for(auto [x,y]:c) // 二维遍历
// 注意：c++11以上才支持auto
  • 因为 vector 可以访问最后的元素 + push进最后的位置 + 弹出最后面的元素，有时候可以利用这一特性用 vector 模拟栈；

2、string（字符串）

string 就是字符串，string s 也相当于char s[N]，但是里面有很多关于字符串操作的函数，所以比字符数组好用很多。下面就来介绍几种 string 的常见用法：

  • 定义：
1
2
3
4
5
// 一维
string s;  // string 变量名;

// 二维
string s[N];  // string 数组;
  • 基本用法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
string s;  // 以变量名为s举例
cin>>s;    // 输入，遇到空格结束
getline(cin,s); // 输入一整行

s.size()   // 求字符串长度
s=' '+s;   // 下标整体往后移
string s=s1+s2;  // 字符串相加

reverse(s.begin(),s.end());  // 翻转字符串
s.substr(i,len);   // substr是取出子串，用法s.substr(开头下标,子串长度)
s.erase(i,len);    // erase是删除子串，用法s.erase(开头下标,子串长度)
s.insert(i,"???");  // insert是插入子串，用法s.insert(开头下标,子串)
s1.find(s2)!=srting::npos;  // 在字符串s1里找字符串s2
for(int i=0;i<s.size();i++)  // 遍历字符串

3、map（映射）

map 是一个很好用的东西，它是基于红黑树实现的，可以作为哈希表使用，增删查改的复杂度都是 O(logn)。下面就来介绍几种 map 的常见用法：

  • 定义
1
2
3
map<int,int> mp;  // map<原类型，映射类型> 变量名;
map<string,char> mp; // 例：mp["nb"]='6';
map<pair<int,int>,string> mp; // 例：mp[{1,1}]="1025_xp";
  • 用法
1
2
3
4
5
map<int,int> mp;  // 以mp为变量名举例
for(auto t:mp) cout<<t.x<<' '<<t.y<<'\n';  // 遍历map，x和y分别代表两维
mp[i]++;  mp[i]=x;  mp[a[i]]--;  // 直接赋值和加减记录
map<string,vector<string>> mp;   // 进阶用法，map嵌套vector
mp["666"].push_back("nb");

4、set（集合）

set 是一种集合的容器，用于存储唯一的元素集合，并且也会根据键（key）自动排序。它基于二叉搜索树的数据结构实现，并且内部使用红黑树来维护顺序和唯一性。以下是 set 容器的一些常见用法示例：

  • 定义
1
2
3
set<int> st;    // 普通集合
set<string> st;
multiset<int> stt;  // 多重集合
  • 用法
1
2
3
4
5
st.insert(10)   // 插入一个元素
st.erase(10)   // 删除一个元素
auto it=st.find(10)  // 查找一个元素
stt.count(10)  // 统计元素的个数（仅限于multset）
st.size()     // 集合大小

5、stack（栈）

stack是一个比较简单易用的数据结构，其最大的特性就是先进后出。就好比一个桶，先放进出的数据就在底部，如果想要取出就先要把上面的数据取出。以下是 stack 容器的一些常见用法示例：

  • 定义
1
2
3
stack<int> stk;
stack<string> stk;
stack<Node> stk;   // Node是结构体
  • 用法
1
2
3
4
5
stk.empty()   //堆栈为空则返回真 
stk.pop()     //移除栈顶元素 
stk.push()    //在栈顶增加元素 
stk.size()    //返回栈中元素数目 
stk.top()     //返回栈顶元素

6、queue（队列）、priority_queue（优先队列）

队列（queue）是一种线性数据结构，其特点是数据的插入和删除操作分别在不同的两端进行：插入操作在队列的尾部，删除操作在队列的头部。因此，队列遵循先进先出（FIFO, First In First Out）的原则，即最早进入队列的元素最先被处理。
而 优先队列（priority_queue） 是队列的一直优化，它是基于堆实现的，使得取出队列里最大最值元素优化到 $O(logn)$ 级别的复杂度。
以下是 queue、priority_queue 容器的一些常见用法示例：

  • 定义
1
2
3
4
5
6
queue<int> q;
queue<string> q;
queue<Node> q;    // Node是结构体

priority_queue<int> q; // 优先队列（大根堆）
priority_queue<int,vector<int>,greater<int>> q; // 优先队列（小根堆）
  • 用法1（queue）
1
2
3
4
5
6
q.push(6);     //入队
q.pop();       //出队
q.back();      //取队尾
q.front();     //取队头
q.empty();     //判空，返回bool值
q.size();      //查询队列元素个数
  • 用法2（priority_queue）
1
2
3
4
5
q.empty()    // 如果优先队列为空，则返回真 
q.pop()      // 删除第一个元素 
q.push(6)    // 加入一个元素 
q.size()     // 返回优先队列中拥有的元素的个数 
q.top()      // 返回优先队列中有最高优先级的元素

三、重载权值排序用法

1、sort 重载排序函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 从大到小排序
bool cmp(int a,int b){
    return a>b;
}

// 从小到大排序
bool cmp(int a,int b){
    return a<b;
}

// 先按第一权值x从小到大排序，然后按第二权值y从大到小排序（按自己需求修改符号和逻辑）
bool cmp(pair<int,int> a,pair<int,int> b){
    if(a.x==b.x) return a.y>b.y;
    return a.x<b.x;
}

sort(a+1,a+n+1,cmp);

2、priority_queue 重载排序函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 普通自定义
struct cmp{
    bool operator()(int x,int y){
        return x>y; // 小的优先级高
    }
};
priority_queue<int,vector<int>,cmp> q;

// 友元函数重载
struct Node{
    int x,y;
    friend operator<(Node a,Node b){
        if(a.x!=b.x) return a.x>b.x; //x小的优先级高
        return a.y<b.y; //y大的优先级高
    }
};
priority_queue<Node> q;

四、增广数组

增广数组主要还是用于解决二维坐标的方位移动问题，以下是一些常见的坐标初始化：

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>

using namespace std;

const int N=1e6+10;

int dx[4]={0,0,1,-1};  // 上下左右四个方位
int dy[4]={1,-1,0,0};
int dxx[8]={0,0,1,1,1,-1,-1,-1};  // 比上下左右多出了四个斜方位
int dyy[8]={1,-1,0,1,-1,0,1,-1};

int main()
{
    int x,y;
    cin>>x>>y;
	
    // 调用四个方位
    for(int i=0;i<4;i++){
        int a=x+dx[i];
        int b=y+dy[i];
        cout<<a<<' '<<b<<'\n';
    }
	
    // 调用八个方位
    for(int i=0;i<8;i++){
        int a=x+dx[i];
        int b=y+dy[i];
        cout<<a<<' '<<b<<'\n';
    }
	
    return 0;
}

Ps：如果大家想了解更多也可以上网搜其他的用法，有很多东西可能很高级但不一一介绍了，思维才是解题里面最重要的，会这些就已经足以应对 90% 以上的问题了。