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

NOI省队第三轮选拔赛-图论算法专题训练试题 [第八组] 【题目一览】 题号 第一题 第二题 第三题 第四题 题目名称 Pigs Life Forms Firing Shoot-out 提交文件 pigs.pas/c/cpp life.pas/c/cpp firing.pas/c/cpp shoot.pas/c/cpp 输入文件 pigs.in life.in firing.in shoot.in 输出文件 pigs.out life.out firing.out shoot.out 时间限制 1s 5s 5s 4s 试题类型 最大流问题 后缀树/后缀数组 最大权闭包 状态压缩动规 难度系数 ★★★★★ ★★★★★ ★★★★★ ★★★★★ 题目出处 POJ1149 POJ3294 POJ2987 POJ3028 题号 第五题 第六题 第七题 第八题 题目名称 Pipes Common Substrings Checking the Text Sequence 提交文件 pipes.pas/c/cpp sub.pas/c/cpp text.pas/c/cpp seq.pas/c/cpp 输入文件 pipes.in sub.in text.in seq.in 输出文件 pipes.out sub.out text.out seq.out 时间限制 1s 5s 8s 2s 试题类型 连通性状态压缩动规 后缀树/后缀数组 后缀数组 + RMQ 后缀数组 难度系数 ★★★★★ ★★★★★ ★★★★ ★★★★ 题目出处 POJ2064 POJ3415 POJ2758 POJ3581 Pigs 【问题描述】 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