leetcode 第 364 场算法比赛

零、背景

这次比赛第二题和第三题竟然完全一样。
最后一题又是经典的树形 DP。

一、最大二进制奇数

题意：给一个二进制字符串，问打乱二进制顺序，求可以构造的最大奇数二进制。

思路1：排序，将最后一个 1 与最后一个 0 交换。
复杂度：O(n log(n))

思路2：统计 1 的个数，前面少填充一个 1，最后放一个 1。
复杂度：O(n)

二、美丽塔 I

题意：给一个数组各下标的最大值，求构造一个山状数组，使得数组和最大。
山状数组：存在一个坐标为最大值，前后方向都呈现递减。

思路：数据访问不大，枚举。
枚举最大值坐标，前后方向贪心为保持递减性质后的最大值。
复杂度：O(n log(n))

三、美丽塔 II

题意：给一个数组各下标的最大值，求构造一个山状数组，使得数组和最大。
山状数组：存在一个坐标为最大值，前后方向都呈现递减。

思路：与第二题题意完全相同，数据范围为 10^5。

面对这个数据量，优化思路显然是预处理出每个位置为山峰时左边的前缀和与后面的后缀和，然后左右求和。
所以问题就转化为了，如何预处理，求出前缀每个位置为山峰时的前缀和。

山峰有一个性质：有序，即具备单调性。
所以这个可以使用单调性来优化。

假设上一个位置为山峰的前缀和已经求出来了。
如果当前位置大于等于上个位置，则当前位置加上上个位置的答案，就是当前位置的答案。

如果当前位置小于上个位置，则上个位置多余出来的部分后面永远都用不到了。
所以我们可以记录前面连续都大于等于当前位置的最远距离，这个区间的山峰高度都需要等于当前位置。

假设当前位置为 i, 第一个小于当前位置的下标为 p
则当前位置的答案为：sum[i]=sum[p] + val[i] * (p - i)

怎么快速找到 p 呢？
维护一个单调栈即可。

复杂度：O(n)

四、统计树中的合法路径数目

题意：给一个无根树，问有多少路径，路径中只有一个节点的值是素数。

思路：典型的树状DP。

树状DP的核心思路是基于有根树，递归处理每个有子根树。

对于一个有根树，有三个原则。

原则1：当前函数只处理当前子树内经过当前根的路径。
原则2：子树中的路径由子树复杂计算。
原则3：经过当前根到达父节点的路径，由祖先去处理计算，这里只预处理祖先需要的子树内的若干信息。

基于这三个原则，可以将经过根的路径分四种情况。

情况1：根是素数，求以根为路径一个端点的路径数。
情况2：根是素数，求经过根的路径数。
情况3：根不是素数，求以根为一个端点的路径数。
情况4：根不是素数，求经过根的路径数。

对于情况1，根节点是素数和一个端点，另一个端点显然在子树中。
此时，我们需要找到子树中所有以子树根为起始位置的路径，且路径上都没有素数。
由此，我们也可以推导出子树需要预处理的一个信息：以当前根节点为起始位置的路径，且路径上都没有素数的个数，记为 emptyChild[i]。

对于情况2，根是素数，但是根不是端点，路径经过根。
此时，我们需要所有子树对(i,j)，其中子树对的答案是emptyChild[i] * emptyChild[j]。

假设子数有 M 个，则子数对有 C(M,2)个，按组合一个个计算显然会超时。
我们进行公式转化，可以转化为其中一个子树与其他子树的答案。
即 emptyChild[i] * sum(otherChild[j])

当然，这样选择时，子树对会被重复计算一次，所以最终答案需要除2。

对于情况3，根不是素数，求以根为端点的路径数。
显然，我们需要找到子树中所有以子树根为起始位置的路径，且路径上只有一个素数。
由此，我们也可以推导出子树需要预处理的另一个信息：以当前根节点为起始位置的路径，且路径上只有一个素数，记为 prmChild[i]。

对于情况4，根不是素数，但是路径经过根。
此时，需要找到所有的子树对[i,j)，其中素数在子树i中，则答案为prmChild[i] * emptyChild[j]。
同样，这种情况与情况2类似，可以使用子数和优化，由于这里子树对是有序的，所以不存在重复计算问题。

复杂度：O(n)

五、最后

这次比赛第三题单调性优化，第四题树状DP 还是有难度的，尤其是树状DP，大家可以多加练习，很实用的。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code