一、朴素的爆搜 01背包的普通爆搜版 //输入 4 5 2 3 1 2 3 4 2 2 //输出 7 每种情况选或不选。这里给出没看书前自己写的。 #include <iostream> #include <stdio.h> #include <vector> void init() { freopen(&quo…

前言 把力扣学习计划之图论基础写完了，萌生出挑出几道我觉得好的题目出来的想法。 在“图论基础”学习计划中搜索占主体。本篇博客也将围绕搜索展开。 搜索中抓住：方向 + 去重 知识点：（循循渐进） 邻接矩阵 在矩阵中的搜索，这里更偏向 bfs 搜索，但是和 dfs 差不多，都是向四周拓展 邻接链表和在图中的搜索 计数搜索、起点到终点的最小步数搜索 二分…

一、二分图模板 二分图的性质： 集合内部没有边 二分图当且仅当图中不含奇数环 1.1. 染色法判断是否为二分图 简要介绍 采用 $dfs$ 遍历图。尝试把和一个点相连的所有的点涂为不同色（一共两种颜色）。 什么情况下图不是二分图呢？尝试涂色时相邻点已被涂同样的颜色。 模板 //尝试将u染成col 的同时尝试拓展它的临边 bool dfs(int u…

模板 需要读者对以下知识有所了解：权值非负最短路、权值带负数最短路、并查集 一、prim 简要介绍 和朴素版的 Dijkstra 算法 相似，区别在于 $Dijkstra$ 的 $dist$ 数组用于存储从起点到该点的最短距离；而 $prim$ 算法的 $dist$ 数组用于存储该点到集合中的任意一点的最短距离。 模板 int prim(int n…

前言与模板 需要读者对最短路之不含负权边：Dijkstra算法朴素和堆实现 有所了解。 1、bellman-ford 适用情况： 与拓展次数有关 可用于负权。因为有次数限制，所以可以有负环（负权回路） 简要介绍： 暴力法。每次大循环的含义是向外拓展一次，每次大循环将所有的边遍历一次。 模板： //循环k次(拓展k次边) 每次循环尝试更新所有的节点最…

前言和模板 参考文档 第一次接触$Dijkstra$是在大一下复习数据结构期末考试看了下思路。现在刚开始大二下，打卡群写kuangbin专题最短路不得不学下$Dijkstra$🤣，事实证明（1）我很懒（2）人的潜力不容小觑，我曾以为自己永远也看不懂与图相关的算法。 再说下$Dijkstra$的适用前提： 带权图的最短路径 权值都为非负值 单点出发到…

视频讲解 前言 我与拓扑排序的故事 一开始接触是数据结构的课上、奈何那段时间沉迷玩游戏没有理解过代码。第二次是打卡群，一场力扣双周赛第二题是拓扑排序（我是暴力循环100次、哈希去重写的），群主发觉群员拓扑排序学的不行写拓扑专题。y总数组模拟数据结构、我看了还是不会啊🤣连续两天不会写、痛失20块。（我到现在也还不会y总的数组写法🤣。 后来寒假开始打卡…

讲解视频：https://www.bilibili.com/video/BV12i4y1f7ky/ 堆的本质 堆是一种特殊的完全二叉树。每一个节点的值都大于等于或者小于等于其孩子节点的值。 堆的操作时间复杂度如下： 插入：$O(log_n)$ 删除：$O(log_n)$ 获取最大/最小值：$O(1)$ 堆的分类（大根堆、小根堆） 大根堆 数据结构（…

配套视频：https://www.bilibili.com/video/BV1Su41197rq?spm_id_from=333.999.0.0 模板 BFS有强烈的“步数”意识。每一步的搜索向外扩展一层。 BFS的核心是搜索：让每个点向所有可能的方向搜索。 核心模板如下（带注释） while(q.size()) { int len = q.siz…

1.什么是递归 一个函数调用它本身就是递归。递归通常把一个大型复杂的问题层层转化为子问题，直到到子问题无需进一步递归就可以解决的地步。递归极大地降低了代码量。 通常来讲一个递归算法由以下部分组成： 能够不使用递归来产生答案的终止方案 可将所有其他情况拆分到基本案例 2.递归的作用 递归算法在以下情况下有着很大的作用： 数据的定义是按递归定义的 问题…