矩阵树定理 1. 思想 矩阵树定理：对于一个无向图 GGG，它的生成树个数等于其基尔霍夫矩阵任何一个 N−1N - 1N−1 阶主子式的行列式的绝对值。 度数矩阵 DDD：是一个 N×NN \times NN×N 的矩阵，其中 D[i][j]=0(i≠j)D[i][j]=0 (i \neq j)D[i][j]=0(i=j)，D[i][i]=iD[i][i]=iD[i][i]=i 号点的度数。 邻接矩阵 A 2020-08-14 Technique ACM 算法 数学 Technique ACM 算法 数学
凸包算法 凸包类型的题算法主要有三种：JarvisMarch 算法、Graham 算法和 Andrew 算法，这三种算法时间性能上递增。 1. JarvisMarch 算法 1.1 思想 纵坐标最小然后横坐标最小的点一定是凸包上的点， 我们将其记为 p0{p_0}p0，从 p0{p_0}p0 开始，按逆时针的方向，逐个找凸包上的点，每前进一步找到一个点，所以叫作步进法。 选取下一个点的方法： 假设已找 2020-08-14 Technique ACM 算法 Technique ACM 算法
LCS、LIS、LICS算法 概念 首先，要理解子串和子序列的含义： 子串：来源于原序列连续的一段。 子序列：来源于原序列中元素相对顺序不变的一段，不要求元素连续。 1. LCS\mathrm{LCS}LCS（最长公共子序列） 1.1 转移方程 给定两个序列 AAA、BBB，设 C[i,j]C[i, j]C[i,j] 为 LCS(Ai,Bj)\mathrm{LCS}(A_i, B_j)LCS(Ai,Bj) 的长度，其中 2020-08-14 Technique ACM 算法 动态规划 Technique ACM 算法 动态规划
BSGS算法 1. 简介 BSGS 算法也称为大小步算法，主要用来解决 Ax≡Bmod p\begin{array}{c} A^x \equiv B \mod{p} \end{array} Ax≡Bmodp 的问题，其中 ppp 为质数。 2. 算法 令 x=i⋅m−jx = i \cdot m -jx=i⋅m−j，其中 m=⌈p ⌉m = \lceil \sqrt{p} \,\rceilm=⌈p⌉。此时 2020-08-14 Technique ACM 算法 数学 Technique ACM 算法 数学
二维几何基础 1. 点、线、凸边形 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899 2020-08-14 Technique ACM 算法 数学 Technique ACM 算法 数学
矩阵树定理 1. 思想 矩阵树定理：对于一个无向图 GGG，它的生成树个数等于其基尔霍夫矩阵任何一个 N−1N - 1N−1 阶主子式的行列式的绝对值。 度数矩阵 DDD：是一个 N×NN \times NN×N 的矩阵，其中 D[i][j]=0(i≠j)D[i][j]=0 (i \neq j)D[i][j]=0(i=j)，D[i][i]=iD[i][i]=iD[i][i]=i 号点的度数。 邻接矩阵 A 2020-08-14 Technique ACM 算法 数学 Technique ACM 算法 数学
最大流 1. 简介 最大流算法主要分为两大类，一类为增广路算法，一类为预流推进算法。最大流算法解决的是在有向网路图 G=(V,E) G = (V,E) G=(V,E) 中计算从源点 sss 到汇点 ttt 的最大流量问题，以及最小割容量问题。 最小割最大流定理 s−ts-ts−t 最大流的值等于 s−ts-ts−t 的最小割容量。 2. 增广路算法 剩余容量 剩余容量 cf(u,v)=c(u,v) 2020-08-14 Technique ACM 算法 图论 网络流 Technique ACM 算法 图论 网络流 网络流算法
最大流 1. 简介 最大流算法主要分为两大类，一类为增广路算法，一类为预流推进算法。最大流算法解决的是在有向网路图 G=(V,E) G = (V,E) G=(V,E) 中计算从源点 sss 到汇点 ttt 的最大流量问题，以及最小割容量问题。 最小割最大流定理 s−ts-ts−t 最大流的值等于 s−ts-ts−t 的最小割容量。 2. 增广路算法 剩余容量 剩余容量 cf(u,v)=c(u,v) 2020-08-14 Technique ACM 算法 图论 网络流 Technique ACM 算法 图论 网络流 网络流算法
PAT「1003 Universal Travel Sites (35分)」 1. 题目 题目链接：PAT「1003 Universal Travel Sites (35分)」 。 Description After finishing her tour around the Earth, CYLL is now planning a universal travel sites development project. After a careful investigat 2020-08-14 Technique ACM 题解 Technique ACM 题解
PAT「1002 Business (35分)」 1. 题目 题目链接：PAT「1002 Business (35分)」 。 Description As the manager of your company, you have to carefully consider, for each project, the time taken to finish it, the deadline, and the profit you can ga 2020-08-14 Technique ACM 题解 Technique ACM 题解