KMP字符串匹配
2022-05-12
杂项
汉诺塔问题#include <bits/stdc++.h>
using namespace std;
void move(int n, char a, char b)
{
cout << "No." <
2022-04-11
树状数组维护区间和/最值
–2022.2.18更新树状数组维护区间最值
树状数组维护区间和/最值假设给定我们一个数组，让我们进行单点修改和区间查询操作，则需要O（1）和O（n）的时间复杂度，多次修改查询的总复杂度最坏为O（n^2），而用树状数组进行这些操作的时间复杂
2022-02-18
线性DP
线性DP数字三角形用f[i] [j]表示走到f[i] [j]的最大步数，一共只有两种走法，左上方走下来或右上方走下来，因此我们可以列出状态转移方程
f[i][j] = f[i - 1][j - 1] + a[i][j]; //左上方走下来
2022-02-11
欧拉函数
欧拉函数定义1~N中与N互质的数的个数称为欧拉函数，记为ϕ(N)。
若在算数基本定理中，N = p1^a1 * p2^a2 * ….. * pm^am。
ϕ(N) = N * (p1 - 1) / p1 * (p2 - 1) / p2 *
2022-02-11
最短路
图论最短路
Dijkstra算法朴素Dijkstra算法 O(n^2)Dijkstra算法用于求节1到点n的最短路，适用于稠密图（其时间复杂度与边数m无关）。
对每个点设定一个dist，代表其距离点1的距离，初始化为无穷大，后续再进
2022-02-11
最小生成树
最小生成树什么是最小生成树？设定一个n点m条边的无向图G=(V,E)，V表示图中点的集合，E表示图中边的集合，n=|V|，m=|E|。
由V中的n个顶点和E中的n-1条边构成的无向连通子图成为G的一棵生成树，其中边权之和最小的生成树成为最小
2022-02-11
堆
堆堆的结构：一颗完全二叉树（十分平衡，除最后一层（叶结点）以外，其他节点均非空，最后一层从左到右依次排布）。
小根堆也指最小堆。经过排序的完全二叉树，其中每一个非终端节点均小于其左右子节点，其根节点为所有元素的最小值。
大根堆同理。
存储方
2022-02-11
二分图（二部图）
二部图（二分图）什么是二分图对于一个无向图G=(V,E)，如果将顶点V分隔为两个互不相交的子集（A,B），且图中的每条边（i，j）所关联的两个顶点分别属于两个不同的顶点集（i in A，j in B），则称图G为一个二分图。
二分图有一个
2022-02-11
C++STL
常用C++STL向量（vector）容器变长数组，使用倍增的思想。
初始化vector <int> a; // 普通初始化
vector <int> a(10); // 定义长度
vector <int>
2022-02-11
约数
约数约数，又称因数。整数a除以整数b(b≠0) 除得的商正好是整数而没有余数，我们就说a能被b整除，或b能整除a。a称为b的倍数，b称为a的约数。
试除法求约数#include <bits/stdc++.h>
using nam
2022-02-05
哈希表
哈希表哈希表的作用将一个庞大的空间（值域）映射到比较小的空间（0-N），N一般为1e5-1e6左右。
这种映射通常使用模运算来进行，但将若干较大范围的数映射到较小范围的数，难免会发生冲突（两个数映射到同一个数上），为解决这种冲突，我们需要特
2022-02-04