【题解】牛客OI周赛4-提高组
(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题）
T1 K小生成树（kmst）
1.1 算法1
对于每次询问，进行一次暴力搜索，枚举所有情况，然后检验是否为生成树及权值和是否符合要求。
时间复杂度
，期望得分
分。
，期望得分分。 1.2 算法2
在算法1 的基础上，加入以下优化：
优化一：显然，对于任意一个n个节点的图，生成树的变数总是n-1条，若当前点数没有到n个但边数超过了n-1条。则剪枝。
优化二：在搜索的过程中，对该图的每一个生成树，使用前缀和数组来维护答案，将查询的复杂度降为
。
。 1.3 算法3
对于val（u，v）两两相等，L=R的10%的数据：
我们对该图做生成树计数，得出所有的生成树的个数，然后判断L是否与val(u，V）*（n-1）相等即可。
时间复杂度
1.4 算法4
枚举边集中的每一条边是否被选入生成树的边集中，利用路径压缩的并查集判断答案是否合法，然后利用前缀和数组统计答案。
时间复杂度
，期望得分50分。
，期望得分50分。 1.5 算法5
在算法4 的基础上，加入以下优化：
优化一:显然,对于任意一个n个节点的图,生成树的边数总是n-1条,若当前边数超过了n-1条,则剪枝。
优化二:使用并查集维护当前状态的连通性,若出现环,则剪枝。
优化三:使用带修并查集/可持久化并查集/某个数据结构动态维护当前状态,回溯地枚举,这样可以降低“判断是否有环”的复杂度。
优化四:舍弃前缀和数组中小于minL的部分,只记录[minL,maxR]部分的答案数,这样可以把前缀和数组的大小从maxR降低到maxR-minL,从而变得可以接受
时间复杂度
,期望得分100分。
优化二:使用并查集维护当前状态的连通性,若出现环,则剪枝。
优化三:使用带修并查集/可持久化并查集/某个数据结构动态维护当前状态,回溯地枚举,这样可以降低“判断是否有环”的复杂度。
优化四:舍弃前缀和数组中小于minL的部分,只记录[minL,maxR]部分的答案数,这样可以把前缀和数组的大小从maxR降低到maxR-minL,从而变得可以接受
时间复杂度
,期望得分100分。
T2 最后的晚餐（dinner）
T3 战争（war）
其他疑问可加以下交流群（加入一个即可啦~）
牛客多校算法训练营1：453799454
牛客全国算法训练营2：330766563
牛客多校算法训练营3：934889305
投递用友等公司8个岗位 >