摘要:网络流是一种独特的图论模型题目,一般一些神仙提经过很精巧的模型转化,就会变成一道网络流的题目。 这种类型的题目杀伤力很大,不论是企业测试题还是oi竞赛题,只要涉及到模型转化就会变成毒瘤题。 这类题目的解法我会在模型篇讨论,这一篇主要还是以网络流基础为主。 本博客无图,真不是我嫌画得累,只是讲这个东西 阅读全文
posted @ 2019-11-14 16:54 LightHouseOfficial 阅读 (3) 评论 (0) 编辑
摘要:Hello,我回来更新线段树系列了。 由于目前鸽掉的文章有点多...所以只能慢慢填坑了。 最近联赛复习的时候写了几道觉得不错的线段树题,正好可以回来填个坑。 首先我们来看看这道题:LuoguP4145 这道题需要我们写一个数据结构,支持下面两种操作:1. 区间开平方 2. 区间求和 可以区间开平方的 阅读全文
posted @ 2019-11-12 11:11 LightHouseOfficial 阅读 (10) 评论 (0) 编辑
摘要:我这种小蒟蒻就只能浅谈一下矩阵这种神奇的东西啦。 但正因为是蒟蒻,所以讲的比较好懂(大概)。 本篇分为两部分——>上:矩阵加速递归+下:高斯消元 如果没有你想看的那我深感抱歉...我太弱了只会讲这两个(说不定以后有补充) ——正片开始—— 首先,不知道什么是矩阵的这里请:必应 我们用矩阵优化递推一般 阅读全文
posted @ 2019-11-11 20:50 LightHouseOfficial 阅读 (21) 评论 (0) 编辑
摘要:说了要肝的怎么能咕咕咕呢? 不了解DP或者想从基础开始学习DP的请移步上一篇博客:DP动态规划学习笔记 这一篇博客我们将分为上中下三篇(这样就不用咕咕咕了...),上篇是较难一些树形DP,中篇则是数位和状压DP,下篇则是各种DP的优化手段。 ——正片开始—— (为啥我最近的博客都喜欢写这个) 背包类 阅读全文
posted @ 2019-11-09 20:42 LightHouseOfficial 阅读 (17) 评论 (0) 编辑
摘要:作为考察范围最广,考察次数最多的算法,当然要开一篇博客来复习啦。 子曰:温故而知新,可以为师矣 我复习DP时有一些自己对DP的理解,也就分享出来吧。 ——正片开始—— 动态规划算法,即Dynamic Programming(以下简称为DP),是解决多阶段决策过程最优化问题的高效数学方法。自从1999 阅读全文
posted @ 2019-11-09 00:13 LightHouseOfficial 阅读 (159) 评论 (0) 编辑
摘要:没错...我就是要讲点分治。这个东西原本学过的,当时学得不好...今天模拟赛又考这个东西结果写不出来。 于是博主专门又去学了学这个东西,这次绝对要搞懂了...【复赛倒计时:11天】 ——正片开始—— 点分是一个用来解决树上路径问题、距离问题的算法。说直接点其实就是分治思想在树上的体现和应用。 首先是 阅读全文
posted @ 2019-11-05 21:35 LightHouseOfficial 阅读 (79) 评论 (0) 编辑
该文被密码保护。
posted @ 2019-11-04 15:14 LightHouseOfficial 阅读 (3) 评论 (0) 编辑
摘要:本章介绍关于素数的一些数论,限于篇幅不给出证明,需要证明的朋友自行相关证明。 什么是素数?只能被自己和1整除的数就是素数。 利用这个性质我们很容易得到下面的素数判断方法。 bool isPrime(int x){ if(x==1)return 0; for(int i=2;i*i<=x;i++) i 阅读全文
posted @ 2019-11-03 17:06 LightHouseOfficial 阅读 (11) 评论 (0) 编辑
摘要:Manacher算法是用来求一个字符串中最长回文串的算法。 考虑暴力求最长回文串的做法: 暴力枚举字符串中的所有字串判断是否回文,然后求最大值。 时间复杂度O(n^3),考虑优化。 我们从枚举所有字串改成枚举所有回文串的对称轴,向左右扩展直到不相等,得到最长回文串。 优化到O(n^2),还是不够优秀 阅读全文
posted @ 2019-11-03 16:10 LightHouseOfficial 阅读 (8) 评论 (0) 编辑
摘要:这篇博客不打算讲多么详细,网上关于后缀数组的blog比我讲的好多了,这一篇博客我是为自己加深印象写的。 给你们分享了那么多,容我自私一回吧~ 参考资料:这位dalao的blog 一、关于求SuffixArray的一些变量定义: 1. sa[i]=j,表示第i名的后缀从j开始 **存的是下标** 2. 阅读全文
posted @ 2019-11-03 00:53 LightHouseOfficial 阅读 (11) 评论 (0) 编辑