共有 31 篇文章
网络流
2019-07-28 - 2024-09-15
  1. 最大流
  2. 最小费用最大流
链式前向星
2019-07-26 - 2024-09-15
前向星是一种特殊的边集数组中的每一条边按照起点从小到大排序,如果起点相同就按终点从小到大排序,并记录下某个点为起点的所有边在数组中的起始位置和存储长度,那么前向星就构造好了。
最大子矩阵
2019-07-22 - 2024-09-15
  1. 最大矩阵
  2. 最大正方形
  3. 最大子矩阵和
直线划分平面
2019-05-31 - 2024-09-15
如果一个平面中有n条直线,最多能将平面划分成多少区域。
判断两个线段相交
2019-05-29 - 2024-09-15

如何判断两条直线是否相交?

这很容易。平面直线,无非就是两种关系:相交 或 平行。因此,只需判断它们是否平行即可。而直线平行,等价于它们的斜率相等,只需分别计算出它们的斜率,即可做出判断。

但倘若我把“直线”换成“线段”呢——如何判断两条线段是否相交?

这就有些难度了。和 直线 不同,线段 是有固定长度的,即使它们所属的两条直线相交,这两条线段也不一定相交。

素数判定
2019-05-28 - 2024-09-15

所谓素数,是指恰好有两个约数的正整数。

  • 埃氏筛法
  • 区间筛法
  • Miller-Rabin素性测试
线段树
2019-05-28 - 2024-09-15

线段树(segment tree),顾名思义, 是用来存放给定区间(segment, or interval)内对应信息的一种数据结构。与树状数组(binary indexed tree)相似,线段树也用来处理数组相应的区间查询(range query)和元素更新(update)操作。与树状数组不同的是,线段树不止可以适用于区间求和的查询,也可以进行区间最大值,区间最小值(Range Minimum/Maximum Query problem)或者区间异或值的查询。

对应于树状数组,线段树进行更新(update)的操作为O(logn),进行区间查询(range query)的操作也为O(logn)。

最大子列和问题
2019-05-27 - 2024-09-15

求取数组中最大连续子序列和,例如给定数组为A={1, 3, -2, 4, -5}, 则最大连续子序列和为

    $math_inline$6$math_inline$

,即

    $math_inline$1+3+(-2)+4=6$math_inline$

方法一共有三种,复杂度分别为

    $math_inline$O(N^2)$math_inline$

    $math_inline$O(NlgN)$math_inline$

    $math_inline$O(N)$math_inline$

分解质因数
2019-05-26 - 2024-09-15

每个合数都可以写成几个质数相乘的形式,其中每个质数都是这个合数的质因数。如果一个质数是某个数的因数,那么就说这个质数是这个数的质因数。而这个因数一定是一个质数。

把一个合数用质因数相乘的形式表示出来,叫做分解质因数。如30=2×3×5 。分解质因数只针对合数。

质数: 质数(prime number)又称素数,有无限个。

质数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数。

合数: 合数指自然数中除了能被1和本身整除外,还能被其他数(0除外)整除的数。与之相对的是质数,而1既不属于质数也不属于合数。最小的合数是4。其中,完全数与相亲数是以它为基础的。

约数定理(约数个数定理,约束和定理)
2019-05-26 - 2024-09-15
约数个数定理可以计算出一个数约数的个数