传送门 题目理解与强调 给定一个有向图，共有 $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$个矩形，它们相互重叠在一起，求出所有矩形占有的面积（重叠部分只算一次）。如果采用暴力枚举每一个点，那么空间与时间都…

分治法简介 主要作用 在计算机科学中，分治法是建基于多项分支递归的一种很重要的算法范型。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法（归并排序、快速排序）、傅立叶变换（快速傅立叶变换）。 分治算法是一个解决…

二叉堆简介 二叉堆是一种基础数据结构，对于其他数据结构来说，支持的操作有限，也就插入，查询，删除这一类。 二叉堆的结构 从二叉堆的结构说起，它是一棵二叉树，并且是完全二叉树，每个结点中存在一个权值。堆性质：父亲的权值不小于儿子的权值（大根堆）。同样的，我们可以定义小根堆。本文以大根堆为例。由堆性质，树根存的是最大值。对于堆的每个子树，它同样也是一个…