\(0.\) 简介 并查集是一种维护节点之间不相交集合关系的一种树状数据结构。在算法竞赛中较为常用。并查集的基本形态如下\(1.\) 一些定义 代表元素 代表元素是指代表这个集合的元素，通常由根节点表示。如上图的4号节点就是这个集合的代表元素。 父亲节点 和其他的树状数据结构类似，父亲节点就是某一节点“上方”的节点。在并查集中，边的方向始终指向父亲节点。 \(2.\) 并查集的功能与基本实现方式 基本的并查集一般实现两种操作：...
vibe算法是采用领域像素来创建背景模型，通过比对背景模型和当前输入像素值来检测前景。 模型的工作原理 背景像素样本（该点过去的像素和其领域的像素）的选取：邻域点选取采用8邻域方法随机选取。用v(x)表示图像中x处的像素在给定的欧几里得颜色空间所取得值，每个背景像素x由N个背景样本值集合来建模 M(x)={v1,v2,……vN} 根据模型M(x)对像素值v(x)进行分类，定义一个以v(x)为中心的半径为R的球...
\(0.\) 问题简介 有一棵树，告诉你它的节点数n，根的编号s以及所有的边。求m次询问，每次查询给定任意两个树上节点的最近公共祖先。 数据范围：\(n,m\leq 10^5\) \(1.\) 暴力 暴力很好理解，就是一个一个往他的父亲节点跳。学过并查集的同学们应该都知道，一个一个往上跳这种做法是很浪费时间的，所以针对这道题，也会\(tle\) \(2.\) 优化（倍增） 看标题也都会知道一定是倍增 针对并查集，我们采取的优化办法是路径压缩求解。但很...
7.1栈的应用 栈:后进先出，可以理解为一个箱子，而箱子的容量仅供一本书放入或拿出。每次可以把一本书放在箱子的最上方，也可以把箱子最上方的书拿出。 栈顶指针：始终指向栈的最上方元素的一个标记，栈中没有元素（即栈空）时令TOP为-1. 栈的常见操作示范实现,使用数组st[]来实现栈: (1)清空(clear): 栈的清空操作将栈顶指针TOP置为-1，表示栈中没有元素。 void clear(){TOP = -1; } (2)获取栈内元素个数(size) 栈内元素个数为TOP...
一、课前思考 两节我们讲了二分查找算法。当时我讲到，因为二分查找底层依赖的是数组随机访问的特性，所以只能用数组来实现。如果数据存储在链表中，就真的没法用二分查找算法了吗？ 实际上，我们只需要对链表稍加改造，就可以支持类似“二分”的查找算法。我们把改造之后的数据结构叫作跳表（Skiplist），也就是今天要讲的内容。 跳表这种数据结构对你来说，可能会比较陌生，因为一般的数据结构和算法书籍里都不怎么会讲。但是它确...
凸包的概念 首先，引入凸包的概念： 大概长这个样子： 那么，给定一些散点，如何快速地求出凸包呢（用在凸包上的点来表示凸包） Andrew算法流程和思想 常见的求凸包的算法有$Graham$和$Andrew$，$Andrew$是$Graham$扫描算法的变种，和$Graham$相比，$Andrew$更快，且更稳定，所以主要讲一下$Andrew$。 首先把所有点以$x$坐标为第一关键字，$y$坐标为第二关键字从小到大进行排序，可以肯定第一个点和最后一个点在答案中。...
一、引子 浏览器的前进、后退功能，我想你肯定很熟悉吧？ 当你依次访问完一串页面a-b-c之后，点击浏览器的后退按钮，就可以查看之前浏览过的页面b和a。当你后退到页面a，点击前进按钮，就可以重新查看页面b和c。但是，如果你后退到页面b后，点击了新的页面d，那就无法再通过前进、后退功能查看页面c了。 假设你是Chrome浏览器的开发工程师，你会如何实现这个功能呢？ 这就要用到我们今天要讲的“栈”这种数据结构。带着这个问题，我...
文章目录什么是集成算法常见的集成算法Bagging随机森林随机森林的特点优点缺点树的数量boosting模型adBoost工作流程Stacking模型 什么是集成算法 把多个基础算法一起拿来用，就是集成算法 目的就是让结果更加准确，让分类器的效果更好。 常见的集成算法Bagging——训练多个分类器取平均 Boosting——从弱学习器开始加强，通过加权来进行训练： Fm(x)=Fm?1(x)+argminh∑i=1nL(yi+,Fm?1(xi)+h(xi)) F_m(x) = F_{m-1}(x)+argmin_h \s...
首先，强烈安利一篇文章，这篇文章对于\(Manacher\)的讲解本人感觉非常到位。 传送门 本文也是对上文的一个整理。虽然上文已经讲得很好了一. 回文子串的一般解法 相信大家都知道的一个方法\(:\)枚举字符串的每一个位置作为回文子串的对称中心，同时向左向右扩展，判断是否相等，然后每次保存之前求取的最大回文子串长度，时间复杂度为\(O(n^2)\)。 在枚举时，还需要考虑对奇数回文串和偶数回文串分开处理，因为奇数回文串的对称中心...
算法用处： 解决最长回文子串的问题（朴素型）。算法复杂度 我们不妨先看看其他暴力解法的复杂度：\(O(n^3)\) 枚举子串的左右边界，然后再暴力判断是否回文，对答案取 \(max\) 。 \(O(n^2)\) 枚举回文子串的对称轴，向两边扩展，对答案取 \(max\) 。 \(O(n)\) \(\texttt{Manacher}\) 算法。显然我们的 \(\texttt{Manacher}\) 是十分优秀的。。。实现原理 \(\text{step 1}\) 首先我们需解决一个问题： 回文串的长度有有奇也有偶，这...
参考资料:menci的博客 前言: 最近在学习生成函数,无奈的发现如果我不学习\(O(nlogn)\)的多项式算法的话什么题也做不了qwq 于是就滚来学习FFT了 其实写的很烂,主要是给自己看的 好像整个机房就我不会这玩意了 定义 多项式 形如\(F(x)=\sum\limits_{i=0}^na_ix^i\)的柿子就是一个多项式,这个多项式的次数就是它的最高次数\(n\) 多项式的表示方法 系数表示法 就是用\(\{a_1,a_2,a_i,...,a_n\}\)来表示这个多项式． 点值表示法 就是用n...
一、学习内容二分查找法非递归 分治算法 动态规划算法 KMP算法 贪心算法 普里姆算法 克鲁斯卡尔算法 迪杰斯特拉算法 弗洛伊德算法 马踏棋算法二、算法代码 1 package Algorithm;2 3 /**4 * 二分查找非递归实现 默认有序5 * 6 * @author LEEWAY7 * 8 */9 public class BSAlgorithm { 10 public static int binarySearchN(int[] srcArray, int des) { 11 // 第一个位置. 12 int low = 0; 13 // 最高...
谱聚类算法 谱聚类【全称：Spectral Clustering】，是一种基于图切割的、有别于 KMeans 算法的无监督学习算法，它同样也使用了距离，但不需要指定 K 。以样本及样本间的距离构造一个图，根据指定的距离阀值初步切割图，形成若干个独立的子图，这些子图的含义与 KMeans 的簇相同，就是一个独立的分类。 涉及的矩阵知识 1. 余子式 也是一个行列式，是去掉 i 行 j 列后的一个行列式 Mij 称为元素 aij 的余子式。 2.代数余子式 对于元素...
接上一节方法的练习，做了一些经典的数学例子： 1.斐波那契数列： Fibonacci数列是是个特殊的数列，数列的规则是这样的： F(0)=0; F(1)=1; F(n)=F(n-1)+F(n-2)(n>=2) 从公式里就很明显看得出来这个数列很适合用递归来实现，递归的判定条件就是括号里的参数是否小于2；public static long Fib(int k){switch(k){case 0:return 0;case 1:case 2:return 1;default:return (Fib(k-1)+Fib(k-2));}}运行结果:2.欧几里得算法求解两个数的最...
同余3：解高次同余方程的BSGS算法及其扩展学习笔记阶原根指标离散对数BSGS算法扩展BSGS算法解决第二个公式的方法（待填） 前言：在前两篇博客，我提到了解决单个线性同余方程的方法，以及解决线性同余方程组的方法，但是，当单个同余方程变成Ax≡B(modP)A^x \equiv B \pmod PAx≡B(modP)或xA≡B(modP)x^A \equiv B \pmod PxA≡B(modP)时，蒟蒻的我又得自闭了，为了不再自闭，就不得不提到BSGS算法 。BSGS算法，原名Baby Step,Giant...