类型范围

int -2147483648~2147483647

long -2147483648～2147483647

long long -9223372036854775808~9223372036854775807 (别用cin，用scanf(“%lld”)) (2^64)

有时候long long 过不了可以用long double

常用定义

正无穷

​ 正无穷的初始化

​ 使用头文件：

注意：使用memset初始化只能初始化0,-1,0x3f; 若要初始化其他值，使用

or in stl

数据输入输出

• 数据规模大的使用 scanf 读取 printf 输出

• 输出固定n位数（不足补0）

• 关于字符串的处理（带空格）

  连续读取带所需数字的字符串如，可以使用

  而可以把数字或者其他写入字符数组中

• 小数位保留

转义

​ 的转义是

位运算

• 除以2的位运算:,例如：写成,写成；同理，乘以2就是（注意：只能对整数操作）

• 不等于-1，例如的快速写法

• 对2取模，简写成x&1 例如：改写成

一些常用的位运算

1. 求n的二进制中第k位（k=0是个位）:
2. lowbit：返回x的最后一位1，应用：求n的二进制中1的个数

浮点数的比较方法

由于计算机中浮点数的存储问题，不能直接,需要判断他们相减的值是不是小于某个很小的数，加很多括号是为了防止宏定义出错

圆周率 Pi

数组复制

结构体

结构体可以这样写，例如：

注意事项

• 的最后一个元素的迭代指针是
• 如果要重复用记得一下…

向量 vector

• vector找最值和对应位置，使用中的,返回最值的迭代器

• 建立一个逆序vector

• 遍历vector

• 找一个元素

• 去重

  需要和``v.erase()`配合才是真正的去重

• 初始化二维vector固定大小

• push_back()和emplace_back()

  emplace_back() 和 push_back() 的区别，就在于底层实现的机制不同。

  push_back() 向容器尾部添加元素时，首先会创建这个元素，然后再将这个元素拷贝或者移动到容器中（如果是拷贝的话，事后会自行销毁先前创建的这个元素）；而 emplace_back() 在实现时，则是直接在容器尾部创建这个元素，省去了拷贝或移动元素的过程。

映射 map

• 查找这个map中有没有这个key：

unordered_map是没自动排序的map，此时通过max_element()找到的最大值，他的key不一定是最小的，若是map则两个相同的值中，找到的key是最小的。

• 找到Map中最大的value对应的key

使用 配合函数中使用pair组成键值对

• 对map的排序

对map排序实际上还是要转换在vector中进行，重载比较函数

集合 set

添加

删除

这里参数可以是值也可以是位置指针

注意，在multiset中erase一个数的话会把set里的数全删除，删一个数使用

优先队列 priority_queue

定义

使用优先队列实现堆

• 小根堆： PII是pair经过typedef
• 大根堆：

字符串 string

• 删除特定字符

  使用和

• 大小写转换

  遍历字符串，对每个字符使用头文件中的,

• 字符串转数字、数字转字符串

  数字 --> 字符串 ：

  字符串 --> 数字：

• 找到对应子串位置

• 在特定位置插入字串

  s.insert(pos,size,char);

  例如在字符串开头插入n个0

• ,从字符串中读入数据和把数据写入字符串中

• 和的转换关系:

  • string -> const char*使用

  • char*和char[]可以直接转string，如：

• 带空格的字符串按空格分割，使用

关于

判断该字符是不是字符数字或者字母，是返非0，否则为0，还有,等

队列queue、栈stack

他们不支持操作

• queue::emplace()

  将元素插入队列末尾

• queue::push()

  插入队尾

• queue::pop()

  队头出队

关于permutation

• 判断v2是不是v1的序列，是1否0

• 和用法

注意要稳定排序有个

1. 默认函数和

sort的排序默认从小到大递增排列，也可以增加第三个参数传入一个比较函数，C++提供两个默认的比较函数

从大到小，递减排列

从小到大，递增排列（默认）

注意：在创建，等STL类型时，通常可以传入比较函数改变其默认排序

快排模板

2. 使用运算符重载

运算符重载可以放到结构体中

3. 使用lamda表达式

4. 手写cmp()函数

排序算法操作

K路归并

标准：利用堆找每一路最大/小

其次：使用遍历找

开个vector数组，然后把数组中的vector都排好序，利用遍历找最小

关于排序题的排名输出（相同分数要求排名一样）

• 推理题都是用枚举来做
• 链表题都丢到数组里做

一般分两大类，一类是两个指针分别指向两个序列，一类是两个指针指向一个序列

一般都是先把暴力算法写出来，然后看有没有单调性，有就用双指针优化

核心思想

单调性，将双重循环优for(i:n){for(j:n){}}化到O(n)

基本模板

用于要使用值做下标的情况下，值域非常大，但是个数不多的时候，把序列映射到从0开始的连续自然数

1. 若序列中有重复元素则需要去重
2. 需要能快速算出序列中的值离散化后的值（二分）【起始也可以排序后用一个unordered_map记录位置】

左闭右闭,找是否存在满足条件的元素，没找到返回-1

找第一个满足条件的元素位置【该条件一定是从左到右先不满足，然后满足】

找第一个不满足性质的元素位置【从左到右满足，然后不满足】

深搜关键在于顺序

关于n皇后的技巧性（数组设置）

存储

初始化

插入

一些链表题做法

先存下链表，然后遍历下链表存在数组中，在数组中进行操作后再把数组变链表

基本操作

• 统计每个集合中人数

• 统计集合个数（连通块个数）
  可以扫描一遍p数组，如果p[i]==i，则集合数量++；

• 维护根结点为点权最大的

存储

数组模拟邻接表一定要记得h初始化为-1，并且要记得e[M],ne[M]设置成边数的个数，不然容易段错误

遍历

DFS

BFS

一层一层遍历的BFS

判断连通

应用 – 最短路

Dijkstra（只能处理边权为正数的问题）

Dijkstra+DFS

SPFA（可以处理负边权）

SPFA判断负环

一开始把所有点加入队列，判断最短路上的点数是否>=n,是则出现负环

Floyd（多源最短路）

拓扑排序

判断是否为拓扑排序

由于拓扑排序在前面的点的下标一定小于后面的点，遍历每条边，看起点下标是否小于终点下标

超级源点和超级汇点

有时候有多个出发点，比如多个入度为0的，这时候需要一个虚拟起点连接所有真正的起点

DAG最长路（关键路径）

有三种方法做：

1. 将边权取相反数，通过SPFA做（先通过拓扑排序判断一下有无环）
2. 使用e[N],l[N],ve[N],vl[V],w[N]的关键路径求解做法
3. 使用DP，DP[i][j]表示i到j的最长路

通过两个遍历建树

中序+前/后序

中序+层序

思路：先求出先序，然后通过先序和中序建树

层序遍历

完全二叉树

存储

使用一维数组存取层序遍历，一个点x左儿子2x，右节点2x+1，父节点x/2下取整

给定值，建立完全二叉搜索树

排序得到中序遍历，然后按中序遍历下树，边遍历边填数

判断是否为完全二叉树

二叉排序树 BST

插入

删除

平衡二叉树 AVL

记忆化搜索（树形dp）

最低公共祖先 (LCA)

爬山法

思路：在下面的节点一直移动到和另一个同一层开始，一起向上爬，直到相等 时间复杂度：
需要优化常数：把int范围内的数映射到0~N-1 如把最小的数映射到0，第二小的数映射到1…(离散化) 这种没说数据范围的就需要离散化，或者你的n开无敌大。。int范围内

Huffman – 参照贪心

概念

大根堆：父节点的值大于等于子节点

小根堆：父节点的值小于等于子节点

判断是不是堆（是什么堆）

建立

基本操作

插入

删除

实际题目中的应用

几种实现方式：

1. 手写堆

2. 优先队列 — 其实如果有些题只是要用到堆这个数据结构用来排序优化找最值可以用set替代（例如dijkstra的堆优化）【优先队列和set一个原理】（但是不支持修改任意元素，会产生冗余）

3. 优先队列不支持修改内部元素和遍历，还是用set吧。。。

4. 使用stl的make_heap()，可以用vector模拟heap方便访问内部元素

完整的模拟堆

上面用一个小根堆维护，下面用大根堆，下面元素个数比上面多一个或一样多；则中位数一定在下面的堆顶
小根堆堆顶作为分界线
如果两堆个数相差>=1，把多的堆顶弹出加入另一堆顶
（可以使用两个set模拟）

插入

把x和下面堆的堆顶比较，大于插入上面的堆，x<=下面的堆顶，插入下面。
**调整：**如果上面元素多，把上面的最小值pop插入到下面的堆；如果下面多则把下面的最大值插入到上面

删除

和下面堆的最大值比较，小于就在下面删除，否则在上面删除

应用

• 求中位数

具体实现

前缀和用于快速求数组中一段区间内的和 【下标一定要从1开始】
如我们要求Dl+Dl+1+…Dr**(原数组中一段区间内的和)**
则S0=0，S1=D1，S2=D1+D2，Si表示前i个数组元素的和，然后用Sr-(Sl-1)

二维前缀和

对于环的处理，把它展开 如转成
那么，1到3就可以走也可以走

差分就是前缀和的逆，类似微分和积分
O(n)时间内从差分数组B求一次前缀和到原数组A，用途，高效让A内一段区间内的值+C

1. 选择不相交区间（做法和区间选点一样）

描述
n个开区间(ai,bi)，选择尽量多个区间，之间没有公共点（例如在时间不冲突情况下选尽量多课）
做法

1. 按照右端点从小到大排序，从第一个区间开始选
2. 把所有和上一个区间相交的区间排除在外

2. 区间选点(和上面的一毛一样)

描述
n个闭区间[ai,bi]，选择尽量少的点，使每个区间内都至少一个点
做法

1. 按区间右端点从小到大排（右端点相同时按左端点从大到小）
2. 从前往后依次枚举每个区间，若当前区间已经包含点，跳过；否则，选当前区间右端点

3. 区间分组

描述：给定 N 个闭区间 [ai,bi]，将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小。
做法：

1. 将所有区间按左端点从小到大排序
2. 从前往后处理每个区间，判断能否将其放到某个现有的组（即：该区间左端点是否大于组内右端点最大值，大于即有交集，不能放）
   1. 如果不存在这样的组，开新组
   2. 存在，放进去并更新 Max_r

4. 区间覆盖

描述：N个闭区间[ai,bi]以及一个线段区间[s,t]，请你选择尽量少的区间，将指定线段区间完全覆盖。（一个目标区间，n个备选区间，从备选的中选最少的覆盖目标区间）
做法：

1. 将所有区间按左端点从小到大排序
2. 从前往后枚举每个区间，在所有能覆盖开始位置start的区间中，选右端点最大的区间。然后将start更新成右端点的最大值

排序后看最大的i个数是不是满足都大于i，即排序后看倒数第i个数是否大于i

转换成图论
i在p[i](有序序列)的位置上，就让i到p[i]连一条边
此时连成的图的每个点出度入度都是1，它必然是一堆环
如果要交换排序，目标就是把n个环变成n个自环
而操作： 交换两个数 <=> {
​ 一个环变成两个环（环内交换）：{
- 和0【可以操作的点】的下一个点交换，下一个点会变自环 - 和非next点交换会变两个环，到时候还是要合并回来（redundancy）
​ }
​ 两个环变一个环（环外交换）
}

可以使用优先队列模拟小根堆

总时间 = t1×n-1+t2×(n-2)+t3×(n-3)… [计算总时间的公式]

描述：给n个人打水时间，安排打水顺序使得等待时间最小

做法：

按时间排序，然后总时间按公式算（注意可能爆出int，最好用long long）

描述：在一条数轴上有N个点表示商家an，an中选一个点x到其他商家距离之和最小
即：max{|a1-x|+|a2-x|+|a3-x|+…}
做法:
对所有an排序，n是奇数，x选中位数；n是偶数，中间两个数都可以,总和就是每个点到中位数的点的距离之和

比如耍杂技的牛，排序后算就可以了

具有最优子结构，核心是找到状态转移方程和边界条件

若更新状态只依赖于与之前的状态，可以使用滚动数组，降低空间复杂度

还是看看算法笔记吧。。。

1. 全部转换为统一单位
2. 使用string
3. scanf(%d:%d:%d)，转换成总秒数之类的…
4. 输出持续时间可以通过总秒数转换而来，例如

在gcd的基础上，把ab/d，防止溢出就是a/d*b

求x、y，使得ax+by=gcd(a,b)

1. down必须为非负数，分数为负则另up为负
2. 分数为0则令up为0，down为1
3. 分子和分母需要时刻保持最简

判断质数（试除法）

约数定理：一个数的所有约数（因数）是成对出现：如果d是n的约数，则n/d也是n的约数，故只要枚举d<=n/d的约数 --> d<=根号n（试除法）

素数筛

线性筛

分解质因子

从小到大枚举所有约数，如果可以被除，就除干净

计算n!的质因子个数

求所有约数(试除法)

求欧拉函数

/phi(N) = 1~N中与N互质的数的个数

线性筛欧拉函数

计算Cmn(m在下面) [需要根据数据范围选方法]

关于逆元

计算Cmn%p

卡特兰数