国家集训队2006论文集周戈林周戈林

进行排序，那么一个点集就可以看成n次操作，每次操作将一条一个端点在O的线段顺时针旋转一个量，再拉长或缩短。一次操作可以用一个二元组(delta,distance)来描述，其中delta就是排序后相邻两点的方向角之差。这样一个n个点的点集S就被对应成了一个长度为n的串T。并且点集可以旋转，也就是串的起始位置不确定，是一个环串。因此两个点集同构，即是它们转换后得到的环串相同。而判断环串T与T’ 是否相同，可以把T和T’从某个地方截断得到U和U’，再使用kmp算法判断U’在串UU中是否出现即可。 概括一下上面的讨论：求质心的费用为O(n)，排序的耗费为O(nlog2n)，执行kmp算法的费用为O(3n)，最后翻转再判断的费用为O(n)，因此整个算法的复杂度就是O(nlog2n)。 有一点需要补充的是，以上的讨论都忽略了某个点与质心重合的情况，但处理此问题只需要特判即可。 小结 本题的关键是处理旋转和平移。我们忽略图形的次要信息——绝对坐标，把关注的重点变为点跟质心的关系以及点跟点的关系，因此平移问题就不存在了，用环串类比旋转操作自然就产生了最后的解法。 三、总结： 本文对类比作了一定的介绍，同时较深入地讨论了一些常见的类比模式。以上所有的解题方法都包含了一种思想，就是类比思想。类比思想是一种转化的思想，但是类比思想在转化过程中突出的不是演绎式的化归，而是跳跃式的比较。固然，类比在思考过程中可能是逐步进行的，但是在外在表现上一般是天马行空的。从这一点上来说，类比是一种相当不好掌握的思想方法。但无论怎么样的类比，都会有以下的特性： 1．可类比性：原问题和转化后的问题具有某些相似之处，正是这些相似之处为类比提供了理论依据和思考动机。 2．可简化性：转化后的问题必然要比原问题更简单。这个“简单”可以是更直观，便于解题者思考；可以是更常见，能利用的理论较多；也可以是更规范，能用标准的方法解决。 3．可移植性：转化后问题的解法要与类比对象密切相关。例如在例三中把点集类比为环串后，要密切注意串的匹配、求最长某某子串这一类算法。解法与类比对象相关，才能体现出类比的必要与优越。 尽管类比思想非常优秀，但并非没有局限性。类比要在转化的前提下才能完成，也就是说对于那些不需要转化的问题，类比是没有任何作用的。 四、感谢： 衷心感谢向期中老师在我写这篇论文时对我的指导和帮助。 衷心感谢刘汝佳教练对我的指导和启发。 衷心感谢陈启峰、杨沐、郭华阳、杨浩、冯子明、吴戈、袁昕颢、周玉姣、刘靓等同学在临近期末考试时还能帮助审阅我的论文，并提出很多宝贵的。 五、参考文献： [1]《数学闯关——数学思想和方法的领悟》 袁银宗编著 [2]《算法艺术与信息学竞赛》 刘汝佳 黄亮 著 [3] USACO OPEN05： peaks [4] USACO FEB05： secret [5] Poland Olympiad of Informatics 2005 Stage I：PUN 六、附录： 例一的原题： Problem 4: Landscaping [Brian Dean, 2005] Farmer John is making the difficult transition from raising mountain goats to raising cows. His farm, while ideal for mountain goats, is far too mountainous for cattle and thus needs to be flattened out a bit. Since flattening is an expensive operation, he wants to remove the smallest amount of earth possible. The farm is long and narrow and is described in a sort of two-dimensional profile by a single array of N (1 <= N <= 1000) integer elevations (range 1..1,000,000) like this: 1 2 3 3 3 2 1 3 2 2 1 2, which represents the farm's elevations in profile, depicted below with asterisks indicating the heights: * * * * * * * * * * * * * * * * * * * * * * * * * 1 2 3 3 3 2 1 3 2 2 1 2 A contiguous range of one or more equal elevations in this array is a "peak" if both the left and right hand sides of the range are either the boundary of the array or an element that is lower in elevation than the peak. The example above has three peaks. Determine the minimum volume of earth (each unit elevation reduction counts as one unit of volume) that must be removed so that the resulting landscape has no more than K (1 <= K <= 25) peaks. Note well that elevations can be reduced but can never be increased. If the example above is to be reduced to 1 peak, the optimal solution is to remove 2 + 1 + 1 + 1 = 5 units of earth to obtain this set of elevations: * * * - * * * * * - - - - * * * * * * * * * * * * 1 2 3 3 3 2 1 1 1 1 1 1 where '-'s indicate removed earth. PROBLEM NAME: peaks INPUT FORMAT: * Line 1: Two space-separated integers: N and K * Lines 2..N+1: Each line contains a single integer elevation. Line i+1 contains the elevation for index i. SAMPLE INPUT (file peaks.in): 12 1 1 2 3 3 3 2 1 3 2 2 1 2 INPUT DETAILS: This is the example used above. OUTPUT FORMAT: * Line 1: The minimum volume of earth that must be removed to reduce the number of peaks to K. SAMPLE OUTPUT (file peaks.out): 5 例二的原题： Problem 2: Secret Milking Machine [Vladimir Novakovski, 2003] Farmer John is constructing a new milking machine and wishes to keep it secret as long as possible. He has hidden in it deep within his farm and needs to be able to get to the machine without being detected. He must make a total of T (1 <= T <= 200) trips to the machine during its construction. He has a secret tunnel that he uses only for the return trips. The farm comprises N (2 <= N <= 200) landmarks (numbered 1..N) connected by P (1 <= P <= 40,000) bidirectional trails (numbered 1..P) and with a positive length that does not exceed 1,000,000. Multiple trails might join a pair of landmarks. To minimize his chances of detection, FJ knows he cannot use any trail on the farm more than once and that he should try to use the shortest trails. Help FJ get from the barn (landmark 1) to the secret milking machine (landmark N) a total of T times. Find the minimum possible length of the longest single trail that he will have to use, subject to the constraint that he use no trail more than once. (Note well: The goal is to minimize the length of the longest trail, not the sum of the trail lengths.) It is guaranteed that FJ can make all T trips without reusing a trail. PROBLEM NAME: secret INPUT FORMAT: * Line 1: Three space-separated integers: N, P, and T * Lines 2..P+1: Line i+1 contains three space-separated integers, A_i, B_i, and L_i, indicating that a trail connects landmark A_i to landmark B_i with length L_i. SAMPLE INPUT (file secret.in): 7 9 2 1 2 2 2 3 5 3 7 5 1 4 1 4 3 1 4 5 7 5 7 1 1 6 3 6 7 3 OUTPUT FORMAT: * Line 1: A single integer that is the minimum possible length of the longest segment of Farmer John's route. SAMPLE OUTPUT (file secret.out): 5 OUTPUT DETAILS: Farmer John can travel trails 1 - 2 - 3 - 7 and 1 - 6 - 7. None of the trails travelled exceeds 5 units in length. It is impossible for Farmer John to travel from 1 to 7 twice without using at least one trail of length 5. 例三的原题： Task: pun Points I stage competition   Source file: pun.xxx (xxx=pas,c,cpp) Memory limit: 32 MB Alternative formats: PostScript | PDF A set of integer points on a plane (points whose both cartesian coordinates are integers) which we shall refer to as the pattern, as well as a group of other sets of integer points on the plane are given. We would like to know which of the sets are similar to the pattern, i.e. which of them can be transformed by rotations, translations, reflections and dilations so that they are identical to the pattern. For instance: the set of points {(0,0), (2,0), (2,1)} is similar to the set {(6,1), (6,5), (4,5)}, it is however not similar to the set {(4,0),(6,0), (5,-1)}. Task Write a programme which: reads from the standard input the description of the pattern and the familly of the investigated sets of points, determines which of the investigated sets of points are similar to the pattern, writes the outcome to the standard output. Input In the first line of the standard input there is a single integer k (1 <= k <= 25.000) - the number of points the pattern consists of. In the following k lines there are pairs of integers, separated by single spaces. The i+1st line containts the coordinates of ith point belonging to the pattern: x_i i y_i (-20.000 <= x_i, y_i <= 20.000). The points forming the pattern are pairwise different. In the next line there is the number of sets to be investigated: n (1 <= n <= 20). Next, there are n descriptions of these sets. The description of each set begins with a line containing a single integer l - the number of points belonging to that particular set (1 <= l <= 25.000). These points are described in the following lines, a single point per line. The description of a point consists of two integers separated by a single space - its coordinates x i y (-20.000 <= x, y <= 20.000). The points which belong to the same set are pairwise different. Output Your programme should write to the standard output n lines - one for each of the investigated sets of points. The ith line should contain the word TAK (YES in Polish), if the ith of the given sets of points is similar to the pattern, or the word NIE (NO in Polish) if the set does not satisfy this condition. Example For the input data: 3 0 0 2 0 2 1 2 3 4 1 6 5 4 5 3 4 0 6 0 5 -1 the correct outcome is: TAK NIE 1 v u n _1195415127.unknown _1195415298.unknown _1195414508.unknown