【题解】 Wannafly挑战赛2

T1 Cut

采取逆向思维。问题就变成我们采取不断合并的策略,使得总代价最大。于是变成了经典的哈夫曼树题。每次从剩下的元素中挑选两个最大的进行合并,直至剩下一个元素。此题得解。

T2 Travel

通过一些观察可得:节点 到节点 的最短路肯定为以下两种情况之一:

1、不经过额外的 条边直接从

2、从先走到某个为额外边端点的 ,再从 走到某个同样为额外边端点的 ,最后从 走到

预处理所有额外边的端点间两两最短路,询问时暴力枚举更新答案即可。

时间复杂度:

算法二:

进一步观察可得,以上第二种路径可进一步化简为:从 先走到第一个为特殊边端点的 ,再从 走到最后一个为特殊边端点的 ,最后从 走到 ,这样的 都是与 相邻的。

故我们只需要预处理出与 相邻的两个和与 相邻的两个 ,就可以计算出答案了。时间复杂度:

T3 Butterfly

表示从 位置向下连续有多少个 ,用 表示从 位置向右下连续有多少个 ,用 表示从位置向左下连续有多少个 ,设 ,枚举蝴蝶的左上角 ,问题就变成了找到对应的右上角 ,使得 最大。移一下前面的式子,即我们要在区间 里找到最大的 ,使得满足 。我们把 按照 排序,随着 从左到右枚举,一点一点把 加进考虑的范畴,于是问题变成了在一段区间里找一个最大的 ,随便怎么弄都可以啦!std选择了线段树,也可以使用并查集路径压缩大法。复杂度

T4 Delete

考虑到图是 DAG 形态,那么删掉一个点 以后会发生什么呢?考虑拓扑序,一定有一条边从 的左边连接到 的右边。我们可以枚举所有的边 ,用 更新拓扑序中 区间的最小值。查询的时候线段树里找一找就可以啦!

T5 Mod

这个区间询问拆成两个前缀询问, 不动。问题形如 属于 属于 ,将 模去 答案不变,因此可考虑对 进行辗转相除。令 ,原问题中的 属于。其中 属于。因为每个 至多对应一组 ,所以这就是求这个三元不定方程在限制下有多少组解。通过 的范围,算 的范围:

全部评论

相关推荐

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