Texcavator 的秘密基地

定义什么是最近公共祖先？ 在一棵树中（也就是有向无环图中），从根结点遍历到每个结点，路径上所经过的所有结点都叫做该结点的祖先结点 两个结点的祖先结点中重复的部分叫做公共祖先 公共祖先中层数最大的一个点叫做最近公共祖先（LCA） 求法向上标记法要求的两个结点依次向上遍历，找到的第一个公共祖先就是最近公共祖先 但是这个做法比较暴力，时间复杂度O(n) 倍增法首先需要预处理f[i][j]：从结点 i 向上走 2^j^ 步走到的结点，j 的范围是0 <= j <= logn比如说，当 j = 0 时，f[i][j]表示的就是 i 向上走一步到达的结点，其实也就是 i 的父结点 （如果从 i 开始跳 2^j^ 跳出了根结点，那么规定f[i][j] = 0且dist[0] = 0） 怎么实现这个算法呢？ 我们发现，从结点 i 向上走 2^j^ 步，相当于结点 i 先向上走 2 ^j-1^ 步，再向上走 2 ^j-1^ 步据此，我们可以利用递归来解决这个问题 用式子可以表示为：f[i][j] = f[f[i][j - 1]][j - 1] 然后，我们需要预处理另一个数组depth[i]： ...

双向BFS和前面的双向DFS思路基本一样，都是为了从两端搜索从而避免搜索中间一大块复杂的情况 送礼物原题链接 达达帮翰翰给女生送礼物，翰翰一共准备了 $N$ 个礼物，其中第 i 个礼物的重量是 $G[i]$。 达达的力气很大，他一次可以搬动重量之和不超过 $W$ 的任意多个物品。 达达希望一次搬掉尽量重的一些物品，请你告诉达达在他的力气范围内一次性能搬动的最大重量是多少。 输入格式 第一行两个整数，分别代表 $W$ 和 $N$。 以后 $N$ 行，每行一个正整数表示 $G[i]$。 输出格式 仅一个整数，表示达达在他的力气范围内一次性能搬动的最大重量。 数据范围 $1 ≤ N ≤ 46,$$1 ≤ W , G[i] ≤ 2^{31}−1$ 输入样例20 5754181输出样例19 题意给出背包体积和每个物品体积，问一次最多装多少物品 思路看数据范围判断背包问题一定会TLE，但N范围比较小，因此使用爆搜，把所有可能方案枚举一遍，取一个最大值但是直接爆搜，时间复杂度 2^46^，也是会超时的 优化——双向DFS 用空间换时间先枚举前一半数能凑出来的集合，再枚举后一半数，然后在两个集合中分别 ...

剪枝是什么意思呢？ 我们知道，不管是内部搜索还是外部搜索，都可以形成一棵搜索树，如果将搜索树全部遍历一遍，效率会很低，但如果我们能在搜索的过程中，提前预知，判断某一些不可能是正确答案的情况，就可以不用遍历其下的子树，从而提高我们的算法效率 我们可以从以下几个角度考虑剪枝： 优化搜索顺序优先选择分支较少的结点 排除等效冗余尽量保证不搜索重复的状态（就是在不考虑顺序时，采用组合的方式搜索） 可行性剪枝不合法提前退出 最优性剪枝如果当前答案无论如何都比目前的最优解要差，那就可以不要往下搜了 记忆化搜索（DP） 接下来将通过例题来讲解 小猫爬山原题链接 翰翰和达达饲养了 N 只小猫，这天，小猫们要去爬山。 经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了（呜咕>_<）。 翰翰和达达只好花钱让它们坐索道下山。 索道上的缆车最大承重量为 W，而 N 只小猫的重量分别是 C1、C2……CN。 当然，每辆缆车上的小猫的重量之和不能超过 W。 每租用一辆缆车，翰翰和达达就要付 1 美元，所以他们想知道，最少需要付多少美元才能把这 N 只小猫都运送下山？ 输入格式 ...

DFS 的搜索分为两大部分： 内部搜索：一个图中从一个点搜到另一个点 外部搜索：从一张图（状态）搜到另一张图（状态） 在第一个部分里是图内部点的搜索，每个点只能搜一次，因此搜过的点不需要恢复到原来的（还没被搜过的）状态（意思就是st数组不恢复） 而第二个部分是点的集合之间的搜索，每次搜索完一定要恢复到原有状态才可以进行下一步搜索（意思就是st数组每次需要恢复原状） 迷宫原题链接 一天Extense在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由 n∗n 的格点组成，每个格点只有2种状态，.和#，前者表示可以通行后者表示不能通行。 同时当Extense处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Extense想要从点A走到点B，问在不走出迷宫的情况下能不能办到。 如果起点或者终点有一个不能通行(为#)，则看成无法办到。 注意：A、B不一定是两个不同的点。 输入格式 第1行是测试数据的组数 k，后面跟着 k 组输入。 每组测试数据的第1行是一个正整数 n，表示迷宫的规模是 n∗n 的。 接下来是一个 n∗n 的矩阵，矩阵中的元素为.或者#。 ...

BFS可以解决边权为1的最短路问题，下面是相关例题 单源最短路将源点在开始时存进队列 迷宫问题原题链接 给定一个 n×n 的二维数组，如下所示：int maze[5][5] = {0, 1, 0, 0, 0,0, 1, 0, 1, 0,0, 0, 0, 0, 0,0, 1, 1, 1, 0,0, 0, 0, 1, 0,};它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。 数据保证至少存在一条从左上角走到右下角的路径。 输入格式 第一行包含整数 n。 接下来 n 行，每行包含 n 个整数 0 或 1，表示迷宫。 输出格式 输出从左上角到右下角的最短路线，如果答案不唯一，输出任意一条路径均可。 按顺序，每行输出一个路径中经过的单元格的坐标，左上角坐标为 (0,0)，右下角坐标为 (n−1,n−1)。 数据范围 0 ≤ n ≤ 1000 输入样例50 1 0 0 00 1 0 1 00 0 0 0 00 1 1 1 00 0 0 1 0输出样例0 01 02 02 12 22 32 43 44 ...