快速幂算法
快速幂时一种给幂运算加速的算法。比如说我们在算 $2^{10}$ 时，如果一步一步去算需要 $9$ 步，而如果我们先算 $2^2 = 2 \times 2$，再算 $2^5 = 2^2 \times 2^2 \times 2$，…
TAG
算法
使用这个标签归档的内容。11 篇内容
↗
ST 表
ST 表ST 表运用了倍增的思想。其中 $dp_{i, j} = \max(i \to i + 2^j - 1)$，也就是 $dp_{i, j}$ 的值是区间 $[i, i + 2^j - 1]$ 中的最大值。通过上面的定义，显…
欧拉图相关知识点学习笔记
[label color = "orange"]图论[/label]欧拉回路欧拉回路的定义是：对于一个图，如果从一个点出发，遍历所有的边后回到出发的那一个点，那么这个图就含有欧拉回路。欧拉回路其实和小学时学习的一笔画问题有关系。…
搜索 & 图的储存和最短路算法
搜索DFS这种方法可以概括为：不撞南墙不回头，回过头来继续撞。DFS，深度优先搜索，顾名思义就是每次递归到最深，然后回溯。我们一般用递归函数实现 DFS。例题：用 DFS 求最短路：#include <bits/stdc+…
LCA 学习笔记
LCA 是最近公共祖先的简称。朴素算法如果两个点的深度相同：就往上跳，直到两个节点相同。否则先让两个点的深度相同。倍增和朴素算法类似，只是把挨个往上跳变成每次跳 $2^i$。代码：#include <bits/stdc++…