牛客周赛64题解

A 小红的对错判断

把所有字符都转换成大写形态，将字符串与 $YES$ 比较。
参考代码

B 小红的幂表达

从大到小枚举底数 $k$ ，求出对数 $m=log_k(n)$ 。
如果有 $k^m=n$ ，输出之。
由于底数从大到小枚举，幂次会是递增的。
对于求对数的环节，计算机并没有对每个 $k$ 都有 $log_k$ 函数。
所以我们使用换底公式 $log_k(n)=log_2(n)/log_2(k)$ 。
参考代码

C 小红的前缀询问

使用 dict 维护当前位置 $i$ 之前，有多少个元素等于 $a_i$ 。
设 $d$ 是存放元素数量的 dict，则第 $i$ 个位置的贡献为 $d_{a_i}$ 。
我们记这个贡献为 $b_i$ ，则前缀 $[1,i]$ 的贡献和为 $\sum_{j=1}^i b_j$ 。
在此基础上，对数组 $b$ 做前缀和，即可快速求解区间之和。
参考代码

D 小红和小紫的博弈游戏

考虑四种组合 $(a,b)$ , $(a,c)$ , $(b,d)$ , $(c,d)$ 。
如果没得取，只有两种可能， $a %2B d = 0$ ，或者 $b %2B c = 0$ 。
既然是最优策略，那么都会取最小的那个。
参考代码

E 小红的字符串重排

首先想到一个 trick ，最大的同种字符数量 $m$ 与 $n/2$ 的关系。
这题要求每个位置都不能放原来的字符，所以需要满足 $m \cdot 2 \gt n$ 。
如果满足，我们考虑字符集整体偏移 $m$ 个长度。
首先，构造一个长度为 $n$ 的二元组数组，每个二元组的 first 存放字符，second 存放下标。
然后，按照字符大小进行排序，从小到大或者从大到小都行，这里是为了让同样字符放到一块去。
然后，构造一个存目标字符的数组 $ans$ ，对于每个二元组，将偏移过后字符放入新的下标。
最终，将字符数组转换为字符串，输出。
参考代码

F 小红的树上路径查询（easy）

由于 $q=1$ ，我们可以考虑时间复杂度为 $O(q \cdot n)$ 的算法。
定义 $xy$ 为 $x$ 到 $y$ 的路径，那么我们需要找出 $xy$ 上所有的点，并且求出其他点到 $xy$ 的最短距离。
现在大问题变成了两个小问题。
1.找出路径上的点。
假设点 $u$ 在路径上，那么从 $x$ 到 $y$ 的路程中，必然经过点 $u$ ，则有 $len(xu) + len(uy) = len(xy)$ 。
注意到，这些边都是无向边，有 $len(uy)=len(yu)$ 。
那么上式可转换为 $len(xu) + len(yu) = len(xy)$ 。
$xu$ 是 $x$ 到 $u$ 的距离， $yu$ 是 $y$ 到 $u$ 的距离。
那么，只要把 $x$ 当作起点，做一次 bfs ，即可得知 $x$ 到其他点的最短距离， $y$ 同理。
做完两次 bfs ，分别得到每个点与 $x,y$ 的距离数组 $disX,disY$ 。
如果点 $u$ 有 $disX_u + disY_u = len(xy)$ ，那么 $u$ 就是在路径上的点。
2.求出其他点到 $xy$ 的距离。
假设有极端情况，一半的点在路径上，另一半不在。
对所有在路径上的点，分别做一次bfs，然后对每一个非路径点，比较得出最小值，求和。
时间复杂度达到了惊人的 $O(q \cdot n^2 )$ ，不可取。
那么多次 bfs ，我们是否能只做一次 bfs 呢？
你别说，还真有。
我们创建一个虚拟源点（也叫超级源点），连接它和路径上的所有点，边权为 $0$ 。
这个源点就是只用做一次 bfs 的起点，它将时间复杂度降到了 $O(q \cdot n)$ 。
在代码实现时，我们不需要真的创建这个点，以及对应的 $0$ 边。
只需要在初始化队列时，把路径上面的点都扔进去就好（普通bfs只会扔一个点进去）。
bfs 结束之后，把距离数组的值全部加起来，输出。
参考代码

G 小红的树上路径查询（hard）

hard version 的 $n,q \in [1,10^5]$ ，显然 $O(q \cdot n)$ 的做法也倒闭了。。。
让我们重新审视点与路径的关系。
点在路径上的情况，已于 F 题解中说明。
那么，点不在路径上的情况呢？
假设点 $v$ 不在路径上，离它最近且在路径上的点是 $u$ 。
路径的两端仍然是 $x$ 和 $y$ 。
那么，从 $v$ 到 $x$ 或者从 $v$ 到 $y$ 的路程中，必然经过点 $u$ 。
所以有如下推导：
$\ \ \ \ len(vx) + len(vy)$
$=(len(vu) + len(ux)) + (len(vu) + len(uy))$
$=2 \cdot len(vu) + (len(ux) + len(uy))$
$=2 \cdot len(vu) + len(xy)$
对于在路径上的点，代入上式，也是正确的。
因为此时 $v=u$ ， $len(vu)=0$ 。
所以，对于给定的所有点，都满足上式。
有同学会问，我们知道这个有什么用吗？
别急，我们来反推一波。
我们想求的是全部的 $len(vu)$ 之和，注意，这里并不需要求出具体的 $u$ 。
根据上式，移项可得 $len(vu)=(len(vx) + len(vy) - len(xy))/2$ 。
对所有 $v$ 的求和为：
$\ \ \ \ \sum_{v=1}^{n} (len(vx) + len(vy) + len(xy))/2$
$=(\sum_{v=1}^{n} len(vx) + \sum_{v=1}^{n} len(vy) - n \cdot len(xy))/2$
$=(\sum_{v=1}^{n} len(xv) + \sum_{v=1}^{n} len(yv) - n \cdot len(xy))/2$
相信大家已经看出来了
$\sum_{v=1}^{n} len(xv)$ 是点 $x$ 到所有点的距离之和。
$\sum_{v=1}^{n} len(yv)$ 是点 $y$ 到所有点的距离之和。
$len(xy)$ 是点 $x$ 到点 $y$ 的路径长度。
大问题又变成了两个小问题。
$\sum_{v=1}^{n} len(xv)$ 和 $\sum_{v=1}^{n} len(yv)$ 可以使用换根dp 维护。
$len(xy)$ 可以使用 LCA 维护。
对于具体算法，不在此处赘述。
对于单次询问的时间复杂度，换根dp 的复杂度是 $O(1)$ ，LCA 的复杂度是 $O(log(n))$ ，总复杂度是 $O(q \cdot log(n))$ 。
需要注意的是，python 在递归上的效率奇差，需要使用栈来替代递归。
参考代码