Mai Icy
ACM程序课算法笔记14——KMP算法
ACM程序课算法笔记14——KMP算法简介KMP算法是一个查找子串的算法，这种算法感觉在题目中都几乎不会出现了，但我们应当注意的是它的思想，算法思想大于算法本身。 问题KMP算法输入两个字符串A...
算法学习笔记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:]记为i...
ACM程序课算法笔记11——差分约束
ACM程序课算法笔记11——差分约束差分约束方程组差分约束指的是一种多个元素之间差的限制，而求某两个值的最大差。 例如求： x1 - x0 <= 2——① x2 - x0 <...
ACM程序课算法笔记10——最短路径问题
ACM程序课算法笔记10——最短路径问题松弛最短路算法中，松弛是最关键的思想，彻底的理解松弛，就能理解最短路径的算法。 以下是边的松弛，而且是有向边的松弛。 void relax(Weighte...
ACM程序课算法笔记9——计算几何入门
ACM程序课算法笔记9——计算几何入门线段属性1.给两条有向线段p0p1和p0p2，线段1是否在线段2顺时针方向？ 2.给两条有向线段p0p1和p1p2，线段2是左拐还是右拐？ 3.给两条有向线...
算法学习笔记8——同余
算法学习笔记(8): 同余前置知识： 整除：当 A / B 为一个整数， 则称 B 整除 A 符号记作：B|A 同余：同余是一种二元关系，需要第三者作为模也就是 A % p == B ...
ACM程序课算法笔记8——二分答案
ACM程序课算法笔记8——二分答案问题一：序列划分问题描述：给定n个正整数数组a，将这个序列从左到右划分成m段，使得每段至少有一个数；你需要让数字之和最大的那一段的数字和尽可能的小；求最大和最小...