资源描述:
《acm第3周周赛试题》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、A:MaxSumofMax-K-sub-sequence(3415)TimeLimit:2000/1000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)本套试题摘自杭电:http://acm.hdu.edu.cn/vip/contest_show.php?cid=291TotalSubmission(s):525 AcceptedSubmission(s):51ProblemDescriptionGivenacirclesequenceA[1],A[2],A
2、[3]......A[n].CirclesequencemeanstheleftneighbourofA[1]isA[n],andtherightneighbourofA[n]isA[1].NowyourjobistocalculatethemaxsumofaMax-K-sub-sequence.Max-K-sub-sequencemeansacontinuousnon-emptysub-sequencewhichlengthnotexceedK. InputThefirstlineoftheinputcontainsanint
3、egerT(1<=T<=100)whichmeansthenumberoftestcases.ThenTlinesfollow,eachlinestartswithtwointegersN,K(1<=N<=100000,1<=K<=N),thenNintegersfollowed(alltheintegersarebetween-1000and1000). OutputForeachtestcase,youshouldoutputalinecontainsthreeintegers,theMaxSuminthesequence,
4、thestartpositionofthesub-sequence,theendpositionofthesub-sequence.Iftherearemorethanoneresult,outputtheminimumstartposition,ifstillmorethanone,outputtheminimumlengthofthem. SampleInput4636-12-65-5646-12-65-563-12-65-5666-1-1-1-1-1-1 SampleOutput713713762-111B:Marriag
5、eMatchIVTimeLimit:2000/1000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):295 AcceptedSubmission(s):38ProblemDescriptionDonotsincerenon-interference。Likethatshow,nowstarvaealsotakepartinashow,butittakeplacebetweencityAandB.Starvaeisinci
6、tyAandgirlsareincityB.EverytimestarvaecangettocityBandmakeadatawithagirlhelikes.Buttherearetwoproblemswithit,oneisstarvaemustgettoBwithinleasttime,it'ssaidthathemusttakeashortestpath.Otherisnoroadcanbetakenmorethanonce.Whilethecitystarvaepassedawaycanbeentakenmoretha
7、nonce.So,underagoodRP,starvaemayhavemanychancestogettocityB.Buthedon'tknowhowmanychancesatmosthecanmakeadatawiththegirlhelikes.Couldyouhelpstarvae? InputThefirstlineisanintegerTindicatingthecasenumber.(1<=T<=65)Foreachcase,therearetwointegernandminthefirstline(2<=n<=
8、1000,0<=m<=100000),nisthenumberofthecityandmisthenumberoftheroads.Thenfollowsmline,eachlinehavethreeintegersa,b,c,(1<=a,b<=n,0