【笔记/模板】Dijkstra算法
原理解释
Dijkstra算法是通过贪心+BFS+动态规划实现的，可以用来计算单个点（源点）到其余任一点的距离大小。
Dijkstra算法的实现分为以下几步：
定义并初始化数组dis[N]，其中 disidis_{i}disi 表示源点当前距离 iii 点的最短距离，再定义一个 boolboolbool 数组 vis[N]， visivis_{i}visi 代表第 iii 个点是否被拓展过（即是否达到了最优解）。
从未被拓展的点中找出一个离源点最近的点 xxx（此时它已经是最优解），通过这个点依次松弛和它联通的每一个点距离源点的距离，同时将所松弛的点加入到队列当中。
等到队列中没有元素存在之后，结束函数，此时 dis[N] 中的每个点 disidis_{i}disi 即代表着距离源点的最小距离。
代码实现
朴素法
123struct Edge { int x, w; }; // x表示出点，w表示权值.vector<Edge> g[N]; //存图数组int dist[N]; //d[i]表示st距离i点的距离大小
12345678 ...
【笔记/模板】排序算法
【模板】快速排序 - 洛谷
1. 冒泡排序
排序原理：
每次将未确定部分的相邻两个值对比，设为ai,ai+1a_{i},a_{i+1}ai,ai+1，如果ai>ai+1a_{i}>a_{i+1}ai>ai+1,则对这两个值进行交换，可以使用swap来快速对两个值进行交换。
那么，这样一轮交换下去，第一个数就可以确定是最小的了。以此类推，直到所有值都被确定，就得出最终排好序的数列了。
时间复杂度：O(n2)O(n^2)
O(n2)
核心模板代码如下：
123456int n,a[100001];void pop_sort(){ for (int i = 1; i <= n; i ++) for (int j = 1; j < n;j ++) if (a[j] > a[j+1]) swap(a[j], a[j + 1]);//change a[j] and a[j+1].}
2. 桶排序
排序原理：
桶排序的原理很简单，就是定义一个数组为桶，然后每个桶代表一个数字，每输入一个数就将这个 ...
【笔记/模板】单调栈 单调队列
单调栈
定义
单调栈即满足单调性的栈结构。通过只在一端进出，从而维护一个数在前 / 后的第一个大于或小于它的数。
操作 / 方式
首先按照特定的顺序遍历。
如果要求出最小值，就要将栈顶大于入列元素的所有数全部弹出。
此时候的栈顶就是直到当前下标的答案。
加入这个元素并且继续更新。
代码
结构体 + STL模板
12345678910111213141516171819int a[N], ans[N];struct Node { int val, idx; };stack <Node> stk; signed main(){ // ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n; cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = n; i >= 1; i--) { while (!stk.empty() & ...
【模板】Floyd算法以及扩展应用
Floyd 算法
原理
Floyd 算法用来求出任意两个节点之间的最短路。
优点：代码少，思维简单，适用于除了负环以外的任何图。
缺点：时间复杂度为 O(n3)O(n ^ 3)O(n3)，空间复杂度为 O(n2)O(n ^ 2)O(n2)。
而 Floyd 的核心原理是用动态规划实现的，定义一个二维数组 fi,jf_{i, j}fi,j，遍历图上的所有点 kkk，可以得到如下公式：
f[i][j]=min(f[i][j],f[i][k]+f[k][j])f[i][j] = min(f[i][j], f[i][k] + f[k][j])
f[i][j]=min(f[i][j],f[i][k]+f[k][j])
代码实现
1234for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
扩展应用
传递闭包
定义
给定一个不包含自环 ...
【笔记】动态规划
前言
动态规划（Dynamic Programming）是c++算法学习当中十分重要而变化灵活的一部分分支，这种算法是通过递推的方式从而达到求出最优解的目的。
动态规划基本原理
能用动态规划解决的问题，需要满足三个条件：最优子结构，无后效性和子问题重叠。
最优子结构：每个子问题的解是其本身的最优解。
无后效性：已经求解的子问题，不会再受到后续决策的影响。
动态规划中可能存在大量的子问题造成的答案重叠。
动态规划基本思路
将原问题划分为若干阶段，每个阶段对应若干个子问题，提取这些子问题的状态与特征。
寻找每一个状态的可能 决策，或者说是各状态间的相互转移方式和关系。
按顺序求解每一个阶段的问题。
背包DP
0-1背包问题
[USACO07DEC]Charm Bracelet S - 洛谷
题目大意：
已知有 nnn 个物品，第 iii 个物品的重量 wiw_{i}wi，价值viv_{i}vi，背包的总容量 WWW。求背包可以容下的最大价值。
解题思路
该类型是典型的背包问题，可以设置一个二维数组 dpi,jdp_{i,j}dpi,j，表示在只能放下 ...
【笔记/模板】Bellman-Ford 与 SPFA
Bellman-Ford求最短路和负环
时间复杂度：O(nm)O(nm)O(nm)
【模板/笔记】Johnson算法
12345678910111213141516171819202122bool Bellman_Ford(){ memset(dist, 0x3f, sizeof dist); for (int k = 1; k < n; k ++) for (int ver = 1; ver <= n; ver ++) for (int i = h[ver]; ~i; i = ne[i]) { int to = e[i]; if (dist[to] > dist[ver] + w[i]) dist[to] = dist[ver] + w[i]; } for (int ver = 1; ver <= n; ver ++) fo ...
【模板】素数筛
模板原题
1. 寻找因数筛法
时间复杂度：O(nn)O(n\sqrt n)O(nn)
核心模板代码如下：
1234567bool isprime(int n){ if (n < 2) return false; //0和1都不是 for(int i = 2; i * i <= n; ++ i) if(n % i == 0) return false; //有1和它本身以外的其他因子就不是素数了 return true;}
2. 埃氏筛法
时间复杂度：O(nloglogn)O(n\log \log n)O(nloglogn)
核心模板代码如下：
1234567891011121314void Eratosthenes(int n){ vis[0] = vis[1] = true; for (int i = 2; i <= n; i++) { if (!vis[i]) for (int j = 2 * i; j <= n; j += ...