Mai Icy

“算法课笔记”

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算法输入两个字...

ACM程序课算法笔记13——线段树入门

ACM程序课算法笔记13——线段树入门 线段树介绍 线段树的功能是维护一个数组,当然你可以用普通数组维护,线段树只是一种维护方式,它的特点是可以在O(LogN)的时间复杂度完成单点修改,区间修改...

ACM程序课算法笔记12——树状数组

ACM程序课算法笔记12——树状数组 引入 对于数据储存,我们通常有求区间的需求,因此产生了不同的用于储存数据的数据结构,例如求区间和问题,我们会使用的前缀和数组。 本次我们考虑的问题是:单点更...

ACM程序课算法笔记11——差分约束

ACM程序课算法笔记11——差分约束 差分约束方程组 差分约束指的是一种多个元素之间差的限制,而求某两个值的最大差。 例如求: x1 - x0 <= 2——① x2 - x0 <= ...

ACM程序课算法笔记10——最短路径问题

ACM程序课算法笔记10——最短路径问题 松弛 最短路算法中,松弛是最关键的思想,彻底的理解松弛,就能理解最短路径的算法。 以下是边的松弛,而且是有向边的松弛。 void relax(Weigh...