简介 Dijkstra算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。 无优化复杂度：O(n ^ 2) 那么有O（km）的Spfa算法我们为什么需要Dijkstra算法呢？ 因为某些毒瘤出题人会专门设计网格图来卡Spfa算法，使其变为O（m ^ 2）如下方提到的落谷题目。 洛谷：P3371（弱化版） Spfa能过 P4779（标准版）卡S…
简介 朴素的算回文串的办法一般是O（n ^ 2） 或 O（n ^ 3）的。而Manacher发明的马拉车算法能将空间复杂度和时间复杂度均优化到O（n）的线性。 具体算法过程是： 1、将字符串中加入# 如 abcde -> ##a#b#c#d#e 举个例子 一个字符串s = abbahopxpo，转换为$#a#b#b#a#h#o#p#x#p#o#（这里的字符 $ 只是为了防止越界，下面代码会有说明），如此，s 里起初有一个偶回文abba和一个奇回文opxpo，被转换为#a#b#b#a#和#o#p#x#…
简介 Hash算法类似于给字符串进行加密的方式，方便判断重复 那字符串Hash就非常好理解了。就是把字符串转换成一个整数的函数。而且要尽量做到使字符串对应唯一的Hash值。 进制哈希是最常见（NOIP）的哈希方式 它的主要思路是选取恰当的进制，可以把字符串中的字符看成一个大数字中的每一位数字，不过比较字符串和比较大数字的复杂度并没有什么区别(高精数的比较也是O(n) 评测：洛谷P3370 模板 #include <cstdio> #include <cstdlib> #include <…
