树分为有根，无根两种，性质有：1.连通，2.n-1条边，3无环。dfs和bfs遍历树。直径：树上两点之间的最长距离。两次dfs确定。偏心距:距路径F最远的点到F的距离。核(为点的时候称为中心)为偏心距最小的点。重心：所有子树中最大子树...

最小生成树一般是求边权之和最小。Prim算法和Kruskal算法是求解最小生成树的两种算法。 //Prim算法堆优化 #include<iostream> #include<vector> #include<queu...

Floyd算法可在任意权图中求多源最短路，时间复杂度为O(n^3)，适用于n较小的情况。以P2910为例。 #include<iostream> #include<vector> using namespace std; ...

Dijkstra算法主要在非负权图中求最短路，朴素做法O(n^2),堆优化O((m+n)logn),前者在稠密图(m>=n^2)中效率较高，后者在稀疏图中效率较高。SPFA算法(Bellman-Ford算法队列优化)在...

二分查找和二分答案(最大的最小，最小的最大，最值问题)。 //二分查找可用lower_bound和upper_bound函数实现 //最大 long long l = 最小可能值, r = 最大可能值, ans = 0; while ...

先介绍一下部分常见数论知识点。快速幂+裴蜀定理+扩展欧几里得算法+乘法逆元+费马小定理+线性筛。 //快速幂，p为模数，快速幂常解决a^b%p问题 int qpow(int a,int b){ int res=1; ...

高精度处理非常大的数字，通过数组或者字符串实现，以下以数组的方式实现加减乘除(仅展示部分代码)。 vector<int> add(const vector<int> &a,const vector<int>...

以UVA12304 2D Geometry 110 in 1为例，介绍一些二维几何的知识。基本概念：点乘+叉乘+向量长度+向量极角（atan2）+弧度转角度+角度转弧度+旋转向量（采用逆时针旋转公式）+单位化向量+单位法向量函数。点和...

求点对之间的最长距离或者说是凸包的直径，在Andrew算法的基础上，使用旋转卡壳来求解。旋转卡壳主要通过双指针进行扫描，维护两个指针分别指向凸包上的两个点，计算它们之间的距离，并根据叉乘的符号来移动指针。以下以P1452 Beauty...

Andrew算法，稳定并且代码简单，建立手动栈，分上下凸包去构建，时间复杂度O(nlogn)。以下以P2742 圈奶牛为例，代码如下： #include<iostream> #include<vector> #includ...