Differences

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

--- exam3 [2012/04/09 10:24] – xcyan
+++ exam3 [2012/04/14 12:56] (current) – [2108] xcyan
@@ Line 1: / Line 1: @@
+==== 2106 ====
+这道题目有很多种做法，下面我说一下我的做法：
-# 二哥的逃离
+这道题目的本质就是求一个会聚点，使得两个分身到达本体的时间和最小。
+由于本体不会移动，所以只需要枚举三次即可。
-## Description
+剩下的问题就是如何求分身到达本体的时间了，这个是一个单源最短路模型。
-二哥突然学会了Blink（闪烁）魔法，但他也因此被伊利丹追杀。在慌乱之间，二哥冲入了迷宫的入口，被传送进入了远古之迷宫。
+其实可以直接用BFS暴力过掉，暴力过掉当然还需要一些技巧，我用的就是SPFA。
-“你将一分为三，两个分身，一个本体。分身不能走动只能使用魔法，而本体则会被束缚而完全无法动弹，他们会被传送至不同的地方。但是作为补偿，你可以在开始行动之前，决定自己的本体是三者中的哪一个。当三者重新汇聚，束缚将被打破，你也自然脱离了迷宫。”二哥在恍惚之间听到了这样一番话。
+至于什么是SPFA，请看：[[http://wcipeg.com/wiki/Shortest_Path_Faster_Algorithm|SPFA reference]]
-迷宫是一个矩形，被划分成了\\( N \\)行\\( M \\)列共\\(N \times M\\)个小格。迷宫左上角小格的坐标定义为\\((1,1)\\)，右上角小格的坐标定义为\\((1,M)\\)，右下角小格的坐标定义为\\((N,M)\\)。两小格\\((a,b)\\)，\\((c,d)\\)之间的距离定义为\\(|a-c|+|b-d|\\)（即曼哈顿距离）。
+当然，这道题的主人佘召臣有一个巧妙的构图方法，大家可以找他问一下。
-二哥唯一能做的事就是使用闪烁魔法，来使得自己的两个分身尽快与本体会合。不过正如同之前听到的那句话，只有分身能够使用闪烁魔法进行移动。
+==== 2107 ====
+这是作业题中的翻版，首先说一下这道题的数据容易引起误解。
-由于二哥的魔法水平有限，他每次使用魔法只能让分身移动到一定距离以内的任意一个小格并且在进行移动之前需要一段时间进行准备（吟唱魔法）。而在这个神秘的迷宫里，二哥发现他的分身在每个小格所能移动的距离和吟唱时间是不同的。
+比如A和B是Group1和Group2的强者，每次询问后不是输出max(A/2,B/2)，而是输出Group1和Group2并成一堆后，最强者。
-在 \\( \(i,j\) \\)小格上能移动的最大距离为: \\( A_{i,j} \\)
+然后就是怎么做这道题目了，熟读了题目之后发现这道题目涉及合并操作，以及找最大值操作。
-需要的准备时间为: \\( B_{i,j} \\)
+对于合并操作，我们能想到并查集，就是每次合并，将一堆人的首领和另一堆人的首领合并。
-更加悲剧的是，二哥每次只能让一个分身进行吟唱魔法并移动，移动完毕之后才能进行下一次吟唱。
+下面就是找最大值的问题了，考场上有不少同学没思考清楚，直接在并查集的基础上做了一些不科学的改动，拿不到满分。
-现在，二哥想知道，自己至少要花多少时间才能逃脱出迷宫。
+其实想一想，找最大值用堆维护不就行了嘛。
-注意：迷宫的外部是虚无，二哥不会通过闪烁移动到迷宫之外。
+总结一下思路，这道题可以用并查集加上堆来解决，具体地说就是每一个集合里面建一个大根堆。
-## Input Format
+初始时有N个堆，每个堆只有一个元素。
-第一行两个整数\\( N,M \\)
+每次合并，就将一堆删去，并入另外一堆。
-接下来两个\\( N \times M \\) 的自然数矩阵:
+这样的确很暴力，不过至少可以通过7个点，已经很不错了。
-\\( A_{i,j} \\) ,
-\\( B_{i,j} \\)
-接下来六个数\\(Xx,Xy,Yx,Yy,Zx,Zy\\)，表示本体和两个分身的坐标。
+当然，由于作业里面出现了左堆，那么可以直接将堆换成左堆，大大减少了合并时间，数据就全过了。
+==== 2108 ====
+这道题目就是N路合并问题，如果不知道什么是N路合并，可以考虑N=2的情形。
-## Output Format
+两个有序队列做合并，数据结构课里面应该讲过怎么做吧。现在我们将N扩大，然后就是N个有序队列做合并。
-输出两行第一行一个字符\\( X,Y\\)或\\( Z \\)，表示以哪一个为本体。
-第二行一个整数，表示最短时间。
-若无法逃出迷宫，则只输出一行"NO"（不带引号）。
-## Sample Input
-4
-0 0 0
-2 2 0
-2 2 1
-0 0 0
-5 5 5
-5 5 5
-5 5 5
-5 5 5
-1 3 4 2 2
-## Sample Output
-	Z
-## About Test Data
-对于20%的数据：\\( 1 \leq n,m \leq 10 \\)。
-对于50%的数据：\\( 1 \leq n,m \leq 100 \\) \\( 1 \leq B_{i,j} \leq 30 \\)。
-对于100%的数据：\\( 1 \leq n,m \leq 100 \\)
-\\( 1 \leq B_{i,j} \leq 100 \\)
-\\( 1 \leq A_{i,j} \leq 10^9 \\)
-# 体育节之战
-## Description
-这次体育节多了一个新项目，神还没有确定它的名字，不过他在人间的代言人已经知道了一些关于这个项目的内容：
-\\(n\\)个人，每个人有个强度值\\(a_i\\)(编号从1开始)，最开始的时候大家都不认识。然后有\\(m\\)次冲突发生，每次冲突发生在2个不认识的人之间(如果两个人本来就认识，则不发生冲突)，这时双方各自会找自己所认识的人中最强的人出来决斗，经过决斗之后他们就互相认识了（并且他们原本认识的人现在都互相认识了）。决斗后，参加决斗的胜者的强度值会减半（向下取整）。
-神想知道对于每次决斗，参与决斗的人所认识的所有人中最大的强度值。希望你能写一个程序帮他解决这个问题。
-## Input Format
-输入共有\\(n + m + 2\\)行。
-第\\(1\\)行有\\(1\\)个整数\\(n\\)，表示参与这个项目的人数
-第\\(2\\)到\\(n + 1\\)行每行有\\(1\\)个整数，分别表示每个人的强度值。
-第\\(n + 2\\)行是一个整数\\(m\\)。
-第\\(n + 3\\)到\\(m + n + 2\\)行描述\\(m\\)组询问，即冲突双方的编号
-## Output Format
-输出\\(m\\)行，每行是对于询问的回答(参与决斗的人所认识的所有人中最大的强度值)。
-如果询问的两个人本来就认识，那么输出-1
-## Sample Input
-3
-4
-5
-5
-5
-## Sample Output
-	-1
-## About Test Data
-对于30%的数据，\\(1 \leq m, n \leq 1000\\)。
-对于70%的数据，\\(1 \leq n \leq 100000, 1 \leq m \leq 1000\\)。
-对于100%的数据，\\(1 \leq n \leq 100000, 1 \leq m \leq 100000\\)。
-# 配对 I
-## Description
-DS接到一个任务，这个任务有很多部分，每一个部分需要两个人完成，自然就要进行配对。
-本次配对的具体要求教务处已经下发：
-) 一共\\( 2 \times N \\)个人，分为两个队伍，每队\\( N \\)人，每个人都有一个工作能力评估值（可以相同）。总共需要配出\\( N \\)对，每对两个人。
-) 每个人可以被配对多次，每一对中的两个人分别来自不同队伍。
-) 要求中提到，需要得到工作能力评估值之和最小的\\( N \\)对。
-请你帮忙进行配对。
-## Input Format
-输入共有三行。
-第一行一个整数\\( N \\)，意义如上。
-第二行有\\( N \\)个整数，分别表示第一个队伍中每个人的工作能力评估值。
-第三行有\\( N \\)个整数，分别表示第二个队伍中每个人的工作能力评估值。
-## Output Format
-共\\( N \\)行，每行一个整数，表示每一对的工作能力评估值之和。
-按照升序输出。
-## Sample Input
-7 4 5
-3 1 4
-## Sample Output
-## About Test Data
-对于30%数据  \\(1 \leq N \leq 800\\)。
-对于100%数据 \\(1 \leq N \leq 200,000\\)。
-所有工作能力评估值\\(\leq 100,000,000\\)。
-样例解释：
-+1, 2+3, 4+1, 2+4
+"配对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的扔进数组，排序输出即可。
+上述两种方法都可以通过此题。