Alex's Blog

This page is locked.

引入

想要了解矩阵快速幂，就不得不提到矩阵的概念。矩阵就像一个二维数组，存储了一组数据，如：

$M=\left[ \begin{matrix} 1&2&3\\ 4&5&6\\ 7&8&9\end{matrix} \right]$

用 $M_{i,j}$ 表示矩阵第 $i$ 行第 $j$ 列的数据，如 $M_{2,3}=6$。

This page is locked

前置知识

数组，结构体，二叉树

引入

有时候我们会遇到一些大规模的区间查找和区间修改问题，比如让你维护一个 $10^5$ 长度的数列，要求操作有区间求和、区间加（区间每个数加上一个值），让你在一秒内完成 $10^5$ 次操作。
暴力是肯定不行的，数据范围太大，操作太多，会超时。
所以我们就有一种专门解决大范围区间修改查询的数据结构：线段树。

引自：《信息学奥赛之-数学一本通》
揍是这样：

$\operatorname{F}(n)=\dfrac{\sqrt{5}}{5}\cdot\left[\left(1+\sqrt{5}\right)^n-\left(1-\sqrt{5}\right)^n\right]$

代码揍这么简单：

1
2
3

int fibo(int n){
	return (sqrt(5)/5)*(pow((1+sqrt(5))/2,n)-pow((1-sqrt(5))/2,n));
}

要是再加个快速幂就更棒了（够快了，懒得写）

前置知识

存图方式（邻接表，邻接矩阵）,图的遍历（dfs，bfs）

引入

我们举个例子吧：
有一个毒瘤水管工，他会造水管，有一天他造了一个水管网络，就像一个图。其中有一个点只有出边，就是起点，还有一个点只有入边，是终点。
点之间有一些管子，这些管子都有单位时间内的容量，现在毒瘤水管工想知道，他的管子在单位时间内在起点终点之间最多能流多少水。

前置知识

存图方式（邻接表，邻接矩阵），并查集。
不会的快进入链接学习吧！

引入

生成树，就是从一个图中选中$n-1$条边，使得这些边构成一棵树，并包含图中的所有节点。
最小生成树，就是找到一种生成树，使得这个生成树的边权和最小。

前置知识

哈哈，简单到爆，没有。

引入

并查集是一种快到爆炸的集合算法，可以进行两项基本操作：合并两个集合（并）、查询两个参数是否在一个集合内（查）。这也是它名字的由来。

前置知识

必备：存图方式（邻接表，邻接矩阵），dfs序。
维护：线段树、树状数组、BST。
不会的快进入链接学习吧！

引入

树链剖分，简单来说就是把树分割成链，然后维护每一条链。一般的维护算法有线段树，树状数组和BST。复杂度为$O(log n)$。

$\texttt{Is KaTeX working?-IT WORKED!NICE!}$

$a^b$

$\left(\dfrac{a}{b}\right)$