KMP(Knuth-Morris-Pratt)算法是一种高效的字符串匹配算法。其核心精髓在于:当匹配失败时,能够利用已匹配的信息,避免模式串指针的回溯,实现“原地”跳跃。 next[i] 的定义是:模式串 P 从第 1 位到第 i 位组成的字符串中,最长公共前后缀的长度。 为何会有 j = ne[j]? 当 P[i]
Miller-Rabin 素数判定算法是可以快速判定质数的一个概率性算法,时间复杂度约为 ,远远快于试除法的 Miller-Rabin 算法是费马小定理与二次探测定理的结合,通过寻找“非平凡平方根”来从概率上判定一个数是否为合数。 如果 是素数,对于任意整数 ( ),满足: 局限性:存在“卡迈克尔数”(伪素数),它们是
平面上简单多边形的面积S,其内部位于整数坐标点上点数目I,以及在边上的整点书目b,满足 1. 首先证明可加性.由假设有两个多边形 均满足Pick定理.且两个多边形有一条公共边,公共边上的点为 .我们设 .由假设得合并后多边形的内部点 ,边界点 ,带入Pick公式得 2. 首先易证得平面上的矩形都满足Pick定理,由可加
如何快速判断一个点是否在一个多边形内部? 这是一个很显然的定理(但很难证明),这条定理指出,每条平面上的简单封闭曲线总是将封面划分为两个部分. 我们考虑从一个点引出一条射线,显然射线一定会到达无穷远处,即对于任意的封闭曲线,射线的终点总是会在曲线外部. 我们考虑这条从曲线内部的一点引射线穿过这条封闭曲线的次数,显然每穿
在二维平面点集中,凸包是能够包含所有点的最小凸多边形。其顶点集是平面点集的子集,多边形内部角均小于 180 度。 Andrew 算法是 Graham 扫描法的变种,常数更优、鲁棒性更强: 1. 坐标排序:优先按 升序排序,若 相同则按 升序排序。 2. 构建下凸壳:从左往右扫描点,用单调栈维护向量叉积 (向左拐)。若出
每条有向直线左侧(或右侧)定义一个半平面。所有半平面的公共交集是一个凸多边形(或空集、无界区域)。 常用 Sutherland-Hodgman / 极角排序增量法 (双端队列) 在 内求解。 1. 极角排序:计算每条有向直线的极角 atan2(dy, dx),按极角排序。同极角平行向量保留最靠内侧的一条。 2. 双端队
更详细的内容可以参考[[Tutorial] Catalan Numbers and Catalan Convolution](https://codeforces.com/blog/entry/87585) 以走网格为例,从格点 走到格点 ,只能向右或向上走,并且不能越过对角线的路径的条数,就是卡特兰数,记为 。 (1

假设我们要合并分别以 为根节点的两棵左偏树,且维护的左偏树满足小根堆的性质: 1. 若为空则返回:如果 中有结点为空,返回 。 2. 确定根节点:选择 两结点中权值更小的结点,作为合并后左偏树的根。 3. 递归合并:递归合并 的右子树与 ,将合并后的根节点作为 的右儿子。 4. 维护性质:维护当前合并后左偏树的左偏性质
