牛客练习赛103题解

牛客练习赛103题解

A题:

首先:三步以内一定可以得到 0 。

其次:一步想要得到 0 当且仅当 a,b,c 中有两个数相等。

最后:如果两步可以得到 0 当且仅当第一步后有两个数可以相等,这里直接枚举就好了。

时间复杂度:O(T)

B题:

把集合中的数排序后从左到右连在一起,此时树的权值就是最小的(即最大权值和最小权值的差)。

在权值不变的情况下使得树的最长树链最短,所以构造一条树链,使得每种权值都在树链中出现一次且是单调排列的,那么其它的点就可以直接连接在树链上即可。

此时情况有两种:一种是树中结点个数不足三个那么最长树链的长度就是结点个数。否则最长树链长度就是权值的种类数,若最小值有重复元素则长度加一,若最大值有重复元素则长度再加一。

时间复杂度:O(n * logn)

C题:

由于光标只会向前移动,所以每个字符最多被遍历两遍,直接模拟即可。

利用 STL 可以简化代码。
时间复杂度:O(len),其中 len 代表的是所有字符串长度的和。
PS:可以单独维护块,例如标程维护的就是循环节,这样时间复杂度是 O(len / 64 + m) 的。

D题:

特征:对于每种颜色,其能覆盖的范围是由所有颜色等于它的点的横纵坐标的最大值和最小值所界定的一个矩形。

所以将每种颜色的 x,y 坐标分别用一个可重集合存起来,就可以动态的修改每一种颜色所有点的横纵最大最小值。

原题转换成:给定一堆矩形,每次修改某两个矩形或者查询一个点是否被矩形所覆盖,这里可以用二维树状数组来维护。

时间复杂度:O((10^6+Q) * logn * logm)

E题:

先考虑只有 A,B 的情况,那么直接进行多源搜索就确定找到最终 B 被抓的时间了。但是可能会有多个点使得 B 可以尽量晚的被抓住,这时由于 B 要使得 C 也尽可能晚的被抓住,而若一个点一个点的验证,那么时间复杂度是 O(n^2) 的。

下面证明 B 对于最晚被抓住的点的选择对 C 并没有影响。如下图,假设 A 当前在 1 结点,B 当前在 2 结点,5,6 结点都是 B 尽可能晚被抓住的结点。

情况一:假设 C 不处于 2 结点的子树中,且 C 的最优解也不在 2 的子树中,那么无论 B 的选择是 5,6 中的哪一个都不会影响 C 的选择。

情况二:假设 C 不处于 2 结点的子树中,而 C 的最优解也处在 2 的子树中,那么实际上影响 C 能不能到最优解的要求就是 C 能不能通过结点 2 。而结点 2 到结点 5,6 的距离是相同的,所以无论选择 5,6 中的哪一个,对 C 的影响是相同的。

情况三:假设 C 处于 2 结点中,那么无论如何 C 结点都是可以到达 2 结点的,所以此时 B 的选择仍然无关紧要。

综上所述,只需要进行两次 bfs 操作即可知道 B,C 最晚被抓住的时间了。

时间复杂度:O(n)。

F题:

此题是上一题的加强版,先考虑没有禁锢时间的限制时怎么解决。若没有时间限制,那么根据上一题的证明,这里每一步要做的就是找到机器人和被抓虫子的位置,然后找到最晚被抓点即可。机器人的行动是可以预测的,那么作为被抓的虫子,应该分为两步,先向机器人的方向走到极限,然后在剩下的不含机器人的方向选一条最远路就可以了。这里的第一步可以通过 st表 解决,第二步则可以通过 二次换根扫描dp 预处理出最优和次优值。

下面说明有禁锢时间限制的影响。如下图,假设机器人在位置 1 被抓虫子在位置 2 (省略了相向而行的部分),5,6 分别是 2 的两个最优选择(最晚被抓住的点),而下一个要被抓住的虫子在结点 7。这里,情况一和情况二都不变,我们重新分析情况三。

image-202209151****7009

若禁锢时间够短,下一个被抓的虫子可以到达结点 2 那么根据上一题的分析,当前被抓的虫子选 5,6 中哪一个都不会对答案产生影响。

若禁锢时间够长,下一个被抓的虫子没法走到结点 2 那么下一个被抓的虫子肯定也无法走到结点 6 和结点 7 的公共祖先处,而为了使下一个被抓的虫子的选择尽可能的多,那么当前被抓的虫子必然会选择一个离下一个被抓的虫子尽可能远的点(也就是图中的结点 5)。

分析几种情况后对于 换根dp 中维护的信息应该是对两个最值维护 4 种可能的结点路径即可,由于要维护的结点互相之间尽可能的远,所以要分两次更新信息(每次每颗子树更新一次信息)。

总时间复杂度:O((n+m) * logn)

G题:

对于问题的第一问,可以将每个骑士编号,然后逐层 bfs 扩展,直到可以封锁魔王的路为止,这里可以用二分或者并查集来解决。

对于问题的第二问,首先将原图拓展对应步数,然后从左下向右上进行一轮 01bfs 即可。

上文提到的 01bfs 和 并查集 的方法是基于一个结论,那就是如果能够封锁魔王的路,那么必然存在一条有骑士占领点和城墙组成的通路可以从左下走到右上(这里是八联通的情况)。

时间复杂度:O(n * m) 。

注:二分加迪杰斯特拉算法可能会被卡常。

全部评论
D题用二维线段树过不了时限不能开大点吗
点赞 回复
分享
发布于 2022-09-26 01:01 江苏

相关推荐

3 收藏 评论
分享
牛客网
牛客企业服务