oi知识表+NOIP提高组算法及算法思想总结

算法及算法思想总结
│ By lib
│
├暴力
├模拟
├递归及递推:数位统计类
├构造
▼├排序算法
│ ├冒泡排序
│ ├选择排序
│ ├计数排序
│ ├基数排序
│ ├插入排序
│ ├归并排序
│ ├快速排序
│ ├堆排序
│ └二叉排序树
│
▼├分治
│ ├快速幂
│ ├单调区间求解(二分答案再验证)
│ ├二分后,先各自计算,然后再根据某种策略合并答案
│ ├逆序对统计
│
▼├贪心
│ ├不相交区间、区间选点问题、区间覆盖问题
│ ├流水作业调度问题、带期限和罚款的单位时间任务调度问题
│ ├其它最优化问题
│
▼├搜索
│ ▼├剪枝
│ │ ├最优化剪枝(可先贪心一个次优解)
│ │ ├可行性
│ │
│ ▼├深度优先搜索(dfs):网格数据
│ │ ▼├实现方式
│ │ │ ├递归实现(栈<=10000-20000层)
│ │ │ └非递归实现(手动栈)
│ │ │
│ │ ├贪心:预处理路径
│ │ ├回溯法
│ │
│ ▼├广度优先搜索(bfs):线性数据
│ │ ├队列(先进先出)
│ │ └双向广度优先搜索(从源汇点同时搜)
│ │
│ ├FloodFill(种子填充法)
│ ├搜索顺序
│ ├搜索与其他算法结合
│ ├二分检索
│
▼├规划
│ ▼├动态规划(DP)
│ │ ▼├优化
│ │ │ ├数据结构
│ │ │ ├单调队列
│ │ │
│ │ ├背包(背包九讲)
│ │ ├区间型动态规划
│ │ ├子序列型动态规划
│ │ ├环形动态规划
│ │ ├树形动态规划
│ │ ├字符串型动态规划
│ │ └记忆化搜索
│ │
│
▼├图论
│ ▼├基本概念
│ │ ├简单路径:一条路径上的结点除起点x1和终点xk可以相同外,其它结点均不相同(x1=xk的简单路径称为回路/环)
│ │ ├阶(图结点个数),度=入度+出度(奇点和偶点)
│ │ ├带权图称为网
│ │ ├子图:假设有两个图G=(V,E)和G’=(V’,E’),如果V’∈ V且E’∈ E,则称G’为G的子图。
│ │ ├连通分量:极大连通子图
│ │ ├混合图(有向+无向):“()”无向边;“<>”有向边
│ │ ├邻接边,邻接点
│ │ ├简单图(无环),完全图(点与点之间均有边)
│ │ ├迹(无重复边),通路/轨(无重复点),圈(起点和终点重合的轨)
│ │ ├DAG(有向无环图)
│ │
│ ├拓扑序(关键路径):AOV网
│ ▼├最短路(三角不等式)
│ │ ▼├算法
│ │ │ ▼├单源最短路(SSSP)
│ │ │ │ ├Dijkstra(无法处理负环)(堆优化) O(n^2) {O(E lg V)}
│ │ │ │ ▼└Spfa(堆优化) O(kE)
│ │ │ │ ├Bellman-Ford的变形
│ │ │ │ └松弛操作
│ │ │ │
│ │ │ ▼└所有顶点对间最短路(APSP)
│ │ │ ├Floyd:在最外层循环做了k-1次之后,dist[i][j]则代表了i到j的路径中,所有结点编号都小于k的最短路径。
│ │ │
│ │ ├次短路∈前K短路
│ │
│ ▼├(最小)生成树(MST)
│ │ ▼├无向图最小生成树
│ │ │ ├Prim(堆优化) O(V^2+E) {O((V+E) lg V)}
│ │ │ └Kruskal(并查集优化) O(E lg E+V*E) {O(E lg E+Eα(V))}
│ │
│ │
│ ▼├网络流
│ │ ▼├算法
│ │ │ ▼├增广路算法
│ │ │ │ ▼├Ford-Fulkerson方法
│ │ │ │ │ ├Edmonds-Karp算法(bfs) O(V*E^2)
│ │ │ │ │ └dfs(效率低下)
│ │ │ │ │
│ │ │ │ ▼└最短增广路算法(分层图) O(V^2*E)
│ │ │ │ ├最短路径增值(MPLA)
│ │ │ │ ├Sap(Gap优化) 推荐
│ │ │ │ └Dinic
│ │ │ │
│ │ │ ▼├预流推进算法:
│ │ │ │ ├push-relabel算法 O(V^2*E)
│ │ │ │ ├relabel-to-front算法 O(V^3)
│ │ │ │ └Hlpp(最高标号预流推进算法)(效率高但代码长) O(V^2*sqrt(E))
│ │ │ │
│ │ │ └压入与重标记算法
│ │
│ ▼├路径
│ │ ├哈密顿回路:点
│ │ └欧拉回路:边(欧拉图:含欧拉回路)
│ │
│ │
│ ├dfs序,bfs序的使用
│
▼├离散结构
│ ▼├串、树
│ │ ├LCA与RMQ相互转化
│ │
│ ▼├矩阵
│ │ ├部分和(前缀和)
│ │ ├离散化
│ │
│
│
▼├数据结构
│ ├顺序表:数组
│ ▼├链表
│ │ ▼├单链表
│ │ ├双链表
│ │ ├循环链表
│ │
│ ├串(见离散结构)
│ ▼├集合
│ │ ▼├哈希表(散列表)
│ │ │ ▼├哈希函数
│ │ │ │ ├直接定址法
│ │ │ │ ├数字分析法
│ │ │ │ ├平方取中法
│ │ │ │ └折叠法
│ │ │ │
│ │ │ ├分段Hash
│ │ │ ▼└处理冲突
│ │ │ ├拉链法
│ │ │ ├多哈希法
│ │ │ ├开放地址法
│ │ │ └建域法
│ │ │
│ │ └并查集(路径压缩)
│ │
│ ▼├堆
│ │ ▼├二叉堆
│ │ │ └最大-最小堆
│ │ │
│ │
│ ├栈:手写栈
│ ▼├队列
│ │ ├链队列
│ │ ├循环队列
│ │ ▼└优先队列(带权值的队列)
│ │
│ ▼├树
│ │ ▼├线段树
│ │ │ └Lazy标记
│ │ │
│ │ ├树状数组(在线支持修改的前缀和)
│ │
│ ▼└图的表示
│ ├邻接矩阵
│ ├邻接表
│ └链式前向星
│
▼├数学
│ ├高精度(*高精除高精不要求*)
│ ├排列组合:Stirling数
│ ├二项式定理
│ ├康托展开:一个全排列到一个整数的双射,经常用来做可以用全排列表示状态的搜索的哈希函数
│ ▼├组合计数
│ │ ▼├递推关系与生成函数(母函数)
│ │ │ ├普通型母函数
│ │ │ └指数型母函数:Fibonacci数列,Catalan数列
│ │ │
│ │ ├抽屉原理
│ │ ├容斥原理
│ │
│ ├素数及素数判定
│ ├乘法逆元(可用欧拉定理,扩展欧几里德定理求解):若ax≡1(mod f),则称a关于模f的乘法逆元为x。
│ ▼├最大公约数
│ │ ├欧几里德算法(辗转相除法):gcd(a,b)=gcd(b,a mod b)
│ │ └扩展欧几里德定理:存在唯一的整数 x,y 使得gcd(a,b)=ax+by
│ │
│
做题流程:1、建模(脱马甲);2、破冰(有序、单调、逆向,发散)(状态与状态间联系);3、设计数据结构保存相关信息,并在数据结构的基础上设计算法解决问题(要证明);4、编写代码、调试程序。
每题任务:1、你尝试了几个解题方向和思路?2、正解怎么做的?3、怎样从题目到正解?4、你自己目标分多少?有没有达到?
理科生做题,多问自己为什么要这么做,下次遇到类似的问题怎么办?
相关文章:
oi知识表+NOIP提高组算法及算法思想总结
算法及算法思想总结 │ By lib │ ├暴力 ├模拟 ├递归及递推:数位统计类 ├构造 ▼├排序算法 │ ├冒泡排序 │ ├选择排序 │ ├计数排序 │ ├基数排序 │ ├插入排序 │ ├归并排序 │ ├快速排序 │…...
【mysql】实现递归查询
mysql实现递归查询的方法:首先创建表,并初始化数据;然后向下递归,利用find_in_set()函数和group_concat()函数、with recursive实现递归查询。 mysql实现递归查询的方法: 1、创建表 DROP TABLE IF EXISTS t_areainf…...
JUC并发编程之原子类
目录 1. 什么是原子操作 1.1 原子类的作用 1.2 原子类的常见操作 原子类的使用注意事项 并发编程是现代计算机应用中不可或缺的一部分,而在并发编程中,处理共享资源的并发访问是一个重要的问题。为了避免多线程访问共享资源时出现竞态条件࿰…...
测试设计中隐藏的边界有哪些?
概述:边界值分析是测试设计一个稳定的部分,但是对黑盒测试人员来讲有时候边界并不是那么明显。这些不明显的边界被称作隐藏的边界。本文提供几个隐藏的边界的例子,还有一些以让隐藏边界显露来设计测试计划的要点方法。 使用边界值分析和等价…...
领航优配:暑期旅游市场热度持续攀升,相关公司业绩有望持续释放
到发稿,海看股份涨停,中广天择、探路者、众信旅行等涨幅居前。 8月8日,在线旅行板块震动上涨,到发稿,海看股份涨停,中广天择、探路者、众信旅行等涨幅居前。 今年以来,国内旅行商场逐渐恢复。文…...
基于 CentOS 7 构建 LVS-DR 集群 及 配置nginx负载均衡
一、构建LVS-DR集群 1、主机规划 Node01:PC Node02:LVS Node03、Node04:Webserver 2、部署环境 2.1 在Node02上配置 2.1.1 安装ipvsadm管理软件按 [rootlocalhost ~]# yum install -y ipvsadm 2.1.2 配置VIP [rootlocalhost ~]# if…...
docker搭建在线Markdown服务器
1.安装docker 2.编写docker-compose.yml version: "3" services:database:image: postgres:11.6-alpineenvironment:- POSTGRES_USERcodimd- POSTGRES_PASSWORDchange_password- POSTGRES_DBcodimdvolumes:- "database-data:/var/lib/postgresql/data"re…...
打靶练习:WestWild 1.1(一个简单但不失优雅的Ubuntu靶机)
主机发现和nmap信息收集 //主机发现 sudo nmap -sn 192.168.226.0/24 //扫描整个C段//端口扫描//初步扫描 sudo nmap -sT --min-rate 10000 -p- 192.168.226.131 -oA nmapscan/ports //用TCP的三次握手,以速率10000扫描1-65535端口,扫描结果以全格式…...
【2.3】Java微服务:sentinel服务哨兵
✅作者简介:大家好,我是 Meteors., 向往着更加简洁高效的代码写法与编程方式,持续分享Java技术内容。 🍎个人主页:Meteors.的博客 💞当前专栏:Java微服务 ✨特色专栏: 知识分享 &…...
【C++】开源:abseil-cpp基础组件库配置使用
😏★,:.☆( ̄▽ ̄)/$:.★ 😏 这篇文章主要介绍abseil-cpp基础组件库配置使用。 无专精则不能成,无涉猎则不能通。——梁启超 欢迎来到我的博客,一起学习,共同进步。 喜欢的朋友可以关注一下&#…...
【GPT-3 】创建能写博客的AI工具
一、说明 如何使用OpenAI API,GPT-3和Python创建AI博客写作工具。 在本教程中,我们将从 OpenAI API 中断的地方继续,并创建我们自己的 AI 版权工具,我们可以使用它使用 GPT-3 人工智能 (AI) API 创建独特的…...
[保研/考研机试] KY35 最简真分数 北京大学复试上机题 C++实现
题目链接: 最简真分数https://www.nowcoder.com/share/jump/437195121691719749588 描述 给出n个正整数,任取两个数分别作为分子和分母组成最简真分数,编程求共有几个这样的组合。 输入描述: 每组包含n(n<600&…...
算法备案后,企业需要做什么?合规与执行挑战
随着技术的迅猛发展,算法已经成为多数企业核心竞争力的一部分。但在技术进步的同时,我们也面临了算法透明度、公平性以及安全性的问题。因此,许多国家已经开始实施算法备案制度,以确保算法的应用满足一定的标准和规范。但在完成算…...
云原生应用程序的自动化管理和编排
云原生应用程序是一种为云环境设计的应用程序,它采用了如微服务、容器、可伸缩性和自动化等特性,以最大限度地提高效率和响应速度。本文将深入探讨云原生应用如何实现自动化管理和编排。 容器化 容器技术,如Docker,是云原生应用程…...
Spring项目整合过滤链模式~实战应用
代码下载 设计模式代码全部在gitee上,下载链接: https://gitee.com/xiaozheng2019/desgin_mode.git 日常写代码遇到的囧 1.新建一个类,不知道该放哪个包下 2.方法名称叫A,干得却是A+B+C几件事情,随时隐藏着惊喜 3.想复用一个方法,但是里面嵌套了多余的逻辑,只能自己拆出来…...
FFmpeg常见命令行(五):FFmpeg滤镜使用
前言 在Android音视频开发中,网上知识点过于零碎,自学起来难度非常大,不过音视频大牛Jhuster提出了《Android 音视频从入门到提高 - 任务列表》,结合我自己的工作学习经历,我准备写一个音视频系列blog。本文是音视频系…...
网络编程 tcp udp http编程流程 网络基础知识
讲解 网络基础知识网络编程tcp编程流程图示理解bind和accept函数理解监视套接字和链接套接字理解linux和window下的编程实现tcp特点 udp编程流程图示理解udp特点 http编程流程图示理解编程实现-网站服务器 网络基础知识 OSI分层:应用层 表示层 会话层 传输层 网络层…...
LaTeX基础学习笔记
LaTeX是一个文本编辑器。其类似于markdown,使用特殊标记和代码来修改文本格式,创建特殊字符等。可以使用overleaf在线LaTex编辑器编写LaTeX并转换为pdf文件(https://www.overleaf.com/) 同时推荐一个网站http://detexify.kirelab…...
zookeeper和kafka
目录 一、zookeeper理论 1.1、zookeeper定义 1.2、zookeeper工作机制 1.3、zookeeper特点 1.4、zookeeper的数据结构 1.5、zookeeper应用场景 1.6、zookeeper的选举机制 二、部署Zookeeper 集群 2.1、环境准备 2.2、安装 Zookeeper 2.3、修改配置文件 2.4、配置…...
服务器无法加载海康sdk依赖的问题
首先遇到的jna.jar和examples.jar无法加载的问题,尝试了很多方法无效,以下方法实测有效 其次是动态链接库无法加载的问题,而且是播放库,我的方法比较简单,netsdk加载出来就行了,播放库用不到,删…...
stm32G473的flash模式是单bank还是双bank?
今天突然有人stm32G473的flash模式是单bank还是双bank?由于时间太久,我真忘记了。搜搜发现,还真有人和我一样。见下面的链接:https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...
【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)
服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...
深入理解JavaScript设计模式之单例模式
目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式(Singleton Pattern&#…...
Java多线程实现之Callable接口深度解析
Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...
WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)
一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解,适合用作学习或写简历项目背景说明。 🧠 一、概念简介:Solidity 合约开发 Solidity 是一种专门为 以太坊(Ethereum)平台编写智能合约的高级编…...
多模态大语言模型arxiv论文略读(108)
CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题:CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者:Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...
如何在网页里填写 PDF 表格?
有时候,你可能希望用户能在你的网站上填写 PDF 表单。然而,这件事并不简单,因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件,但原生并不支持编辑或填写它们。更糟的是,如果你想收集表单数据ÿ…...
七、数据库的完整性
七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...
【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论
路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中(图1): mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...
脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)
一、OpenBCI_GUI 项目概述 (一)项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台,其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言,首次接触 OpenBCI 设备时,往…...
