Python基础教程
本文内容可能存在错误，欢迎指正习题没有标准答案，提供的题解仅供参考 基本操作数据的输入input()Python程序的输入通过函数input()实现，特别注意，利用input()函数输入的任何数据都是字符串类型所以需要整数数字需要用int()函数转换为整数 如下 1x = int(input("请输入x:")) 其中input()...
树状数组
前置知识学习树状数组之前，最好先了解下面这些内容： 前缀和与差分； 二进制与位运算； 树状数组的代码非常短，核心操作甚至只有几行。不过代码短不代表它很好理解，特别是第一次看到x += x & -x和x -= x & -x时，很容易产生一种“它为什么能这样跳”的疑问。 所以这篇文章不会只给出一个模板，而是从树状数组...
并查集
什么是并查集？并查集（Union-Find）是一种数据结构，主要用于处理动态连通性问题。它支持高效的合并（Union）和查询（Find）操作，常用于解决图的连通性、集合的合并等问题。通过并查集，我们可以将两个（或多个）元素合并到一个集合中，并查询两个元素是否同属一个集合。我们通过数组来实现这个操作 代码示范$fa[i]$指的是第i个元素的祖宗（可以理解...
堆（heap）
前置知识：注意：实现堆需要用到完全二叉树的知识，如果未学习，点击了我也没用，因为我还没写 什么是堆？堆（heap），又叫二叉堆，是一种基于完全二叉树实现的数据结构，它可以实现在堆顶的元素是整个堆里面最大的元素（大根堆），也可以是最小的元素（小根堆），进而获取到整个仪器中的最值的一种数据结构。通过它，我们可以快速获取一组数据中的最值，它的时间复杂度只有O...
栈（stack）
什么是栈？我们先回顾一下我们对于队列的学习。我们对于队列的理解，是一个队伍，在队尾进入，先进先出。那么我们应该通过什么来理解栈呢？你可以想象一堆叠在一起的书构成“书塔”，由下往上叠放。每次放书都放在最上面那层书的上面，如果你想取书，由于书的重力你很难从“书塔”的中间取出来书，所以你只能从这一叠书的最上面取书。所以我们每次取书都是取得最上面得一本。你可以...
队列（queue）
什么是队列？队列（queue）是一种数据结构，它的特点是只允许从队尾入队，从队列头部出队，满足先进先出的性质，即先进入队列的元素先出队列。可以把它理解为排队排在前一个人的后面。比如队列中依次有 1 5 7 9 2，插入元素 $3$ 后会变成 1 5 7 9 2 3，再插入元素 $5$ 后变成 1 5 7 9 2 3 5。此时出队，最先进入的 $1$ 会...
线性dp
对于线性动态规划，顾名思义指的就是根据题目内容可以得出线性相关的动态规划，如果书有序列（数组）那么状态就是一维的，如果是网格（棋盘）那么就是二维的。前文引例中的题目便是这种类型的。线性动态规划定义状态通常会考虑某类有序事件前面若干子事件的和 接下来我们给出例题 [HNOI2004] 打鼹鼠题目描述 鼹鼠是一种很喜欢挖洞的动物，但每过一定的时间，它还是喜...
动态规划（DP）的引入
动态规划并不是一段固定的模板，而是一种组织计算的方式：把原问题拆成若干个状态，先求出较小状态的答案，再利用它们得到更大的状态。 它解决的也不只是“求最大值”。最小代价、方案数量、能否到达，都可以使用动态规划。真正需要想清楚的只有几件事：状态表示什么、如何转移、从哪里开始，以及按照什么顺序计算。 从递归到动态规划先看一个很简单的问题：走上$n$级台阶，每...
宽度优先搜索（BFS）
前置知识注意 该算法的前置知识为队列（queue）,如果没有学习，请点击这里进行学习 BFS的介绍BFS（宽度优先搜索 Breadth-First Search）是一种用于图的遍历或搜索的算法。它从一个节点开始，逐层遍历图中的所有节点。BFS通常用队列来实现，因为它需要按照节点的发现顺序来访问它们。 工作原理BFS的工作原理可以总结为以下几个步骤 循...
深度优先搜索（DFS）
DFS的介绍DFS（深度优先搜索，Depth-First Search）是一种用于遍历或搜索树或图的算法。它从一个节点开始，尽可能深地搜索树的分支，直到到达叶子节点（没有子节点的节点），然后回溯到上一个节点，继续搜索其他分支。这个过程会一直进行，直到所有可能的分支都被探索完毕。 工作原理DFS的工作原理可以总结为以下几个步骤 选择一个起始节点：从树或...
