“算法”
ACM程序课算法笔记19——矩阵快速幂
ACM程序课算法笔记19——矩阵快速幂 矩阵快速幂是对递推式的一种高效解决方法。 主要的解决问题是类似于斐波那契数列 f(n) = f(n - 1) + f(n - 2) 的使用。 不过我们要先...
ACM程序课算法笔记18——中国剩余定理
ACM程序课算法笔记18——中国剩余定理 问题引入 《孙子算经》中有问「物不知数」：有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？ 即希望x同时满足多个模线性方程，然后求解。...
ACM程序课算法笔记17——树链剖分
ACM程序课算法笔记17——树链剖分 定义 将一个树分割成若干条链即树链剖分。 树链剖分有多种形式，有重链剖分和长链剖分。至于如何剖分，实际上就是让每个点都选择一条边，并且这些边形成多个链条，重...
ACM程序课算法笔记16——2-SAT
ACM程序课算法笔记16——2-SAT 定义 SAT 是适定性（Satisfiability）问题的简称。一般形式为 k - 适定性问题，简称 k-SAT。 对于n个集合，每个集合仅有两个元素。...
ACM程序课算法笔记15——强联通分量
ACM程序课算法笔记15——强联通分量 问题与目的 强联通的点是指，A点能到达B点，且B点能到达A点。 对于一个图，问有多少强联通分量？ Kosaraju 算法 获取目标图G1的反图G2（所有边...
ACM程序课算法笔记14——KMP算法
ACM程序课算法笔记14——KMP算法 简介 KMP算法是一个查找子串的算法，这种算法感觉在题目中都几乎不会出现了，但我们应当注意的是它的思想，算法思想大于算法本身。 问题 KMP算法输入两个字...
算法学习笔记10——康托展开
算法学习笔记(10): 康托展开 可以求一个组合的全排列的名次 比如：对于序列1,2,3 则序列排名为 1 2 3；1 3 2； 2 1 3； 2 3 1； 3 1 2； 3 2 1 这个排...
ACM程序课算法笔记13——线段树
ACM程序课算法笔记13——线线段树 线段树介绍 线段树的功能是维护一个数组，当然你可以用普通数组维护，线段树只是一种维护方式，它的特点是可以在O(LogN)的时间复杂度完成单点修改，区间修改，...
ACM程序课算法笔记12——树状数组
ACM程序课算法笔记12——树状数组 引入 对于数据储存，我们通常有求区间的需求，因此产生了不同的用于储存数据的数据结构，例如求区间和问题，我们会使用的前缀和数组。 本次我们考虑的问题是：单点更...
算法学习笔记9——后缀数组
算法学习笔记(9): 后缀数组 定义 后缀数组是对后缀的一个排序，每个后缀按照字典序进行排序，然后用两个数组来映射它们自己和它们的排名。 同时，为了便于记录后缀，我们记字符串s的后缀s[i:]记...