当前位置: 首页 > 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.gsyq.cn/news/19327.html

相关文章:

  • Java二维数组
  • 在Ubuntu系统上设置syslog日志轮替与大小限制
  • 从 “有人值守” 到 “少人运维”:智能巡检机器人重塑配电室管理模式 - 实践
  • 2025年10月最新推荐卫星电话品牌发布,涵防爆对讲卫星电话,卫星电话应急指挥系统,卫星电话防爆对讲终端,防爆手持卫星电话!
  • dataset类
  • [ARC081E] Dont Be a Subsequence 题目分析
  • macos单独打开模拟器simulator
  • 子序列自动机学习笔记
  • 2018牛客网暑期ACM多校训练营(第一场)
  • 20232311 2025-2026-1 《网络与系统攻防技术》实验一实验报告
  • 你的认知模式,决定了你的人生高度
  • 在Typora中数学公式无法显示问题
  • C# 集合框架完全指南:从IEnumerable到ObservableCollection的深度解析 - 教程
  • docker常用命令 - 实践
  • 如何在UE中创建动态枚举
  • 搭建SSH服务于RK3399平台上的Ubuntu 18.04,实现远程连接
  • UE网络编程完全指南:UDP TCP WebSocket实现详解
  • 从十五岁的今天写给十六岁的明天
  • Java依记 DAY02 - I
  • WAV 转 flac 格式
  • 详细介绍:MySQL专用服务器自动调优指南
  • P4147 玉蟾宫(最大子矩形)
  • 【实录】应用 Verdaccio 从零搭建私有 npm 仓库(含完整步骤及避坑指南)
  • 2025 年 10 月西安房屋鉴定公司最新推荐排行榜:覆盖房屋安全评估、结构检测、承载力鉴定、危房鉴定领域,助您选专业机构
  • GESP C++5级 2025年6月编程2题解:最大公因数 - 教程
  • 阿里发布「夸克 AI 眼镜」:融合阿里购物、地图、支付生态;苹果拟收购计算机视觉初创 Prompt AI丨日报
  • 在AI技术唾手可得的时代,挖掘新需求成为制胜关键——某知名AI聊天框架需求探索
  • 数论学习之路
  • 详细介绍:C# WinForms的入门级画板实现
  • 【汇编】汇编语言运行过程