Trie

高效的存储和查找字符串集合的数据结构

并查集

1、将两个集合合并
2、询问两个元素是否在一个集合当中,3，时间复杂度为o(m)，m为边数

O2优化

用了ios::sync_with_stdio(false),和cin.tie(0)就不能用scanf和printf了

最大异或对

最大异或对：一个数乘以2，相当于把这个数的二进制向左移1位，也就是在后面加一个0
除以2也是同理
for循环中的 i > = 0可以改成
~ i ；这两者等价

系统分配空间

系统为某个程序分配空间时所需的时间与空间大小无关，与申请次数有关
capacity()表示数组的实际容量
size（）表示已经使用的数据容量

getline()

substr（）函数在string头文件里，作用是截取一段字符串
getline函数这样用 ；
getline（cin,str）;

scanf和cin

超过1百万就用scanf，1百万以下和cin差不多

count()和find()

全局变量 char g[N][N]的好处就是每个元素默认为’\0’，所以可以用puts输出每一行！！但要保证N比要输入的大
map和set函数底层是红黑树
unorded map中的count和find的区别：
count函数直接放回的是一个数值，如果存在，那么返回1，反之0；
find返回的是一个iterator， 直接输出iterator是会报错的，要输出的话得取出迭代器的值再输出。
string和容器中的用法有些不同，容器中的比如 ar1是个vector容器
find(ar1.begin(), ar1.end(), “bbb”)
map底层是红黑树实现的，因此它的find函数时间复杂度：O(logn)
而unordered_map底层是哈希表,因此它的find函数时间复杂度：O(l)
！！！！！！！注意map与unordered_map的区别！！！！
而algorithm里的find函数是顺序查找，复杂度为O(n)
count 和find有些相似，在algorithm里面返回的是个数，而在容器里返回的是0或1
稠密图用邻接矩阵来存，
稀疏图用邻接表来存
重边的意思是两条边有多条路

Dijkstra()

从一堆数中找一个最小的数，可以用堆排序
优先队列使用的是top()函数，而不是队列中的front（）函数
DIjkstra朴素版时间复杂度为
o(n^2);n是点的个数；堆优化版的时间复杂度为o(mlogn)，m是边。
Dijkstra算法思路：dist先设为无穷大，dist[1]=0;在遍历的过程中找到还未走到的点中的权值最小的，再对其取最小路径
朴素版的用的是稠密图，存储方式为邻接矩阵
堆优化版的用的是稀疏图，存储方式为邻接表

spfa

spfa算法可以来解决dijkstra算法的题目
重边&有向图
若存在负环，一定会更新无穷次

bellman

bell-man ford算法如果有负权回路，最短路不一定不存在，如果负权不在它通往n号点的路中，那么他不影响
如果是SPFA算法，一定不存在负权回路
99.9%的最短路没有负权环路
用bellman_ford算法用任何方式存边都可以，用的是结构体
时间负杂度为o(n*m)

floyd

floyd算法不能用于在负权环中
调代码大概分两类，一类是cout输出变量。第二个是出现RE或者内存超限就用删代码法
kruskal算法比优化版的prime算法思路清楚，代码实现少，存在竞争关系，都用于稀疏图
朴素版的prime用于稠密图
prime朴素版：先把所有距离初始化正无穷，先进行n次遍历，然后在非集合当中选个离集合最近点加入到集合当中来
集合：当前已在连通快中的点
邻接矩阵无向图g[a][b]=g[b][a]。

dijkstra和prime

dijkstra算法和prime算法代码的区别：
dijkstra求的是点到起点最小权值，prime求的是点到集合的最小值
floyd算法因为会问及到自身到自身的距离，所以g[a][a]=0，
用邻接矩阵写的题，题目中有重边这个要求的话，那么都需要g[a][b]=min(g[a][b],c)

if(prime()==0x3f3f3f3f)
else cout<<prime();这中间其实调用了两次prime，第一次调用之后应在初始化，不然会错

当题目中出现走不到终点，但是又更新了，这个时候要用

INF/2这个条件，如bellamn_ford算法那个k条路径的约束，又如Floyd算法；
如果只更新走到终点的点，那么只能用==INF，如dijkstra朴素版算法，又如优化版的spfa算法
kruskal（克鲁斯卡尔）算法
o(mlogm)
思路：1.先将所有边的权重从小到大排序，2.枚举所有边和权重，如果a，b边不连通，就把b加入到a的集合

二分图

const ：常变量
bool类型的数组也可以memset，
判断一个图是否为二分图：
1、至少欧两个顶点
2、如果产生回路，那么一个回路中的边数一定为偶数。
3、没有回路的图也叫二分图。
二分图当且仅当图中没有奇数边的环

匈牙利算法

二分图中的染色法时间复杂度为O(m+n)
匈牙利算法时间复杂度为O(mn),但实际运行时间远小于o(mn);
在关押罪犯那道题里面，用的是邻接表，但应该要用临接矩阵，所以二分图染色法就默认用邻接表来存储
如果出现数组越界，那么错误可以有很多种，如TLE，RE；

数学知识

sqrt函数比较慢
分解质因数当中，n中最多包含一个大于sqrt（n）的质因子
时间复杂度最坏为o(sqrt(n)),最好是logn
筛质数中优化的时间复杂度为
o(nloglogn)相当于o(n),也称为“埃式筛法”，还有个“线性筛选法”
如果数据在1e6内两者时间差不多，如果数据为1e7，线性筛选法快一倍
公约数就是公因数
unorded_map比map更快
unorded_map 中也有first和second
欧几里得算法得时间复杂度为logn
sort函数的时间复杂度为nlogn
queue和stack中用push()，vector和deque（双端队列）用的是push_back();
约数&合数
！！！取模的题一般都要边乘边模
数组开不了2e9那么大，可以开1e9；
素数分解定理：
对于一个大于1的数n，存在唯一的一组素数，他们的乘积为n
算数基本定理：
任何一个大于 11 的自然数 NN ，如果 NN 不为质数，那么 NN 可以唯一分解成有限个质数的乘积 N=Pa11Pa22Pa33……PannN=P1a1P2a2P3a3……Pnan，这里 P1<P2<P3……<PnP1<P2<P3……<Pn 均为质数，其中指数 aiai 是正整数。

欧拉函数

-x=~x+1；
求x的第k位数字：x>>k&1;
若要求2，3的欧拉函数则只需要res（2）=2*（1-1/2）=1;
3同理，1的欧拉函数值为1
快速幂的时间复杂度为logk（k是次方）

c++中取模

a*x=b(mod m)的含义是：
a乘以x模上m等于b
-2/5=3;数学上取模没有负数
在c++中 -2/5 = -2.

o2和puts()

ios::sync_with_stdio(false);
cin.tie(0);
这句话和puts冲突，你要关了同步的话，scanf，printf，puts这些你都不能用

高斯算法

高斯消元时间复杂度为o(n^3)
初等行列变换：
①将某一行乘以一个非零常数
②将某两行交换
③将某一行乘以一个非零常数加到另一行
逆元的作用将除法变乘法
数论倒数，又称逆元
a/b≡a*x(mod m) (b|a)
b 存在乘法逆元的充要条件是 b 与模数 m 互质。
逆元法的时间复杂度为
o(nlogn)
涉及到a/b%p；就考虑用逆元
b太大会爆精度

寄存器变量register

register是做声明的，为了提高效率。
C语言允许将局部变量的值放在CPU中的寄存器中，这种变量叫寄存器变量
我们常用定义变量存放在内存中！而register是指寄存器变量。寄存器是cpu的存储部件，即是高速缓存，通常不大，最多几mb。定义这个变量适用于频繁使用某个变量，以加快运行速度，因为保存在寄存器中，省去了从内存中调用，要注意定义了这个变量后，不能取地址！！就是不能使用&符号，这与一般不同。
出现这个“Float Point Exception ”，有可能再除法中分母为零
printf(“%04d”，)表示要以四位数字存储

背包问题

01背包问题：每件物品只有一个
完全背包问题：每件物品有无限个
多重背包问题：每件物品为有限个
分组背包问题：给出很多组背包，每组选一个
滚动数组：有一个g[2][N],一直用g[0][N]和g[1][N]来算
++i比i++效率要高~

区间dp

scanf输入字符串到int类型的，可以通过字节来判断，字符是占一个字节，而一个int占四个字节，但如果用cin读入的话会直接报错
最长公共子序列~LCP
“因为要保证后面使用到的状态在前面被计算过，所以只能先枚举长度（这也是区间dp基本的技巧，所有的区间dp问题，第一维都是枚举区间长度）”

运算符优先级

运算符的优先级：
指针最优，单目运算优于双目运算。如正负号。
先算术运算，后移位运算，最后位运算。请特别注意：1
逻辑运算最后结合。

小根堆

小根堆的定义：
priority_queue<int,vector,greater>haep;

int和long的范围

32位系统下，int和long的范围是一样的，都是4字节
64位系统下，long和long long的范围是一样的，都是8字节
优先队列为什么叫优化？？
log2(10^x) 近似等于3x;
如log2(10^18) = 54;
sizeof()的返回值单位是字节
1MB/s=8Mbps;
100兆宽带指的是网速最高可达12.2MB/s
流量是兆字节
带宽是兆比特

vector初始化

vector<vector> state(M) 等价于
vectorstate[M]
Tab键可以使代码整体右移，
shift + Tab键可以使代码整体左移
isditgit()函数可以判断输入的字符是否为数字，头文件就可以用了

0x80,0x3f

用memset()函数赋值时，0x80（-2139062144） 与
0x7f（2139062143） 绝对值差1
0x3f（1061109567） 与
0xc0（-1061109568） 绝对值差1

计组

计算机应该有输入设备、存储器（有指令和数据，指令传输到控制器，数据传输到运算器）、控制器、运算器、输出设备五个基本部分组成
二进制表示指令和数据，指令由操作码和地址码组成，操作码指出操作类型，地址码指出操作数的地址
冯·诺依谩体系最核心的思想是“存储程序”工作方式
pc程序寄数器每次加1
机器指令用二进制表示，汇编指令用符号表示
机器语言和汇编语言统称为机器级语言

程序执行过程

寄存器相当于一个缓冲区把
（register）ALU、MDR、IR、PC、MAR
计算机硬件包括cpu、存储器、I/O控制器、外部设备、总线
高级语言源程序–汇编语言源程序–机器语言目标程序–控制信号
编译程序：用来将高级语言源程序翻译成汇编语言或机器语言目标程序
预处理、编译、汇编、链接

malloc()和calloc()和realloc()

结构指针，可以提高参数传递的效率
指针数组每个元素都是个字符串
extern可以定义为外部变量，即全局变量的使用位置先于该全局变量的定义
也可以对函数进行外部申明，两个模块中的函数互不影响
static可以使编写的自用函数影响其他程序员的程序
malloc(),calloc(),realloc()函数在stdlib.h头文件里，malloc()和calloc()都用来申请内存空间，但calloc()会有初值null
realloc()更改以前的存储分配
还有搭配free()这个函数

excel公式

成绩排序函数：
=RANK( G2, G$2 : G$11);

-128的原码

指数（阶）的移码表示阶码，
用移码表示指数
补码0000 0000的原码是1000 0000符号位同时也可以看做数字位即表示-128，这也解释了为什么127（0111 1111）+1（0000 0001）=-128（1000 0000）。

移码和补码：
移码等于数值组成的二进制数+2的二进制数个数的次方
补码等于 2 的数值位和符号位一共的位数+数值组成的二进制数
补码和移码仅仅是符号位不同
指数的移码称为阶码

排序复杂度

c++中sort的时间复杂度为
o(nlogn),归并排序也为
o(nlong),快速排序平均为
o(nlongn),最坏为o(n^2)

计算机系统分类

●硬件系统
主机部分分为-CPU(中央处理器)，内存(4G,8G,16G 32G 64G)。
外设部分
输入设备包括键盘鼠标
输出设备包括显示器音响
外存储器包括硬盘
●软件系统
系统软件包括操作系统，操作系统:控制硬件运行,支持其他软件运行
分类:
Windows(7 8 10)
Mac
Linux
Android
ios
应用软件:自己安装的使用的软件

INT_MAX

<limits.h>中有INT_MAX和INT_MIN的宏定义可直接使用。

sort()的第三个参数

c++中sort默认从大到小排序第三个参数为greater()

c++map遍历

for (auto& [k, v] : head) {
cout << k << “ “ << v << endl;
}

scanf输入空格

scanf(“%[^\n]”,str);//直到输入回车键，读取才结束，当然不能超过a定义的大小，否则会出错。
此命令与gets(str)效果一样。
关于输入空格：
https://www.cnblogs.com/h694879357/p/11767447.html

求负数的补码

-8的补码可以这样计算
先计算8的原码，再计算出8的补码，然后所有位取反加1

算法题目空间大小

64MB说明可以开6.4*10^7个字节

朴素筛法

朴素筛选的时间复杂度为
o(n lnn)，其实就是
o(nlogn)，埃式筛选的时间复杂度可以看成o(logn)，其实是
o(nlnn/lnn)(朴素筛法的优化),然后其实也是o(nloglogn)。
线性筛选在大于1百万的情况下，会比埃式筛法快一倍作用。

1字

32位的计算机中：32位(bit)=4字节(byte)=1字(word)
64位的计算机中：64位(bit)=8字节(byte)=1字(word)

红黑树和AVL

queue没有clear这个函数，要想清空，可以重新定义
q = queue();
map向数组一样取下标的时间复杂度是logn的
关联容器的大部分操作的时间复杂度是logn的，无序容器的大部分操作的时间复杂度是1的，因为关联容器的实现原理是红黑树，而无序容器的实现原理是哈希表

红黑树和ALV的区别：
红黑树放弃追求完全平衡，只求大致平衡，在它与平衡二叉树的时间复杂度相差不大的情况下，保证每次插入最多只需要三次旋转就能达到平衡，所以实现起来也更为简单。logn

平衡二叉树会追求绝对平衡，实现条件艰难，并且它每次插入新节点之后需要旋转的次数不能预知。