信息学集训队作业zoj

1、ZOJ2696Andrew Sevichs Contest #9Chip Designing解题题目大意在坐标平面上(i,0)有 n 个输入点，(i,1)有 n 个输出点。输出一个方案，按照给定的顺序，用折线把输入和输出一一连接起来。折线不能自交或相交，每一段都和坐标轴平行，线段数不超过 k=1000，每个线段的端点坐标必须是以不超过 maxlong的整数为分子分母的分数。算法分析首先试着手工求解。可以发现手工求解可以很随意地完成。如果能比较好地模拟这个“随意”的过程，这道题就能解决。把点和区间等同地离散化为格点进行 bfs。这道题的主要是不能不考虑平面上无数的点，又不能全部考虑。自然，平面上

2、的点有的重要，有的不重要。线段的端点，包括路径的拐角、输入点和输出点是重要的。可以用离散化的方法把这些重要的点的坐标值对应到连续的整数上。与此同时，两个相邻重要的点之间的部分可能是一条线段或者什么都没有，这些不重要的点也需要占有一席之地。可以把两个点之间的开区间看成（这两个点之间的）另一个点，同样对应到整数上。在两个维上都这样做，就得到了一个图论意义上的地图。在寻找路径之前，它的可通过性和题目给出的图是完全等价的。于是可以很容易地对这张地图进行 bfs。可以证明这样 bfs 时总能找到一条路。由于所有路径都有端点同时不能有交点，对图上的任意一个点都总能找到一条路径到无穷远处，这样对于两个点 A

3、，B 就有路径 A无穷远处B。每找到一条路径修改地图。找到的路径会在一些不重要的点的区间内有拐角，于是产生一些新的重要的点。自然要确定这些新点的坐标，但是在离散化的地图上坐标的具体值并不重要。事实上这项工作可以留到最后。在一维上，一个区间可以由此拆分为一个区间、一个点和另一个区间。这意味着每个新点的加入会导致地图上的若干行或列各自变成 3 行或 3 列。向地图中新的行和列并修改相应的内容，并且把新路径的标记化，使新的地图和加入新路径之后的状况等价。这样就可以 bfs 下一条边了。最后容易知道坐标轴上相邻整点之间要用到多少坐标，为地图上每个点确定坐标并输出路径即可。复杂度和优化这个算法的复杂度和

4、地图尺寸成正比，而地图尺寸决定于每次修改地图时增加的行数和列数。朴素的算法往往会不利用刚刚的有空闲的列而让地图额外增加一些行和列。在这种情况下，该题 n=10 的数据规模可以产生 120*120 左右的地图。这个程度已经完全可以 AC 该题。向地图中增加一些信息，使搜索路径时可以优先走对应点的行和列而不是对应区间的行和列，可以得到更好的效果。总结和心得这是一道基本没人交的题，或许很好地属于了囧题的范畴。这大概是因为手工求解很容易但是没什么明显规律。这样想进一步思考就会比较茫然，或者去考虑网络流之类的模型来追求一个完美（但是没有明确定义）的解。事实上，手工求解的容易以及 k=1000 和坐标分母

5、不超过 maxlong这些显得不大靠谱的限制给的信息只有一条：这道题真的可做。原题Chip DesigningTime limit: 10 SecondsTotal Submit: 4Memory limit: 32768K Accepted Submit: 1Spel JudgeDesigning computer chips is quite difficult. Recently Peter has decidedto get a job in Karelia Quaterconductors companyt is going to producechips for new EBM p

6、rosor. As a qualifying work for theition he hasgoask of designing a layout for a very simple chip. A chip has n inputsand n outputs, located in pos (0, 0) , (1, 0) , (n-1, 0) and (0,s are, of course,1)in, (1, 1) , , (n-1, 1) respectively (all dimen nanometers).his chip the i-th input must be connect

7、ed to the ai-th output using nanowires. All nanowires must be polylines with segments parallel to thesides of the chip (coordinate axes). No two nanowires mustersect(there must be no common pofor any two nanowires). The thickness ofthe wires is so small,t it can be ignored.Help Peter to get the job,

8、 write a programt will design the chip for him.InputThere are mutilple caseshe input file.line of each case contains n (1 = n = 10 ). Next line containsThen differenteger numbers - a1, a2, , an.There is an empty line after each case.OutputOutput the description of n nanowires. Each description must

9、start withk - the number of segmentshe wire (k must not exceed 1000). Nextk + 1 lines must contawo numbers each and specify the coordinates ofthe breaking pos of the polyline. All coordinates must be specifiedas rational irreducible fractions in a form “ nominator/ denominator”.Nominator and denominator must not exceed 109 .of the i-th polyline must be the i-th input of the chip pomust be the ai-th output of t