hw2冬令营_自选题出题互测解题报告命题memory.pdfVIP

《记忆中的水杉树》解题报告 【题目简述】 在一个平面上有N 条线段。 要求做 N 作，每一轮可以选择一条线段，按水平或者垂直方向将线段移走，前提 是移动过程中不被任何尚未移走的线段所阻碍。如果某一轮线段的移动会被阻碍，那么这次 移动就是 的，是不被允许的。n 轮过后，平面上的所有线段都将被移走。 现在我们已经有了一个操作序列，需要你求出： 1) 找出最早的一次 移动出现在哪一轮； 2) 给出一个合法的移动方案完成这个N 作。 端点接触 造成阻碍。 【数据规模】 测试数据编号 n 其他约定 1 n = 3 对任意2≤i≤n 2 n ≤ 8 有 对任意1≤i≤n bi-1di-1bidi 有qi = 1 3 n ≤ 100 对任意1 ≤i≤n |ai|, |bi|, |ci|, 4 n ≤ 2,000 有aici，di–bi = 1 |di| ≤ 104 5 n ≤ 2,000 / 6 n ≤ 20,000 / 对任意1≤i≤n 7 n ≤ 30,000 / 有0 ≤qi≤ 3 8 n ≤ 50,000 / |ai|, |bi|, |ci|, 9 n ≤ 80,000 / |di| ≤ 109 10 n ≤ 100,000 / 【算法1】 对于问题1：找出最早的一次 移动出现在哪一轮，我们直接模拟即可，这只需要涉 及到很浅显的计算几何知识，每次判断的复杂度为O(N)。 2 时间复杂度：O(N )； 期望得分：25 分 对于问题2：很显然，无论当前局面如何，我们总是可以找到一条线段将其合法的移走。 因此我们每次枚举并且判断即可。 3 时间复杂度：O(N ) 期望得分：15分 总期望得分：40分 【算法2】 3 之前算法 1 求解问题二的复杂度高达 O(N )， 这里的复杂度优化下来，我们需 要进一步的分析。 通过分析，我们可以发现：所有线段只往一个方向移动也必然是有解的，所以，我们可 以直接根据这个限制，建立出一个图，如果线段i 要 段j 之前被移走，那么i 向j 连 一条有向边。 2 这个图必然是有向无环的， 为 N ，点数为 N，现在的任务相当于是要求我们求解 这个图的一个合法的拓扑序列。 2 时间复杂度：O(N ) 期望得分：50 分 【算法3】 我们有了建立一个有向图并求其拓扑序列的算法以后，会发现，由于图的规模过大，导 致我们无法解决剩下的测试点，那么我们能不能减少这个拓扑图的数量呢？ 是可以的~，我们观察下面这 ： 这 启示了我们，实际上我们只要将和每条线段的端点往上和往下碰到的第一条线段 建立限制关系即可，这样我们就成功的将拓扑图的 的规模缩小到了O(