省选pku查漏补缺专题训练

《省选pku查漏补缺专题训练》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、PekingUniversityOnlineJudge[March·30·2009]NOI省队第三轮选拔赛-图论算法专题训练试题[第八组]【题目一览】题号第一题第二题第三题第四题题目名称PigsLifeFormsFiringShoot-out提交文件pigs.pas/c/cpplife.pas/c/cppfiring.pas/c/cppshoot.pas/c/cpp输入文件pigs.inlife.infiring.inshoot.in输出文件pigs.outlife.outfiring.outshoot

2、.out时间限制1s5s5s4s试题类型最大流问题后缀树/后缀数组最大权闭包状态压缩动规难度系数★★★★★★★★★★★★★★★★★★★★题目出处POJ1149POJ3294POJ2987POJ3028题号第五题第六题第七题第八题题目名称PipesCommonSubstringsCheckingtheTextSequence提交文件pipes.pas/c/cppsub.pas/c/cpptext.pas/c/cppseq.pas/c/cpp输入文件pipes.insub.intext.inseq.in输出

3、文件pipes.outsub.outtext.outseq.out时间限制1s5s8s2s试题类型连通性状态压缩动规后缀树/后缀数组后缀数组+RMQ后缀数组难度系数★★★★★★★★★★★★★★★★★★题目出处POJ2064POJ3415POJ2758POJ3581Pigs【问题描述】MirkoworksonapigfarmthatconsistsofMlockedpig-housesandMirkocan'tunlockanypighousebecausehedoesn'thavethekeys.Cus

4、tomerscometothefarmoneafteranother.Eachofthemhaskeystosomepig-housesandwantstobuyacertainnumberofpigs.AlldataconcerningcustomersplanningtovisitthefarmonthatparticulardayareavailabletoMirkoearlyinthemorningsothathecanmakeasales-planinordertomaximizethenum

5、berofpigssold.Moreprecisely,theprocedureisasfollowing:thecustomerarives,opensallpig-housestowhichhehasthekey,Mirkosellsacertainnumberofpigsfromalltheunlockedpig-housestohim,and,ifMirkowants,hecanredistributetheremainingpigsacrosstheunlockedpig-houses.Anu

6、nlimitednumberofpigscanbeplacedineverypig-house.Writeaprogramthatwillfindthemaximumnumberofpigsthathecansellonthatday.【输入格式】ThefirstlineofinputcontainstwointegersMandN,1<=M<=1000,1<=N<=100,numberofpighousesandnumberofcustomers.Pighousesarenumberedfrom1to

7、Mandcustomersarenumbered-9-PekingUniversityOnlineJudge[March·30·2009]from1toN.ThenextlinecontainsMintegeres,foreachpig-houseinitialnumberofpigs.Thenumberofpigsineachpig-houseisgreaterorequalto0andlessorequalto1000.ThenextNlinescontainsrecordsaboutthecust

8、omersinthefollowingform(recordaboutthei-thcustomeriswritteninthe(i+2)-thline):AK1K2…KABItmeansthatthiscustomerhaskeytothepig-housesmarkedwiththenumbersK1,K2,…,KA(sortednondecreasingly)andthathewantstobuyBpigs.NumbersAandBc