模拟赛T2 交换 解题报告

模拟赛T2 交换 解题报告

题目大意:

给定一个序列和若干个区间,每次从区间中选择两个数修改使字典序最小。
\(n,m\) 同阶 \(10^6\)
2.1 算法 1
按照题意模拟,枚举交换位置并比较。
时间复杂度\(O(mn3)\)。
期望得分20分。
2.2 算法 2
不难发现给定区间之外的位置对每个询问的答案无影响,所以每次的问题就是取出一个子段,问这个子段怎样交换一次字典序最小。
根据字典序定义,我们需要找到最小的位置满足通过交换可以使这个位置变小,也就是说这个位置不是后缀最小值,因此从后往前取最小值,找出可以变小的位置中最靠前的一个。最后与把这个位置与这个位置之后的最小值交换就是最优的了。
时间复杂度\(O(mn)\)。
期望得分40 − 50分。
2.3 算法 3
对于性质 A 可以用 set 暴力找出这些逆序对。因为每次交换的时候一定会使逆序对减少,所以对于每个询问,枚举哪些逆序对在区间中,选择最优的交换,并更新减少的逆序对。
时间复杂度\(O(nlogn(n) + 100m)\)
结合前面的算法,期望得分55 − 60分。
2.4 算法 4
对于性质 B 可以发现每个区间第一个可以交换变优的位置会很靠前。直接暴力枚举前几位看一下是不是能交换,用线段树维护区间最小值。应该可以取得不错的效果。结合前面的算法,期望得分65 − 70分。
2.5 算法 5
问题在于如何求出第一个能变小的位置。可以找出这一段区间从开头开始的最长的连续上升段,那么交换的一定是连续上升段内和连续上升段后的数字。可以求出连续上升段之后的最小值,然后找到连续上升段中第一个比这个最小值大的位置,交换这两个位置就是最优的。
求连续上升段可以为每个位置维护一个标记,表示这个位置是否比下一个位置大。使用线段树二分查找第一个有标记的位置就能找到最长连续上升段。线段树维护最小值很简单。最后查询连续上升段中比一个数大的最小位置,这个可以维护区间的最大值,同样二分查找即可。
时间复杂度O(nlog(n))
期望得分100分。

上一篇:1044 火星数字 (20 分)


下一篇:浙大版《C语言程序设计实验与习题指导(第4版)》题目集 实验2-3-8 计算火车运行时间