T1 Cut
采取逆向思维。问题就变成我们采取不断合并的策略,使得总代价最大。于是变成了经典的哈夫曼树题。每次从剩下的元素中挑选两个最大的进行合并,直至剩下一个元素。此题得解。
T2 Travel
通过一些观察可得:节点 到节点 的最短路肯定为以下两种情况之一:
1、不经过额外的 条边直接从 到 。
2、从先走到某个为额外边端点的 ,再从 走到某个同样为额外边端点的 ,最后从 走到 。
预处理所有额外边的端点间两两最短路,询问时暴力枚举更新答案即可。
时间复杂度: 。
算法二:
进一步观察可得,以上第二种路径可进一步化简为:从 先走到第一个为特殊边端点的 ,再从 走到最后一个为特殊边端点的 ,最后从 走到 ,这样的 和 都是与 和 相邻的。
故我们只需要预处理出与 相邻的两个和与 相邻的两个 ,就可以计算出答案了。时间复杂度: 。
T3 Butterfly
用 表示从 位置向下连续有多少个 ,用 表示从 位置向右下连续有多少个 ,用 表示从位置向左下连续有多少个 ,设 ,枚举蝴蝶的左上角 ,问题就变成了找到对应的右上角 ,使得 且 且 最大。移一下前面的式子,即我们要在区间 里找到最大的 ,使得满足 。我们把 按照 排序,随着 从左到右枚举,一点一点把 加进考虑的范畴,于是问题变成了在一段区间里找一个最大的 ,随便怎么弄都可以啦!std选择了线段树,也可以使用并查集路径压缩大法。复杂度
T4 Delete
考虑到图是 DAG 形态,那么删掉一个点 以后会发生什么呢?考虑拓扑序,一定有一条边从 的左边连接到 的右边。我们可以枚举所有的边 ,用 更新拓扑序中 区间的最小值。查询的时候线段树里找一找就可以啦!
T5 Mod
将 这个区间询问拆成两个前缀询问, 不动。问题形如 属于 , 属于 ,将 模去 答案不变,因此可考虑对 和 进行辗转相除。令 ,原问题中的 属于。其中 属于。因为每个 至多对应一组 ,所以这就是求这个三元不定方程在限制下有多少组解。通过 的范围,算 的范围:
全部评论
(0) 回帖