当前位置: 首页 > news >正文

对我学过的算法的一些总结

随缘更新,希望能帮到你,不过肯定能帮到我就是了。
\(\LaTeX\) 写的不是很严谨,其中的 “\(=\)” 具体是等于还是赋值就自己悟吧。


不知道该怎么归类的算法

二分

对具有单调性的东西快速查找合法边界,\(O(log_n)\),模板,oiwiki。

二分查找

对具有单调性的数组操作,每次以 \(mid = {l+r\over 2}\) 作为边界将搜索范围缩小 \(len\over 2\),细节非常多。

二分答案

如果答案具有单调性(有一个明确的“合法 & 不合法”的分界点,一侧所有都合法另一侧所有都不合法),就对答案进行二分,直到找到最小(最大)的合法答案。


数据结构

栈和队列太简单不想写。

并查集

快速查询两个点之间的连通性,连通块个数与大小,复杂度不会算,模板,oiwiki。
记录每个点的父亲,初始每个点的父亲都是自己,合并时将一个点的祖宗的父亲从自己设置为另一个点的祖宗,查询联通性时查询祖宗是否相等,初始连通块个数为 \(n\),每合并一次连通块个数 \(-1\),连通块大小在合并时从被合并的集合加给合并的集合。

前缀和与差分

oiwiki

前缀和

快速查询离线数组区间和,初始化 / 修改 \(O(n)\),查询 \(O(1)\),模板。
已有一个数组 \(arr\),维护一个数组 \(pre\) 满足 \(pre_i = pre_{i-1}+arr_i\)(即“数组的前 \(n\) 项和”), \(\sum_{i=l}^{r}arr_i\) 的答案即为 \(pre_r - pre_{l-1}\)

差分

快速区间修改,修改 \(O(1)\),查询 \(O(n)\),模板。
对于数组 \(arr\),它的差分数组为 \(s_i=arr_{i}-arr_{i-1}\),对区间 \([l,r]\) 加上一个数字 \(a\) 即为 \(s_l = s_l+a,s_r = s_{r+1}-a\),查询时对 \(s\) 做一遍前缀和即可。

哈希表,堆

我不会。

链式前向星

存图用的,模板。
我也不知道这么写为什么对。

图论

DFS

我不会。

BFS

无边权时查找达到某个状态(点)的最少步骤(最短路径),oiwiki图论,oiwiki搜索。
设定好(可以是多个)初始状态,维护一个队列,将所有初始状态压入队列,每次拿出队头,遍历所有这个队头可以扩展到的状态并压入队列,因为没有边权所以 \(dist_j = dist_t + 1\),如果 \(dist_j \ne 0\) 即这个点被搜过,跳过即可。
没找着我写的模板,所以不放。

http://www.hskmm.com/?act=detail&tid=29187

相关文章:

  • 鲜花 10.12
  • 数组01
  • 实验一:逆向及BOF基础实践-20232301郑好
  • 排除通过IP访问MySQL时出现的连接错误问题
  • SciTech-Mathmatics-Proba. Stats.: 统计量: 增长速度、同比 与 环比 的概念、用途、示例、计算公式、注意事项
  • Java二维数组
  • 在Ubuntu系统上设置syslog日志轮替与大小限制
  • 从 “有人值守” 到 “少人运维”:智能巡检机器人重塑配电室管理模式 - 实践
  • 2025年10月最新推荐卫星电话品牌发布,涵防爆对讲卫星电话,卫星电话应急指挥系统,卫星电话防爆对讲终端,防爆手持卫星电话!
  • 很早就想注册博客园了
  • [KaibaMath]1006 关于∀ε0, |a-b|λε(λ0) = a=b的证明
  • dataset类
  • 【PolarCTF】nc
  • [ARC081E] Dont Be a Subsequence 题目分析
  • AI代理从概念验证到生产部署全流程
  • Azure Arc C2即服务:攻击与防御实战指南
  • CPU中的加法运算与减法运算
  • macos单独打开模拟器simulator
  • 子序列自动机学习笔记
  • 2018牛客网暑期ACM多校训练营(第一场)
  • 20232311 2025-2026-1 《网络与系统攻防技术》实验一实验报告
  • 你的认知模式,决定了你的人生高度
  • 在Typora中数学公式无法显示问题
  • 洛谷个人主页
  • 原码、反码、补码
  • C++ - 从字符串中提取一个数的若干种写法
  • ABC 日志
  • 251012
  • 如何在UE中创建动态枚举
  • 能连上 GitHub(SSH 验证成功),却 push 失败?常见原因与逐步解决方案 - 详解