省选PKU查漏补缺专题训练.doc

Peking University Online Judge March302009NOI省队第三轮选拔赛-图论算法专题训练试题第八组【题目一览】题号第一题第二题第三题第四题题目名称PigsLife FormsFiringShoot-out提交文件pigs.pas/c/cpplife.pas/c/cppfiring.pas/c/cppshoot.pas/c/cpp输入文件pigs.inlife.infiring.inshoot.in输出文件pigs.outlife.outfiring.outshoot.out时间限制1s5s5s4s试题类型最大流问题后缀树/后缀数组最大权闭包状态压缩动规难度系数题目出处POJ1149POJ3294POJ2987POJ3028题号第五题第六题第七题第八题题目名称PipesCommon SubstringsChecking the TextSequence提交文件pipes.pas/c/cppsub.pas/c/cpptext.pas/c/cppseq.pas/c/cpp输入文件ext.inseq.in输出文件pipes.outsub.outtext.outseq.out时间限制1s5s8s2s试题类型连通性状态压缩动规后缀树/后缀数组后缀数组 + RMQ后缀数组难度系数题目出处POJ2064POJ3415POJ2758POJ3581Pigs【问题描述】Mirko works on a pig farm that consists of M locked pig-houses and Mirko cant unlock any pighouse because he doesnt have the keys. Customers come to the farm one after another. Each of them has keys to some pig-houses and wants to buy a certain number of pigs.All data concerning customers planning to visit the farm on that particular day are available to Mirko early in the morning so that he can make a sales-plan in order to maximize the number of pigs sold.More precisely, the procedure is as following: the customer arives, opens all pig-houses to which he has the key, Mirko sells a certain number of pigs from all the unlocked pig-houses to him, and, if Mirko wants, he can redistribute the remaining pigs across the unlocked pig-houses.An unlimited number of pigs can be placed in every pig-house.Write a program that will find the maximum number of pigs that he can sell on that day.【输入格式】The first line of input contains two integers M and N, 1=M=1000, 1=N=100, number of pighouses and number of customers. Pig houses are numbered from 1 to M and customers are numbered from 1 to N.The next line contains M integeres, for each pig-house initial number of pigs. The number of pigs in each pig-house is greater or equal to 0 and less or equal to 1000.The next N lines contains records about the customers in the following form (record about the i-th customer is written in the (i+2)-th line):A K1 K2 KA BIt means that this customer has key to the pig-houses marked with the numbers K1, K2, , KA (sorted nondecreasingly) and that he wants to buy B pigs. Numbers A and B can be equal to 0.【输出格式】The first and only line of the output should contain the number of sold pigs.【输入输出样例】输入：3 33 1 102 1 2 22 1 3 31 2 6输出：7Life Forms【问题描述】You may have wondered why most extraterrestrial life forms resemble humans, differing by superficial traits such as height, colour, wrinkles, ears, eyebrows and the like. A few bear no human resemblance; these typically have geometric or amorphous shapes like cubes, oil slicks or clouds of dust.The answer is given in the 146th episode of Star Trek - The Next Generation, titled The Chase. It turns out that in the vast majority of the quadrants life forms ended up with a large fragment of common DNA.Given the DNA sequences of several life forms represented as strings of letters, you are to find the longest substring that is shared by more than half of them.【输入格式】Standard input contains several test cases. Each test case begins with 1=n=100, the number of life forms. n lines follow; each contains a string of lower case letters representing the DNA sequence of a life form. Each DNA sequence contains at least one and not more than 1000 letters. A line containing 0 follows the last test case.【输出格式】For each test case, output the longest string or strings shared by more than half of the life forms. If there are many, output all of them in alphabetical order. If there is no solution with at least one letter, output “?”. Leave an empty line between test cases.【输入输出样例】输入：3abcdefgbcdefghcdefghi3xxxyyyzzz0输出：bcdefgcdefgh?Firing【问题描述】Youve finally got mad at “the worlds most stupid” employees of yours and decided to do some firings. Youre now simply too mad to give response to questions like “Dont you think it is an even more stupid decision to have signed them?”, yet calm enough to consider the potential profit and loss from firing a good portion of them. While getting rid of an employee will save your wage and bonus expenditure on him, termination of a contract before expiration costs you funds for compensation. If you fire an employee, you also fire all his underlings and the underlings of his underlings and those underlings underlings underlings An employee may serve in several departments and his (direct or indirect) underlings in one department may be his boss in another department. Is your firing plan ready now?【输入格式】The input starts with two integers n (0n=5000) and m (0=m=60000) on the same line. Next follows n+m lines. The first n lines of these give the net profit/loss from firing the i-th employee individually bi (|bi|=107, 1=i=n). The remaining m lines each contain two integers i and j (1=i,j=n) meaning the i-th employee has the j-th employee as his direct underling.【输出格式】Output two integers separated by a single space: the minimum number of employees to fire to achieve the maximum profit, and the maximum profit.【输入输出样例】输入：5 58-9-2012-101 22 51 43 44 5输出：2 2提示：As of the situation described by the sample input, firing employees 4 and 5 will produce a net profit of 2, which is maximum.Shoot-out【问题描述】This is back in the Wild West where everybody is fighting everybody. In particular, there are n cowboys, each with a revolver. These are rather civilized cowboys, so they have decided to take turns firing their guns until only one is left standing. Each of them has a given probability of hitting his target, and they all know each others probability. Furthermore, they are geniuses and always know which person to aim at in order to maximize their winning chance, so they are indeed peculiar cowboys. If there are several equally good targets, one of those will be chosen at random. Note that a cowboys code of ethics forces him to do his best at killing one of his opponents, even if intentionally missing would have increased his odds (yes, this can happen!)【输入格式】On the first line of the input is a single positive integer t, telling the number of test cases to follow. Each case consists of one line with an integer 2=n=13 giving the number of cowboys, followed by n positive integers giving hit percentages for the cowboys in the order of their turns.【输出格式】For each test case, output one line with the percent probabilities for each of them surviving, in the same order as the input. The numbers should be separated by a space and be correctly rounded to two decimal places.【输入输出样例】输入：52 1 1003 100 99 983 50 99 1003 50 99 993 50 99 98输出：1.00 99.002.00 0.00 98.0025.38 74.37 0.2525.38 49.50 25.1225.63 24.63 49.74提示：Q: Does the cowboy know the other cowboys strategy of shooting?A: Yes.Pipes【问题描述】The construction of office buildings has become a very standardized task. Pre-fabricated modules are combined according to the customers needs, shipped from a faraway factory, and assembled on the construction site. However, there are still some tasks that require careful planning, one example being the routing of pipes for the heating system.A modern office building ismade up of squaremodules, one on each floor being a service module from which (among other things) hot water is pumped out to the other modules through the heating pipes. Each module (including the service module) will have heating pipes connecting it to exactly two of its two to four neighboring modules. Thus, the pipes have to run in a circuit, from the service module, visiting each module exactly once, before finally returning to the service module. Due to different properties of the modules, having pipes connecting a pair of adjacent modules comes at different costs. For example, some modules are separated by thick walls, increasing the cost of laying pipes. Your task is to, given a description of a floor of an office building, decide the cheapest way to route the heating pipes.【输入格式】The first line of input contains a single integer, stating the number of floors to handle. Then follow n floor descriptions, each beginning on a new line with two integers, 2=r=10 and 2=c=10, defining the size of the floor - r-by-c modules. Beginning on the next line follows a floor description in ASCII format, in total 2r+1 rows, each with 2c+2 characters, including the final newline. All floors are perfectly rectangular, and will always have an even number of modules. All interior walls are represented by numeric characters, 0 to 9, indicating the cost of routing pipes through the wall (see sample input).【输出格式】For each test case, output a single line with the cost of the cheapest route.【输入输出样例】输入：34 3# 2 3 #1#9#1# 2