1644专题

AcWing 1644. 二叉树中的最低公共祖先 题解 线性dp 倍增算法 前序中序构造二叉树

二叉树中的最低公共祖先 题目描述 树中两个结点 U 和 V 的最低公共祖先(LCA)是指同时具有 U 和 V 作为后代的最深结点。给定二叉树中的任何两个结点,请你找到它们的 LCA。 输入描述 第一行包含两个整数 M 和 N ,分别表示询问结点对数以及二叉树中的结点数量。 接下来两行,每行包含 N 个不同的整数,分别表示二叉树的中序和前序遍历。保证二叉树可由给定遍历序列唯一确定。 接下来

bzoj 1644: Obstacle Course 障碍训练课 BFS

Description 考虑一个 N x N (1 <= N <= 100)的有1个个方格组成的正方形牧场。有些方格是奶牛们不能踏上的,它们被标记为了'x'。例如下图: . . B x . . x x A . . . . x . . x . . . . . x . . 贝茜发现自己恰好在点A处,她想去B处的盐块舔盐。缓慢而且笨拙的动物,比如奶牛,十分讨厌转弯。尽管如此,当然在必要的时候她