Differences

This shows you the differences between two versions of the page.

--- exam3 [2012/04/14 09:24] – xcyan
+++ exam3 [2012/04/14 12:56] (current) – [2108] xcyan
@@ Line 1: / Line 1: @@
-## 2106
+==== 2106 ====
 这道题目有很多种做法，下面我说一下我的做法：
 这道题目的本质就是求一个会聚点，使得两个分身到达本体的时间和最小。
 由于本体不会移动，所以只需要枚举三次即可。
 剩下的问题就是如何求分身到达本体的时间了，这个是一个单源最短路模型。
 其实可以直接用BFS暴力过掉，暴力过掉当然还需要一些技巧，我用的就是SPFA。
-至于什么是SPFA，请看：
-[[http://wcipeg.com/wiki/Shortest_Path_Faster_Algorithm|SPFA reference]]
+至于什么是SPFA，请看：[[http://wcipeg.com/wiki/Shortest_Path_Faster_Algorithm|SPFA reference]]
 当然，这道题的主人佘召臣有一个巧妙的构图方法，大家可以找他问一下。
-## 2107
+==== 2107 ====
 这是作业题中的翻版，首先说一下这道题的数据容易引起误解。
-比如A和B是Group1和Group2的强者，每次询问后不是输出max(A/2,B/2)，
-而是输出Group1和Group2并成一堆后，最强者。
+比如A和B是Group1和Group2的强者，每次询问后不是输出max(A/2,B/2)，而是输出Group1和Group2并成一堆后，最强者。
 然后就是怎么做这道题目了，熟读了题目之后发现这道题目涉及合并操作，以及找最大值操作。
 对于合并操作，我们能想到并查集，就是每次合并，将一堆人的首领和另一堆人的首领合并。
 下面就是找最大值的问题了，考场上有不少同学没思考清楚，直接在并查集的基础上做了一些不科学的改动，拿不到满分。
 其实想一想，找最大值用堆维护不就行了嘛。
 总结一下思路，这道题可以用并查集加上堆来解决，具体地说就是每一个集合里面建一个大根堆。
 初始时有N个堆，每个堆只有一个元素。
 每次合并，就将一堆删去，并入另外一堆。
 这样的确很暴力，不过至少可以通过7个点，已经很不错了。
 当然，由于作业里面出现了左堆，那么可以直接将堆换成左堆，大大减少了合并时间，数据就全过了。
-## 2108
+==== 2108 ====
 这道题目就是N路合并问题，如果不知道什么是N路合并，可以考虑N=2的情形。
 两个有序队列做合并，数据结构课里面应该讲过怎么做吧。现在我们将N扩大，然后就是N个有序队列做合并。
+"配对I" 这个题有2种做法 by 蒋舜宁：
+  - N路归并。先将A,B排序，考虑A[i]+B[j], j=1..N这个数列，对于每一个i都有一个N个数的有序数列，我们选取当前剩下的序列头中最小的那个，自然就是当前最小的一对。然后这就成了一个N路归并的问题。如果没法一下子想清楚，就画个图试试看吧，N行，每行N个数，每次比较这N行的头，然后把选了的那个头划掉，划N次。
+  - 二分答案套二分查找。我们发现，我们可以把第N大的数找出来。事实上，如果我们知道了一个数T，就可以算出比他小的有多少个，这个通过排序A,B，枚举每个i，然后二分得到B[j]<=T-A[i]的个数，再加起来，就可以搞出来，这一步的复杂度是kNlogN，k是个常数(<32)。最后，我们可以用算出来的答案ret，还原最后一次二分：再枚举i=1到N，将所有A[i]+B[j]<=ret的扔进数组，排序输出即可。
+上述两种方法都可以通过此题。