day1学习 最后更新于 2025-05-01 19:42:46

今天是五一集训普及转提高的第一天，我们学习了一些有关 __数据结构__ 的内容，我认为难度逐渐提升，正好适合我的节奏。 我听懂了这些内容： 1. __线性数据结构__ ：他们具有不同的功能。双向队列像一个没有限制，只能从头尾进出的管子；栈类似于一个手枪的弹夹，只能从顶上的开口接纳及吐出东西；单调队列基于双向队列实现，他保证队列的东西严格单调递增|递减，队列是一种简易的打水队伍。数组是最基本的数据结构。链表是一个一个单元依靠指针链接而成的。有关线性数据结构的问题我听懂并独立完成了这些：模板队列，模板栈，单调队列。 3. __非线性数据结构__ ：他们不是线性的，我们知道了 __并查集__ ，我将其理解成了一些亲戚朋友认亲戚；我了解了 __分块__ ，他可以类似于线段树，但具有更优秀的功能与稍微劣势的复杂度。从分块我们引出了一种暴力的算法即莫队算法。我们还了解了 __Trie 字典树__ 。一种队列虽然有队列的名字，但他 __不是__ 线性数据结构，这就是优先队列，我们将其当堆使用。一般他是大根堆，但是将数字全部取相反数存入取出可以简易的实现小根堆。我完成了这些题：模板优先队列，模板并查集，彩色木棍三角形。 他们用在哪里呢？ 数据结构与算法相结合，形成了OI的绝大部分。我们将栈应用在深度优先搜索中，队列使用在广度优先搜索中，双向队列用于既需要实现栈也需要实现队列的一些犄角旮旯及实现一种单调队列解决区间问题。并查集在图论中可以判断是否有环，还能做出许多的事情，优先队列（我不习惯叫他堆）常常用于与图相关的一些问题，本质上还是一颗二叉树，字典树顾名思义会在大量的字符串题中遇见，分块应用于一些需要分而治之的问题里，逆序对也应用到了分治的知识。 第二天，我们预计将要学习线段树，我们必须知道树状数组，线段树与分块要用在哪里，怎么应用。 总的来说，我们必须学会怎么实现数据结构，及其对应的应用方法。 实例代码：没有，做题去了。 听懂一天 __不是__ 永远听懂，我们需要继续巩固，多刷题多练习。 实在不太会用Markdown啊！