题解大杂烩（一）

镇楼图是我为自己开发的一个小工具，可以登记已经解决的题目、设置复习计划和记录笔记等。它的亮点在于，能够根据解题时间、尝试次数等指标，得出某道题的综合难度分数，根据这个分数赋予相应的复习优先级，帮助我更加高效地完成复习流程。
目前这个工具是基于 CLI 的，我打算之后空下来了把它迁移到 web 上去（比如用 nextjs），然后开源给所有人使用，顺便增加一些新功能，比如图表显示和记忆曲线拟合之类的，不过那是后话了。

1. 洛谷 - P11968 「ALFR Round 7」T1 二进制与一 II
>>> 题面：

>>> 题解：
基本思路是想办法构造出与 x 最接近的两个 "二进制表示下恰好有 k 位为 1" 的数，那么它们与 x 的差的绝对值的最小值即为最终答案。
问题在于怎么构造。
我们可以利用类似 next permutation 的方法，从 (1 << k) - 1 开始不断地求出下一个满足 "二进制表示下恰好有 k 位为 1" 条件的数。然而在极端情况下，这样的数可能有 C(60,30) = 118264581564861424 个，即便用最高效的实现 Gosper's Hack，也无法在时间限制下得到答案。
因此，需要使用别的办法。
我们知道，康托展开可以实现全排列到自然数的双射，而本题涉及的是组合，尽管它和排列并不相同，但依然可以用类似的思路进行映射。
所以，一种做法是二分查找映射后的自然数（rank），根据 rank 构造出对应的满足 "二进制表示下恰好有 k 位为 1" 条件的数，判断与 x 的大小关系，进而找到最接近 x 的两个数。
>>> 提交记录：

>>> 代码：

2. 力扣 - 31. Next Permutation
>>> 题面：

>>> 题解：
对于排列来说，越靠前（左）的数越能决定这个排列在所有排列中的名次，这是因为字典序是从左到右比较的。那么，要想求出下一个排列，我们要修改的元素必须尽可能地靠右。
不妨从右往左考虑，对于排列的某个后缀，如果该后缀是不上升的，那么如果交换该后缀中的任意两个元素，所得到的新排列都会比原来的排列的名次更靠前，如 12543 -> 12534，不符合题目要求。反过来，我们可以选择第一个（最靠右的）破坏不上升性质的元素 x 作为交换对象之一，把它和不上升后缀中的某个元素交换，来得到名次更靠后的排列。
那么，应该选择后缀中的哪个元素呢？恰好大于 x 的那个元素，记作 y。
为什么？如果选择更小的元素交换，那么得到的排列名次会更靠前，不符合题目要求；如果选择更大的元素交换，那么得到的排列名次肯定比和 y 交换后的要更大，同样不符合题目要求。
交换之后，不难发现，后缀依然是不上升的，所以只需要反转后缀，就能使新排列的名次最小且大于原先排列，也就是题目所求的 "下一个排列"。
>>> 提交记录：

>>> 代码：

3. 力扣 - 2588. Count the Number of Beautiful Subarrays
>>> 题面：

>>> 题解：
每次操作都必须消除两个 1，因此每一位上 1 的个数必须是偶数。
假设数组中只有 0 和 1，不妨用前缀和的思想来解决本题。
统计前缀中 1 的个数，如果它是奇数，为了方便，称此时的前缀为 “奇前缀”。
那么，从该奇前缀中去掉任何奇前缀，得到的子数组中的 1 的个数一定是偶数。
反之，如果是偶前缀，那么从中掉任何偶前缀，得到的子数组中的 1 的个数也一定是偶数。
注意到，我们并不需要记录 1 的个数到底有多少个，只需要知道它是奇数还是偶数。
可以用前缀异或和来编码前缀中 1 的个数的奇偶性，并进一步推广至元素为任意整数的情况。
因为每一位都是独立的，所以前缀异或和的做法依然正确。
>>> 提交记录：

>>> 代码：

4. 力扣 - 938. Range Sum of BST
>>> 题面：

>>> 题解：
虽然是一道简单题，但仔细想想却很有意思，这也是为什么我会把它纳入复习清单。
暴力做法是遍历所有的结点，然后将处于 [low, high] 区间内的结点值累加到最终答案起来。
然而，这样做没有利用好输入是 BST 的条件。
我们可以根据当前结点的值和目标区间的关系，判断是否有必要继续遍历当前结点的左孩子和右孩子，以减少访问的结点数量。
我第一次做这道题的时候，显式地下传了当前子树的值域，类似线段树的 query。
但后来发现并没有这样做的必要。只需要判断查询区间和当前结点存储的值的关系即可。
当时做的时候，在这里卡了好久。我一直想不明白，它和线段树这么像，却又不一样。为什么？
经过思考，我得到了一个令自己较为满意的答案：
本题的写法和线段树的 query 极为相似——当前结点存储的值 x 可以理解为线段树 query 中的 mid。线段树 query 之所以需要维护当前子树的区间，是因为每个结点都对应一段区间，我们必须通过当前区间来判断它是否对查询区间有贡献。
而本题并不需要，这是因为本题中的结点存储的只是一个值。
从本质上看，在线段树的 query 中，我们将查询区间分割成了线段树所维护的多段区间，然而在本题中，我们并没有做区间分割，只是利用有序性质排除掉了那些绝对无法满足查询区间限制的子树。
这样就合理多了。
>>> 提交记录：

>>> 代码：

5. 力扣 - 907. Sum of Subarray Minimums
>>> 题面：

>>> 题解：
单调栈模板题。
考虑贡献法，即，计算出每个最小值总共对多少个子数组产生了贡献。为此，对于当前考虑的元素 x，我们需要找到前一个大于 x 的元素和后一个大于等于 x 的元素（或者前一个大于等于 x 的元素和后一个大于 x 的元素），之所以引入等号是为了防止重复统计，因为对于拥有多个相同最小值的子数组，该最小值只能被计入一次。
可以使用单调栈来找到我们需要的元素。
>>> 提交记录：

>>> 代码：

今日复习完成。

6. 洛谷 - P12247 跳舞机
>>> 题面：

>>> 题解：
首先，不难看出这道题的基本模型是 partition dp （这部分没什么好说的，纯粹是经验积累，如果之前接触过相关的内容就能很快看出来）。
定义 dp[i] 为前 i 分钟所能取得的最大兴奋值。
因为一局游戏的时间是固定的 k 分钟，对于第 i - k + 1 到第 i 分钟在电 v♂an 城的玩家，贪心地思考，我们应当选择能够产生最大兴奋值的那个玩家。
剩下的问题是，如何高效找到这一时间段能够产生最大兴奋值的那个玩家。
这是一个经典的扫描线问题，具体细节不在此赘述。
>>> 提交记录：

>>> 代码：

7. Codeforces - 474F. Ant colony
>>> 题面：

>>> 题解：
题目要求我们计算出查询区间内被吃掉的蚂蚁的数量。
反过来，我们可以计算没有被吃掉的蚂蚁的数量。
对于没有被吃掉的蚂蚁，它的力量 x 必须是该区间内其他所有蚂蚁的力量的公因数。
我们知道，cd(a, b, c, ...) <= min(a, b, c, ...)，这里 cd 代表公因数（common divisor）。
等号并不一定能取到，不过一旦取到了，那么 cd(a, b, c, ...) 一定是 gcd(a, b, c, ...)。
因此，x 必须小于等于区间内所有蚂蚁的力量，也就是说，x 小于等于区间最小值。因此，若 x 存在，则它必定是唯一的，且等于该区间的最小元素值。
同时根据上面的分析，我们知道 x 也是该区间所有元素的最大公因数。
所以，我们可以利用 st 表维护区间 gcd 的值。每次查询时，先通过 st 表找到当前区间的 gcd 值 x，再用二分查找确定当前区间内等于 x 的元素数量 y，用区间长度减去 y，即为当前查询的答案。
>>> 提交记录：

>>> 代码：

8. 力扣 - 1399. Count Largest Group
超时。花费 30 分钟解决。
写数位 DP 的时候，把 dfs 中表示当前数位下标的变量 i 和 for 循环变量 i 搞混了，debug 了好久。
>>> 题面：

>>> 题解：
本题因为数据范围较小 (1e4)，可以直接暴力，但这里提供的解法适用于更一般的情况，即便 n = 1e18 也能瞬间完成计算。
基本思想是数位 DP。我们遍历数位和的所有可能情况，利用数位 DP 统计当前情况的整数个数，然后根据题目要求找到最大的 group。
数位 DP 在大部分情况下都是非常公式化的，这里不加赘述。
>>> 提交记录：

>>> 代码：

9. 力扣 - 98. Validate Binary Search Tree
>>> 题面：给你一棵二叉树，验证它是否为二叉搜索树。
>>> 题解：
方法有很多，比如前序遍历下传区间，中序遍历判断访问序列是否严格升序，后序遍历维护左子树最大值和右子树最小值等等。这里使用（个人认为）最简单的中序遍历来实现。
每次访问到新节点（非空）时，都判断它是否大于前一个节点的值 prev，如果是则将 prev 更新为当前节点的值，否则 return false。
>>> 提交记录：

>>> 代码：

10. 力扣 - 295. Find Median from Data Stream
>>> 题面：给你一个数组，你可以动态地向里面添加元素，求出每次添加之后的中位数。
>>> 题解：
对顶堆模板题。
维护两个堆（优先队列）left 和 right，分别代表当前数组中最小的 floor(n / 2) 个元素和当前数组中最大的 ceil(n / 2) 个元素，可知前者应该使用最大堆，后者应该使用最小堆。
为了在添加元素后依然保证这两个堆符合最初的定义，需要根据两个堆的 size 以及所添加的元素 x 和两个堆各自的堆顶元素之间的大小关系来分类讨论。
假设现在两个堆的 size 相等，那么在添加元素 x 之后，right 的 size 应当比 left 大 1。
假设 left 堆顶元素为 a，right 堆顶元素为 b，根据定义有 a <= b。
如果 x < a，那么它应该被插入到 left 里面去，同时 left 弹出一个元素给 b；
如果 x >= a，那么它可以直接被插入到 right 里面去。
实际上，我们并不需要显式地讨论元素的大小关系，完全可以将这两种情况统一起来，直接往 left 里面插入 x，然后把 left 的堆顶弹出放到 b 里面。
另外一种情况（在插入之前 right 的 size 就比 left 大 1，即此时数组的 size 是奇数）也同理。
>>> 提交记录：

>>> 代码：

今日复习完成。

感觉提交记录没必要发上来，所以从今天开始就不贴提交记录了。
11. 力扣 - 111. Minimum Depth of Binary Tree
>>> 题面：给定二叉树，求它的最小深度。
>>> 题解：对于以当前结点构成的子树，分别求出左子树和右子树的最小深度，取它们中的最小值 + 1 作为当前子树的最小深度上传给父结点。这里需要注意的是，为了简化代码，通常我们会在访问到空结点时返回 0，在本题也是如此，但还要进行一些额外处理。
上述算法基于这一事实：树的最小（最大）高度等于其最小（最大）深度。然而，在访问到空结点时直接返回 0 并不能保证所得到的高度是合法的。如果某个结点只有一个孩子，那么它的高度至少是 2，而不应该是 1。
>>> 代码：