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

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提高组算法及算法思想总结

&#xfeff;算法及算法思想总结 │ By lib │ ├暴力 ├模拟 ├递归及递推:数位统计类 ├构造 ▼├排序算法 │ ├冒泡排序 │ ├选择排序 │ ├计数排序 │ ├基数排序 │ ├插入排序 │ ├归并排序 │ ├快速排序 │…...

【mysql】实现递归查询

mysql实现递归查询的方法&#xff1a;首先创建表&#xff0c;并初始化数据&#xff1b;然后向下递归&#xff0c;利用find_in_set()函数和group_concat()函数、with recursive实现递归查询。 mysql实现递归查询的方法&#xff1a; 1、创建表 DROP TABLE IF EXISTS t_areainf…...

JUC并发编程之原子类

目录 1. 什么是原子操作 1.1 原子类的作用 1.2 原子类的常见操作 原子类的使用注意事项 并发编程是现代计算机应用中不可或缺的一部分&#xff0c;而在并发编程中&#xff0c;处理共享资源的并发访问是一个重要的问题。为了避免多线程访问共享资源时出现竞态条件&#xff0…...

测试设计中隐藏的边界有哪些?

概述&#xff1a;边界值分析是测试设计一个稳定的部分&#xff0c;但是对黑盒测试人员来讲有时候边界并不是那么明显。这些不明显的边界被称作隐藏的边界。本文提供几个隐藏的边界的例子&#xff0c;还有一些以让隐藏边界显露来设计测试计划的要点方法。 使用边界值分析和等价…...

领航优配:暑期旅游市场热度持续攀升,相关公司业绩有望持续释放

到发稿&#xff0c;海看股份涨停&#xff0c;中广天择、探路者、众信旅行等涨幅居前。 8月8日&#xff0c;在线旅行板块震动上涨&#xff0c;到发稿&#xff0c;海看股份涨停&#xff0c;中广天择、探路者、众信旅行等涨幅居前。 今年以来&#xff0c;国内旅行商场逐渐恢复。文…...

基于 CentOS 7 构建 LVS-DR 集群 及 配置nginx负载均衡

一、构建LVS-DR集群 1、主机规划 Node01&#xff1a;PC Node02&#xff1a;LVS Node03、Node04&#xff1a;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的三次握手&#xff0c;以速率10000扫描1-65535端口&#xff0c;扫描结果以全格式…...

【2.3】Java微服务:sentinel服务哨兵

✅作者简介&#xff1a;大家好&#xff0c;我是 Meteors., 向往着更加简洁高效的代码写法与编程方式&#xff0c;持续分享Java技术内容。 &#x1f34e;个人主页&#xff1a;Meteors.的博客 &#x1f49e;当前专栏&#xff1a;Java微服务 ✨特色专栏&#xff1a; 知识分享 &…...

【C++】开源:abseil-cpp基础组件库配置使用

&#x1f60f;★,:.☆(&#xffe3;▽&#xffe3;)/$:.★ &#x1f60f; 这篇文章主要介绍abseil-cpp基础组件库配置使用。 无专精则不能成&#xff0c;无涉猎则不能通。——梁启超 欢迎来到我的博客&#xff0c;一起学习&#xff0c;共同进步。 喜欢的朋友可以关注一下&#…...

【GPT-3 】创建能写博客的AI工具

一、说明 如何使用OpenAI API&#xff0c;GPT-3和Python创建AI博客写作工具。 在本教程中&#xff0c;我们将从 OpenAI API 中断的地方继续&#xff0c;并创建我们自己的 AI 版权工具&#xff0c;我们可以使用它使用 GPT-3 人工智能 &#xff08;AI&#xff09; API 创建独特的…...

[保研/考研机试] KY35 最简真分数 北京大学复试上机题 C++实现

题目链接&#xff1a; 最简真分数https://www.nowcoder.com/share/jump/437195121691719749588 描述 给出n个正整数&#xff0c;任取两个数分别作为分子和分母组成最简真分数&#xff0c;编程求共有几个这样的组合。 输入描述&#xff1a; 每组包含n&#xff08;n<600&…...

算法备案后,企业需要做什么?合规与执行挑战

随着技术的迅猛发展&#xff0c;算法已经成为多数企业核心竞争力的一部分。但在技术进步的同时&#xff0c;我们也面临了算法透明度、公平性以及安全性的问题。因此&#xff0c;许多国家已经开始实施算法备案制度&#xff0c;以确保算法的应用满足一定的标准和规范。但在完成算…...

云原生应用程序的自动化管理和编排

云原生应用程序是一种为云环境设计的应用程序&#xff0c;它采用了如微服务、容器、可伸缩性和自动化等特性&#xff0c;以最大限度地提高效率和响应速度。本文将深入探讨云原生应用如何实现自动化管理和编排。 容器化 容器技术&#xff0c;如Docker&#xff0c;是云原生应用程…...

Spring项目整合过滤链模式~实战应用

代码下载 设计模式代码全部在gitee上,下载链接: https://gitee.com/xiaozheng2019/desgin_mode.git 日常写代码遇到的囧 1.新建一个类,不知道该放哪个包下 2.方法名称叫A,干得却是A+B+C几件事情,随时隐藏着惊喜 3.想复用一个方法,但是里面嵌套了多余的逻辑,只能自己拆出来…...

FFmpeg常见命令行(五):FFmpeg滤镜使用

前言 在Android音视频开发中&#xff0c;网上知识点过于零碎&#xff0c;自学起来难度非常大&#xff0c;不过音视频大牛Jhuster提出了《Android 音视频从入门到提高 - 任务列表》&#xff0c;结合我自己的工作学习经历&#xff0c;我准备写一个音视频系列blog。本文是音视频系…...

网络编程 tcp udp http编程流程 网络基础知识

讲解 网络基础知识网络编程tcp编程流程图示理解bind和accept函数理解监视套接字和链接套接字理解linux和window下的编程实现tcp特点 udp编程流程图示理解udp特点 http编程流程图示理解编程实现-网站服务器 网络基础知识 OSI分层&#xff1a;应用层 表示层 会话层 传输层 网络层…...

LaTeX基础学习笔记

LaTeX是一个文本编辑器。其类似于markdown&#xff0c;使用特殊标记和代码来修改文本格式&#xff0c;创建特殊字符等。可以使用overleaf在线LaTex编辑器编写LaTeX并转换为pdf文件&#xff08;https://www.overleaf.com/&#xff09; 同时推荐一个网站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无法加载的问题&#xff0c;尝试了很多方法无效&#xff0c;以下方法实测有效 其次是动态链接库无法加载的问题&#xff0c;而且是播放库&#xff0c;我的方法比较简单&#xff0c;netsdk加载出来就行了&#xff0c;播放库用不到&#xff0c;删…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

Caliper 负载(Workload)详细解析

Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...

springboot 日志类切面,接口成功记录日志,失败不记录

springboot 日志类切面&#xff0c;接口成功记录日志&#xff0c;失败不记录 自定义一个注解方法 import java.lang.annotation.ElementType; import java.lang.annotation.Retention; import java.lang.annotation.RetentionPolicy; import java.lang.annotation.Target;/***…...