传送门 题目理解与强调 给定一个有向图,共有 $n$ 个点和 $m$ 条边,存在自环的情况,每条边的长度都为 $1$ 。与一般题目不同的是,每走一步会走过 $2^k$ 个单位长度( $k$ 为任意自然数),我们要找的是从点 $1$ 到点 $n$ 中所有路径中需要步数最少的一条。 题解 排除错误算法 第一个想到的方法一定是找到从 $1$ 到 $n$ …
Catalan数(卡特兰数) 实际问题 有 $2n$ 个人排成一行进入剧场。入场费 $5$ 元。其中只有 $n$ 个人有一张 $5$ 元钞票,另外 $n$ 人只有 $10$ 元钞票,剧院无其它钞票,问有多少种方法使得只要有 $10$ 元的人买票,售票处就有 $5$ 元的钞票找零? 一位大城市的律师在她住所以北 $n$ 个街区和以东 $n$ 个街区处…
传送门 题目强调与分析 翻译本题:给出一串长度为 $n$ 的字符串,其中只包含 "$B$" , "$R$" 两种字符,分别表示蓝色和红色,每一个字符还附有一个值,对于每次操作,你可以选择其中一个字符,对它的值进行以下两种修改: 如果颜色是红色,可以通过一次操作将它的值 $+1$ ;如果颜色是蓝色,可以通过一次操作将它的值 $-1$ ; 求:是否存在…
传送门 题目理解与强调 给定了一个长度为 $n$ 的序列,允许有 $k$ 次交换,每次可以在序列中交换任意两个数,输出其交换后子串可能的最大值。 题解 这道题是一个思维题,对算法要求低,只要你学会了语言,拥有思维能力就可以做出这道题。 首先分析一下,这题目是要求一个子串的最大值,数据范围又是 $1 \le n \le 200$ ,所以我们可以分别枚…
左偏树简介 左偏树是一种可并堆,也叫左偏堆、左倾堆、左氏堆,是一种树,具有堆的性质,可以实现快速合并。左偏树不是二叉搜索树,不是平衡树,因为它不满足中序有序性,无法进行二分搜索,因此不可以快速查找或者删除特定值的节点。 左偏树的性质 堆序性 节点的值大于或者等于(或小于等于)其左右子节点的值。对最大堆,父节点大,子节点小,每个结点的值都大于或者等于…
线性动态规划规划简介 在所有动态规划中,线性动态规划的难度最低,同时线性动态规划也是所有动态规划的基础。 顾名思义,线性动态规划就是说动态规划的过程在“一条线”上进行,状态转移只有一个方向。最常见的线性$\rm{DP}$有子集和问题,$\rm{LIS}$问题,$\rm{LCS}$问题,字段和问题等。其实,线性$\rm{DP}$的用处不只如此,很大一…
前言 先前博客中写过“线段树”这一篇文章,而这一次是一种具有新的含义的线段树:权值线段树。 权值线段树简介 定义 权值线段树和普通线段树的形态类似,但是含义不同。普通线段树的节点通常存储该区间的最值或者和值,其节点范围是一个区间:权值线段树的节点存储该值域内的元素个数,其节点范围是一个值域。 基本结构 如图,对于每个节点的位置表示的是元素的值,然后…
学习扫描线,你需要先学习线段树和离散化 扫描线简介 扫描线是一种求矩形面积并/周长的好方法,同样的,它可以延伸到很多地方。注意,扫描线并不是一条存在的线,是在解释算法时的帮助我们更好理解的线。 扫描线原理 现在在平面直角坐标系中有$n$个矩形,它们相互重叠在一起,求出所有矩形占有的面积(重叠部分只算一次)。如果采用暴力枚举每一个点,那么空间与时间都…
分治法简介 主要作用 在计算机科学中,分治法是建基于多项分支递归的一种很重要的算法范型。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础,如排序算法(归并排序、快速排序)、傅立叶变换(快速傅立叶变换)。 分治算法是一个解决…
二叉堆简介 二叉堆是一种基础数据结构,对于其他数据结构来说,支持的操作有限,也就插入,查询,删除这一类。 二叉堆的结构 从二叉堆的结构说起,它是一棵二叉树,并且是完全二叉树,每个结点中存在一个权值。堆性质:父亲的权值不小于儿子的权值(大根堆)。同样的,我们可以定义小根堆。本文以大根堆为例。由堆性质,树根存的是最大值。对于堆的每个子树,它同样也是一个…