祝馀宫

算法简介：鱼龙沉四方$\tt Manacher $ 算法，也叫马拉车；是一个用于求字符串中最大回文子串的算法。相同于 KMP，$\tt Manacher$ 也是一种基于字符串的自动机，他们的本质都是基于已知信息来求出未知信息解决问题。而从实现上来讲，$\tt Manacher$ 算法更加相似于拓展 KMP，到时候慢慢推出来就知道了。 友情链接： 【算法介绍】拓展KMP（Z函数） | 祝馀宫 算法小引：赫赫雷涌起我们首先从这个算法最最基础的模板开始：P3805 【模板】manacher - 洛谷 | 计算机科学教育新生态题目的意思很简单，要我们求一个字符串的最长回文子串。 那么首先考虑暴力，这里提一嘴，发现了一个很有趣的现象：同样是 $O(n^3)$ 的暴力，如果我们优先计算较短的回文串这题只能拿十八分，但是如果优先计算较长的回文串，答案会是原来的两倍也就是三十六分！这里贴上两次的代码以方便比较。 1234567891011121314151617181920212223242526// 18ptsinline void Work() { int n = strlen ...

算法简介：幽邃鸦眼首先说呢，这个拓展 KMP 其实和 KMP 关系不算特别大。我们定义了一个函数 $\operatorname Z(i)$ 表示字符串 $s$ 中 $s[1\dots n]$ 和字符串 $s[i\dots n]$ 的最长公共前缀的长度，这个函数被叫做 $\operatorname Z$ 函数，由于其代码实现相似于 KMP 算法，于是呢这个算法在国内被称为拓展KMP也就是说本名 $\operatorname Z$ 函数，小名拓展 KMP 。 算法演示：圣裁影羽那么首先的首先，我们要知道一个新的算法怎么做，我们肯定是从他的定义出发来看看暴力是怎么样的。那么说我们已经在简介中给出了 $\operatorname Z$ 函数的定义：函数 $\operatorname Z(i)$ 表示字符串 $s$ 中 $s[1\dots n]$ 和字符串 $s[i\dots n]$ 的最长公共前缀的长度。我们可以给出一个例子尝试一下。哦对了我们有一个特殊值 $\operatorname Z(1)=0$ 就是说原字符串和原字符串的最长公共前缀长度，本来说应该是 $n$ 的，但是被特殊定义成了 $ ...

算法简介：外酥里嫩众所周知，我们在数学上的两点间距离一般指的是直线距离。也就是欧几里得距离，但是，这篇文章我们要讲的是另外两个常用的距离，曼哈顿还有切比雪夫距离。 所谓曼哈顿距离，对于二维直角坐标系来说，他就是两个点的横坐标之差还有纵坐标之差的和。我们还会用他来计算出切比雪夫距离的计算方式，所以说开始吧~ 算法演示：大火宽油首先来看看曼哈顿距离，虽然说我们已经知道曼哈顿距离是什么，也知道怎么去求他，但是呢题目肯定不会考你模板的，所以说我们来一个经典例题试试水。 Clarke 是一位患有多重人格障碍的患者。有一天，他变成了一个几何学的学习者。他对一种有趣的距离一一曼哈顿距离进行了研究。点 $A(x_A,y_A)$ 和点 $B(x_B,y_B)$ 之间的曼哈顿距离是 $|x_A - x_B| + |y_A - y_B|$ 。现在他想要找到 $n$ 个点中任意两点之间的最大距离。 那么其实就是式子转化的问题，因为我们肯定不可以用 $n^2$ 复杂度过这道题，所以说我们要考虑一种类似线性的做法。这就要基于式子的变形了，我们发现这个绝对值非常的难受，所以说我们首先需要的就是去掉绝对值。 大力分讨 ...

算法简介：如影流露的冷刃递归和回溯，亲家兄弟如影随形，几乎哪里都能看到他们，所以说这里的副标题是万物根基。递归的思想，相信都不陌生，就是把所有的问题分成小块小块的去解决。而回溯，就是在递归完了之后，往回走，再接着递归。这种一步一步的枚举方式，可以很方便的穷举出所有的情况结果，这个就是递归。 像我们熟知的算法动态规划，它最初的形态也是递归，不过因为递归的特性而不利于优化，所以呢后续就有了非递归形式的动规，而各种神奇的动规优化方式也接踵而来。 算法演示：层见叠出的谜象正如标题，层见叠出，就是递归的基本特征。对于斐波那契数列，相信大家都不陌生，我们可以用下列的函数来表示斐波那契的值： \forall x\in \operatorname N^{\ast},\operatorname{f}(x)= \begin{cases} 1 &{x\le 2}\\ \operatorname{f}(x-1) + \operatorname{f}(x-2) & \operatorname{other.} \end{cases}这就可以称为递归的基本形式了。如果我们要求第 $3$ 个斐波那契数，就会根据函数 ...

Definition of Combinatorial CountingWe all have studied some basic Combinatorial Counting in primary , middle or high school. But now I still want to tell you the definition of Combinatorial Counting. The Combinatorial Counting is a old things in math. Know we will get many branch in math that have some correlation with Combinatorial Counting. I think the Combinatorial Counting is a way to discuss the method to calculate a combo of set. We all know we have such as problem in primary : Problem : ...

算法简介：稳固阵线的魄力实话实说，这个被叫做基环树东西，没有什么强制的算法。本质上来讲，这是一种特殊的图，因为他特殊的性质，存在一种方式去统计和综合上面的信息，所以被单独拿出来讲了。 基环树，这个名字可以仍未是基于环的树，这个思维去解决问题的思路，还有答案的计算已经图的构建，都和环离不开关系，所谓基环基环，就是有环且仅有一个环的树。有时候也被称为章鱼图 算法基础：诱导殉爆的狙击那么首先，我们来介绍基环树的基本相关内容，首先给出一个基环树的图片。 说实话，这张图片可能画的不够明显。我们会发现这个被称为基环树的结构分为两个部分： 中间的环。树周围的分支，都围绕着中间的那四个环节点连出来。 周围的支。环的每一个节点，都可以看做一个以当前环节点为根的子树。 这和基环树的定义有关，一棵树增加一条边使得原图存在了一个环，这就是基环树。 而基环树处理问题的思路，就是分别处理每一个子树，然后再通过环统计一些答案。这就是基环树处理问题的基本思想，下面给出一个实例尝试一下。 算法演示：娴熟复装的技巧那么我们现在就给出演示实例。比如说我们要求基环树的直径，或者说距离最远的两个点对。这里给出一道例题：I ...

基础语法之“读入输出” 基本介绍在 C++ 读入有两种流派，第一种是 C++ 新出品的 cin/cout 代表的 IOS 流派。第二种是传承自 C 语言的 scanf/printf 代表的旧语法流派。当然还有一些人会使用 快读/快写 等高速读入方式，后面的文章会提及。 IOS 流派 读入 一般来讲，在新手入门时，推荐使用$cin$来读入，其格式类似于： 123456789#include<bits/stdsc++.h>#include<iostream>// iostream 是包含 cin/cout 的头文件，当然包括在万能头里，所以如果引用了万能头，就不必担心用不了 cin/cout 了using namespace std;// 另外，cin/cout 还依赖于 C++ 新出的 std 库，也就是说我们必须引用 std 命名空间才可以，就是上面那一句话，不然的话我们要在所有和 std 有关的工具前面加上 std:: 这是命名空间的引用方式，以后的文章也会提及，举个例子，如果没有引用 std 库，那么 cin/cout 会变成 std::cin/std: ...

算法简介：号 · 仙蕊玲珑这篇文章就是继二维数点里挖下的坑的扫描线内容了。对于扫描线问题，其实是非常广泛的，就像动态规划一样。他主要是提供了一个在二维平面上用平行于坐标轴的线一个一个扫描过来的思想。总归一句话：只有你想不到，没有你扫不到。 友情链接： 【算法介绍】二维数点 | 祝馀宫 只要你可以按照题目的意思建立出可以通过题目的坐标系和线段，使其可以用扫描线扫出来，那么它就是可以的！ 算法思想：武 · 西风长枪首先，既然叫做扫描线，那么上面叫做扫描呢？顾名思义，扫描扫描，从下到上扫一遍就可以了，但是扫描线其实还有一个特点，扫描线。其实所谓扫描线思想，就是把问题转化成一些线段，去按照某个顺序扫描他，然后顺便处理出问题。 我们可以先给出一个扫描线的经典问题，求矩形面积并。所谓矩形面积并，就是一堆矩形叠在一起，重复覆盖的地方只算一次，当然只出现一次的也是算一次（ 那么这题首先第一眼应该都是暴力，毕竟大家都没什么好的思路去做这样奇怪的题目，那么，如果是扫描线呢？他其实是可以做出这样的题目的。为什么，我们来想想矩形是什么。小学大家就学过老师的名言：点动成线，线动成面。其实矩形的本质，就是一个 ...