栈（stack）
什么是栈？ 我们先回顾一下我们对于队列的学习。我们对于队列的理解，是一个队伍，在队尾进入，先进先出。 那么我们应该通过什么来理解栈呢？ 你可以想象一堆叠在一起的书构成“书塔”，由下往上叠放。每次放书都放在最上面那层书的上面，如果你想取书，由于书的重力你很难从“书塔”的中间取出来书，所以你只能从这一叠书的最上面取书。所以我们每次取书都是取得最上面得一本。你可以理解为一个单头的队列，只有队首，插入元素和删除元素都是针对队首进行的。 这种性质使得栈中先插入的元素会在后插入元素的“下方”,但是出栈是从所谓“上面”出栈，所以这就使得先插入的元素的出栈顺序在后插入的元素之后，所以栈具有先进后出的性质。 栈的代码实现 123const int MAXN = 10000007;int stack[MAXN];int p = 0; //栈顶指针 不难理解，依然类似于队列，我们通过数组和指针实现栈。这里的MAXN指的是栈最大支持的大小; 接下来是操作代码的实现 12345678910void push(int a){ if(p >= MAXN) cout<<"S...
队列（queue）
什么是队列？ 队列（queue）是一种数据结构，它的特点是只允许从队尾入队，从队列头部出队，满足先进先出的性质，即先进入队列的元素先出队列。可以把它理解为排队排在前一个人的后面。 比如数字1 5 7 9 2的队列，插入一个元素3，应该插入到队尾，成为3 1 5 7 9 2，再插入一个5，应该排到3的前面，变成5 3 1 5 7 9 2，出队一个头部元素2，则成为3 1 5 7 9，所以满足先进队列的先出队的先进先出性质。 此外，队列只允许队首出队，新元素也只能在队尾入队,访问只能访问队首和队尾,无法从中间进行入队出队的操作也无法访问队列中间的元素。 队列（queue）的代码实现 123int queue[MAXN];int head = 0;int tail = 0; $queue$数组为队列开辟需要的存储仪器：$MAXN$是队列的最大能入队元素的次数,一般开一个较大的数防止溢出 $head、tail$为指示队首与队尾元素的两个指针。 如果有新元素插入，就会插入到$tail$这个位置 12345void push(int x){ if(tail >= MAXN) ...
线性dp
对于线性动态规划，顾名思义指的就是根据题目内容可以得出线性相关的动态规划，如果书有序列（数组）那么状态就是一维的，如果是网格（棋盘）那么就是二维的。前文引例中的题目便是这种类型的。线性动态规划定义状态通常会考虑某类有序事件前面若干子事件的和 接下来我们给出例题 [HNOI2004] 打鼹鼠 题目描述 鼹鼠是一种很喜欢挖洞的动物，但每过一定的时间，它还是喜欢把头探出到地面上来透透气的。根据这个特点阿牛编写了一个打鼹鼠的游戏：在一个 $n \times n$ 的网格中，在某些时刻鼹鼠会在某一个网格探出头来透透气。你可以控制一个机器人来打鼹鼠，如果 $i$ 时刻鼹鼠在某个网格中出现，而机器人也处于同一网格的话，那么这个鼹鼠就会被机器人打死。而机器人每一时刻只能够移动一格或停留在原地不动。机器人的移动是指从当前所处的网格移向相邻的网格，即从坐标为 $(i, j)$ 的网格移向 $(i-1, j), (i+1, j), (i, j-1), (i, j+1)$ 四个网格，机器人不能走出整个 $n \times n$ 的网格。游戏开始时，你可以自由选定机器人的初始位置。 现在知道在一段时间内，...
动态规划（DP）的引入
动态规划的介绍 动态规划(Dynamic Programming)，简称DP，是运筹学的一个分支，用于解决多阶段决策过程中的最优化的一种数学方法，把多阶段问题变换为系列单阶段的问题加以解决的方法。 所以动态规划其实是一种数学方法，是求解某类问题的一种方法，不是一种特定的算法，更没有标准的数学表达式或者明确的定义的一种规则。 动态规划的根本是一种解决问题的思路，思考问题的方式，而不是具体的方法。所以动态规划的难点是思想上的，在于如何学会这种思想。这导致如果我们学习不善，很多时候会构造不出来动态规划所需要的形式，甚至根本想不到这是一道动态规划的问题。 而动态规划的基本思想，就是将一个大问题分解成若干个简单的小问题来求解。其中每一个阶段都需要做出决策，从而使得整个过程达到最优。 动态规划的三个重要要素 状态 动态规划的状态可以相对笼统的理解为“问题所在的局面”，例如，“从第i个数字到第j个数字的最大下降子系列”就是状态，是一种关于i,j的局面，然后“最”大下降子序列就是问题所对应的最优答案。某状态表示的答案（的值），方案（集合），在本质上相同，通常会用一个字母（$dp_i$或$f_...
宽度优先搜索（BFS）
前置知识 注意 该算法的前置知识为队列（queue）,如果没有学习，请点击这里进行学习 BFS的介绍 BFS（宽度优先搜索 Breadth-First Search）是一种用于图的遍历或搜索的算法。它从一个节点开始，逐层遍历图中的所有节点。BFS通常用队列来实现，因为它需要按照节点的发现顺序来访问它们。 工作原理 BFS的工作原理可以总结为以下几个步骤 循环：只要队列不为空，就执行以下操作： 出队一个节点（我们称之为当前节点）。 访问当前节点的所有未访问的邻居节点（子节点）。 将每个未访问的邻居节点（子节点）标记为已访问，并将其入队。 BFS算法的特点 层级遍历：它按层级顺序访问节点，这意味着它会先访问所有与源节点相邻的节点，然后是那些节点的邻居，以此类推。 最短路径：在无权图中，BFS可以找到从源节点到其他任何节点的最短路径。 时间复杂度：对于有V个顶点和E条边的图，BFS的时间复杂度是O(V+E)。 空间复杂度：在最坏的情况下，BFS可能需要O(V)的空间来存储所有节点的访问状态。 图示演示 下面进行进行图示演示： 首先1为根节点 假如我们使用的是DFS，那么DFS...
深度优先搜索（DFS）
DFS的介绍 DFS（深度优先搜索，Depth-First Search）是一种用于遍历或搜索树或图的算法。 它从一个节点开始，尽可能深地搜索树的分支，直到到达叶子节点（没有子节点的节点），然后回溯到上一个节点，继续搜索其他分支。 这个过程会一直进行，直到所有可能的分支都被探索完毕。 工作原理 DFS的工作原理可以总结为以下几个步骤 选择一个起始节点：从树或图的某个节点开始。 探索尽可能深的分支：从当前节点开始，选择一个未被访问过的邻接节点，然后递归地在该节点上执行DFS。 回溯：当当前节点的所有邻接节点都被访问过，或者到达了叶子节点时，回溯到上一个节点。 重复：重复步骤2和3，直到所有节点都被访问过。 DFS的特点 栈的使用：在实现DFS时，通常使用栈数据结构来存储节点。在递归实现中，调用栈隐式地充当了栈的角色。 时间复杂度：对于有V个顶点和E条边的图，DFS的时间复杂度通常是O(V + E)。 空间复杂度：在最坏的情况下，DFS的空间复杂度也是O(V)，因为可能需要存储整个路径上的节点。 路径搜索：DFS非常适合于寻找从起点到终点的路径，尤其是在图不是非常大的情况下。 ...