schtonn

前置知识

字符串基础操作；强烈建议先学习 KMP 和 manacher，对理解有很大帮助。

引入

假设模式串是 pat，文本串是 txt。

拓展 KMP，有时也叫 Z 函数，是求 pat 和 txt 的（所有）后缀的最大公共前缀长度，用 z[i] 表示。

前置知识

字符串基础操作。

引入

KMP 是一种字符串匹配算法，意思就是说给出模式串 pat 和文本串 txt（长度各为 m 和 n），找出模式串在文本串中出现的所有位置。

考虑用暴力来解决这一问题，那么：

对于文本串的每一位置，循序匹配模式串，遇到不匹配就退出。此算法时间复杂度 \(O(mn)\)。

KMP算法则用了一 \(O(m)\) 的预处理将时间复杂度缩减到了 \(O(n)\)。

引入

快速幂是一种效率极高，以至于题目中不得不取模防止数据越界的求幂算法。计算 \(a^n\) 的复杂度为 \(O(\log n)\)。

引入

说起进制，大家应该都不陌生。今天来讲一讲进制转换。

前置知识

动态规划，二进制基础知识。

引入

假设我们有一个矩形的棋盘，里面有 \(n\) 行 \(m\) 列的 \(1\times1\) 的方格，现在我们要往里面放 \(1\times2\) 的多米诺骨牌。要求骨牌不能重叠，正好填满棋盘的所有方格。求所有方案数。

这时我们可以利用状态压缩，对每一层进行动态规划。

前置知识

字符串基础操作。

引入

回文串，即 \(s=s_{rev}\)，也就是本身与反转相等。

想要找到字符串 \(s\) 中最大的回文子串，很容易想到的是一种复杂度为 \(O(n^2)\) 的朴素算法，也就是对于每一个点都向外扩展。

这里介绍一种复杂度为 \(O(n)\) 的最大回文子串算法，叫做 Manacher。

前置知识

图论，动态规划，二进制基础知识。

引入

我们都知道欧拉回路，也就是经过每条边正好一遍的路径。

哈密尔顿回路和欧拉回路很像，但是需要经过每个点正好一遍。

欧拉回路有稳定的解法，然而哈密尔顿回路是 NPC 的，没有多项式时间解法。

我们使用动态规划来解决哈密尔顿回路问题。

引入

想要了解矩阵快速幂，就不得不提到矩阵的概念。矩阵就像一个二维数组，存储了一组数据，如： \[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\)。

前置知识

数组，结构体，二叉树

引入

有时候我们会遇到一些大规模的区间查找和区间修改问题，比如让你维护一个 \(10^5\) 长度的数列，要求操作有区间求和、区间加（区间每个数加上一个值），让你在一秒内完成 \(10^5\) 次操作。

暴力是肯定不行的，数据范围太大，操作太多，会超时。

所以我们就有一种专门解决大范围区间修改查询的数据结构：线段树。

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

就是这样： \[\operatorname{F}(n)=\dfrac{\sqrt{5}}{5}\left[\left(\frac{1+\sqrt5}{2}\right)^n-\left(\frac{1-\sqrt5}{2}\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));
}