hzwer.com - Page 110

「BZOJ1345」[Baltic2007] 序列问题Sequence
Description对于一个给定的序列a1,…,an，我们对它进行一个操作reduce(i)，该操作将数列中的元素ai和ai+1用一个元素max(ai，ai+1)替代，这样得到一个比原来序列短的新序列。这一操作的代价是max(ai，ai+1)。进行n-1次该操作后，可以得到一个长度为1的序列。我们的任务是计算代价最小的reduce操作步骤，将给定的序列变成长度为1的序列。Input第一行为一个整数n(1<=n<=1,000,000)，表示给定序列的长度。接下来的n行，每行一个...
22014年3月23日4,172单调栈

「CF405C」Unusual Product
LittleChrisisahugefanoflinearalgebra.Thistimehehasbeengivenahomeworkaboutthe unusualsquare ofasquarematrix.The dotproduct oftwointegernumbervectors x and y ofsize n isthesumoftheproductsofthecorrespondingcomponentsofthevectors.The unusualsquare ofan n × n squarematrix A isdefinedasthesumof n dotproducts.The i-thofthemisthedotproductofthe i-throwvectorandthe i-thcolum...
02014年3月23日2,351模拟
「CF405B」Domino Effect
LittleChrisknowsthere'snofuninplayingdominoes,hethinksit'stoorandomanddoesn'trequireskill.Instead,hedecidedtoplay with thedominoesandmakea"dominoshow".Chrisarranges n dominoesinaline,placingeachpieceverticallyupright.Inthebeginning,hesimultaneouslypushessomeofthedominoeseithertotheleftortotheright.However,somewherebetweeneverytwodominoespushedinthesamedirectionthereisatleastonedominopush...
12014年3月23日2,731模拟
「CF405A」Gravity Flip
LittleChrisisboredduringhisphysicslessons(tooeasy),sohehasbuiltatoyboxtokeephimselfoccupied.Theboxisspecial,sinceithastheabilitytochangegravity.Thereare n columnsoftoycubesintheboxarrangedinaline.The i-thcolumncontains ai cubes.Atfirst,thegravityintheboxispullingthecubesdownwards.WhenChrisswitchesthegravity,itbeginstopullallthecubestotherightsideofthebox.Thefigureshowstheinitialandfi...
02014年3月23日2,350模拟
最小字符串
「题目描述」给定一些字符串(只包含小写字母)，要求将他们串起来构成一个字典序最小的字符串。「输入格式」第一行T,表示有T组数据。接下来T组数据每组第一行一个正整数n，表示字符串个数。接下来n行，每行一个字符串(长度不超过100)。「输出格式」T个字典序最小的字符串。「样例输入」13abc「样例输出」abc「数据范围」对于30%的数据T<=100;对于100%的数据T<=7000，n<=100；题解[crayon-67a64db0...
02014年3月22日4,210模拟
「CODEVS3013」单词背诵
题目描述 Description灵梦有n个单词想要背，但她想通过一篇文章中的一段来记住这些单词。文章由m个单词构成，她想在文章中找出连续的一段，其中包含最多的她想要背的单词（重复的只算一个）。并且在背诵的单词量尽量多的情况下，还要使选出的文章段落尽量短，这样她就可以用尽量短的时间学习尽可能多的单词了。输入描述 InputDescription第1行一个数n，接下来n行每行是一个长度不超过10的字符串，表示一个要背的单词。接着是一...
02014年3月22日3,437哈希表
「cogs1489」玩纸牌
「题目描述」本题目有一定的数学背景。题中要求计算一个随机变量的期望值。如果你之前没有听说过这些数学名词，下面给出了一些简单的定义。一个随机变量是一个可以取若干个值的变量，对于每个可能值，它都有一定概率取这个值。取到每个可能值的概率都是正的，并且它们的和是1.随机变量的数学期望是它所有可能值与其对应概率之积的乘积总和（对它有一些更为复杂，形式化的定义，但你现在不需要用到这些）。例如，一个标准的6面骰子投...
02014年3月22日3,511概率与期望
「BZOJ1982」[SPOJ 2021] Moving Pebbles
Description2021.MovingPebblesTwoplayersplaythefollowinggame.Atthebeginningofthegametheystartwithn(1<=n<=100000)pilesofstones.Ateachstepofthegame,theplayerchoosesapileandremoveatleastonestonefromthispileandmovezeroormorestonesfromthispiletoanyotherpilethatstillhasstones.Aplayerlosesifhehasnomorepossiblemoves.Giventheinitialpiles,determinewhowins:thefirstplayer,orthesecondplayer,ifboth...
02014年3月22日4,263博弈论
「POJ2115」C Looooops
DescriptionACompilerMystery:WearegivenaC-languagestyleforloopoftype [crayon-67a64db050a93350596410/]I.e.,aloopwhichstartsbysettingvariabletovalueAandwhilevariableisnotequaltoB,repeatsstatementfollowedbyincreasingthevariablebyC.WewanttoknowhowmanytimesdoesthestatementgetexecutedforparticularvaluesofA,BandC,assumingthatallarithmeticsiscalculatedinak-bitunsignedintegertype(withvalu...
22014年3月21日3,914扩展欧几里得算法
「BZOJ1477」青蛙的约会
Description两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只...
12014年3月21日5,354扩展欧几里得算法
「JoyOI1460」旅行
描述DescriptionA国有n座城市，每座城市都十分美，这使得A国的民众们非常喜欢旅行。然而，A国的交通十分落后，这里只有m条双向的道路，并且这些道路都十分崎岖，有的甚至还是山路，只能靠步行。通过每条道路的长度、泥泞程度等因素，我们给每条道路评估一个“崎岖度”，表示通过这条道路的不舒适程度。从X城市经过若干条道路到达Y城市，我们称这次旅行的“代价”为所经过道路“崎岖度”的最大值。当然，如果从X城市到Y城市...
112014年3月20日5,055并查集,二分法
「POJ2157」Maze
DescriptionAcm,atreasure-explorer,isexploringagain.Thistimeheisinaspecialmaze,inwhichtherearesomedoors(atmost5doors,representedby'A','B','C','D','E'respectively).Inordertofindthetreasure,Acmmayneedtoopendoors.However,toopenadoorheneedstofindallthedoor'skeys(atleastone)inthemazefirst.Forexample,ifthereare3keysofDoorA,toopenthedoorheshouldfindallthe3keysfirst(that'sthree'a'swhichdenote...
02014年3月20日3,217深度搜索