APTX博客

  • ACGN
  • Coding
  • DevOps
  • Daily
  • Share
  • Bangumi
落谷
OI

C/C++ 最短路算法Dijkstra算法 + 堆优化模板

简介 Dijkstra算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。 无优化复杂度:O(n ^ 2) 那么有O(km)的Spfa算法我们为什么需要Dijkstra算法呢? 因为某些毒瘤出题人会专门设计网格图来卡Spfa算法,使其变为O(m ^ 2)如下方提到的落谷题目。 洛谷:P3371(弱化版) Spfa能过    P4779(标准版)卡S…

2018年8月3日 0条评论 2943点热度 0人点赞 神楽坂 みずき 阅读全文
OI

C/C++Manacher算法(字符串判断回文串) 马拉车算法 模板

简介 朴素的算回文串的办法一般是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#…

2018年8月2日 0条评论 2175点热度 0人点赞 神楽坂 みずき 阅读全文
OI

C/C++字符串哈希(单哈希)Hash算法 模板

简介 Hash算法类似于给字符串进行加密的方式,方便判断重复 那字符串Hash就非常好理解了。就是把字符串转换成一个整数的函数。而且要尽量做到使字符串对应唯一的Hash值。 进制哈希是最常见(NOIP)的哈希方式 它的主要思路是选取恰当的进制,可以把字符串中的字符看成一个大数字中的每一位数字,不过比较字符串和比较大数字的复杂度并没有什么区别(高精数的比较也是O(n) 评测:洛谷P3370 模板 #include <cstdio> #include <cstdlib> #include <…

2018年8月2日 0条评论 2630点热度 6人点赞 神楽坂 みずき 阅读全文

神楽坂 みずき

萌萌萌,好萌!

搜索
最新 热点 随机
最新 热点 随机
站点域名变更通知 私たちの居る理由 《サクラノ詩》VI 章 直哉与蓝对话 从《AMRITA》到《HELLO WORLD》── 野﨑まど世界观下的个体与世界的真实感 几种云端 VSCode/类 VSCode 方案对比与部署 Summer Pockets REFLECTION BLUE 豪華限定版 早期予約色紙付き/通販・店舗対応版
C++快读快写模板 又快过年了,警惕新型骗子 #动漫#我的青春恋爱物语果然有问题:OP/ED/角色歌/Flac无损音乐下载 #洛谷#C/C++P1090 合并果子 Linux中zip/unzip命令简略笔记 #万事达活动#免费10元话费不限运营商
标签聚合
C++ ST OI 洛谷 C/C++ 动漫 日常 HTML
分类
  • ACGN
  • Coding
  • Daily
  • DevOps
  • OI
  • Share

COPYRIGHT © 2017-2022 APTX博客. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang