【动态规划】背包 DP 学习笔记
背包问题是一类经典的可以使用动态规划解决的问题。先看以下几个动态规划基本模型： 0/1 背包问题 0/1 背包问题基本模型是：给定 nnn 个物品，每个物品有一个价值和一个体积，分别记作 wiw_iwi 和 viv_ivi，给定一个容量为 mm...
【数据结构】线段树（一） 学习笔记
线段树（一） 线段树是一种维护区间信息常用的树形数据结构。在全国青少年信息学奥林匹克竞赛大纲内难度评级为 6，是提高级中开始学习的数据结构。 本篇文章讨论的内容是线段树的基本结构与操作、线段树的延迟更新。 代码模板 代码模板-线段树 基本结构 ...
【动态规划】动态规划基础概念 学习笔记
动态规划可解问题的特点 如果一个问题可以通过动态规划求解，则这个问题一定（充分不必要）满足这两个特点： 最优子结构 动态规划可以解决的问题通常是求问题最优解的问题。且这种问题可被分割为多个子问题，子问题的解也是最优的。通过各个子问题的最优解可以逐...
【基础算法】二分 学习笔记
适用范围 两段性：在某个区间内，存在一个分界点，使得分界点一侧满足某性质，另一侧不满足 二分算法适用于具有“两段性”特征的问题，只要有高效的检验性质的方法，就可以在对数复杂度时间内求出分段点的位置。最基础的二分查找有对应 STL 的实现，根据处...
【图论】图的概念、存储和遍历 学习笔记
图的概念 从数据结构的角度看，图可以看作一个多对多的数据存储结构。而结合图论算法，图就可以成为很多问题的载体。图论是数据结构与算法结合的产物。 OI Wiki 上给出的图相关概念比较全面，但是因为 OI 是民科各个地方的一些定义都不太一样，所以作大...
【数据结构】树状数组 学习笔记
树状数组是一种基于二进制拆分的思想，用来动态维护序列的前缀和的树形数据结构。在全国青少年信息学奥林匹克竞赛大纲内难度评级为 6，是提高级中开始学习的数据结构。树状数组的基本操作：1. 修改序列中的一个数。2. 查询序列前缀和。 基本思想 树状数组是...
【数据结构】并查集 学习笔记
基础知识 并查集是一种树形数据结构。在全国青少年信息学奥林匹克系列竞赛大纲中难度为 6，是提高级中学习的数据结构。 并查集的基本操作： 查询一个元素在哪个集合。 合并两个集合。 使用一个森林来存储并查集，一个元素是一个结点，每棵树是一个集合。用...