算法 - Page 42 - hzwer.com

NOI2011阿狸的打字机
Description 阿狸喜欢收藏各种稀奇古怪的东西，最近他淘到一台老式的打字机。打字机上只有28个按键，分别印有26个小写英文字母和'B'、'P'两个字母。经阿狸研究发现，这个打字机是这样工作的：l输入小写字母，打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。l按一下印有'B'的按键，打字机凹槽中最后一个字母会消失。l按一下印有'P'的按键，打字机会在纸上打印出凹槽中现有的所有字母并换行，但凹槽中的字母不会消...
32014年12月6日10,238dfs序,AC自动机,树状数组

「BZOJ1528」[POI2005] sam – Toy Cars
DescriptionJasio是一个三岁的小男孩,他最喜欢玩玩具了,他有n个不同的玩具,它们都被放在了很高的架子上所以Jasio拿不到它们.为了让他的房间有足够的空间,在任何时刻地板上都不会有超过k个玩具.Jasio在地板上玩玩具.Jasio'的妈妈则在房间里陪他的儿子.当Jasio想玩地板上的其他玩具时,他会自己去拿,如果他想玩的玩具在架子上,他的妈妈则会帮他去拿,当她拿玩具的时候,顺便也会将一个地板上的玩具放上架子使得地板上有足够的空间...
02014年12月6日4,622STL,堆,贪心
「BZOJ1216」[HNOI2003] 操作系统
Description写一个程序来模拟操作系统的进程调度。假设该系统只有一个CPU，每一个进程的到达时间，执行时间和运行优先级都是已知的。其中运行优先级用自然数表示，数字越大，则优先级越高。如果一个进程到达的时候CPU是空闲的，则它会一直占用CPU直到该进程结束。除非在这个过程中，有一个比它优先级高的进程要运行。在这种情况下，这个新的（优先级更高的）进程会占用CPU，而老的只有等待。如果一个进程到达时，CP...
02014年12月6日4,156STL,堆
「BZOJ2938」[POI2000] 病毒
Description二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。示例：例如如果{011,11,00000}为病毒代码段，那么一个可能的无限长安全代码就是010101…。如果{01,11,000000}为病毒代码段，那么就不存在一个无限长的安全代码。任务：请写一个...
02014年12月6日6,484深度搜索,AC自动机
「BZOJ2732」[HNOI2012] 射箭
Description沫沫最近在玩一个二维的射箭游戏，如下图1所示，这个游戏中的x轴在地面，第一象限中有一些竖直线段作为靶子，任意两个靶子都没有公共部分，也不会接触坐标轴。沫沫控制一个位于(0,0)的弓箭手，可以朝0至90?中的任意角度（不包括0度和90度），以任意大小的力量射出带有穿透能力的光之箭。由于游戏中没有空气阻力，并且光之箭没有箭身，箭的轨迹会是一条标准的抛物线，被轨迹穿过的所有靶子都认为被沫沫射中了，包括那些...
52014年12月4日6,682二分法,半平面交
「CF493E」Vasya and Polynomial
Vasyaisstudyinginthelastclassofschoolandsoonhewilltakeexams.Hedecidedtostudypolynomials.PolynomialisafunctionP(x) = a0 + a1x1 + ... + anxn.Numbersaiarecalledcoefficientsofapolynomial,non-negativeintegerniscalledadegreeofapolynomial.Vasyahasmadeabetwithhisfriendsthathecansolveanyproblemwithpolynomials.Theysuggestedhimtheproblem:"DeterminehowmanypolynomialsP(x)existwithintegernon-ne...
62014年12月4日5,181其它
「CF493D」Vasya and Chess
Vasyadecidedtolearntoplaychess.Classicchessdoesn'tseeminterestingtohim,soheplayshisownsortofchess.Thequeenisthepiecethatcapturesallsquaresonitsvertical,horizontalanddiagonallines.Ifthecellislocatedonthesamevertical,horizontalordiagonallinewithqueen,andthecellcontainsapieceoftheenemycolor,thequeenisabletomovetothissquare.Afterthattheenemy'spieceisremovedfromtheboard.Thequeencannotmovetoacellc...
02014年12月4日3,860博弈论
「CF493C」Vasya and Basketball
Vasyafollowsabasketballgameandmarksthedistancesfromwhicheachteammakesathrow.Heknowsthateachsuccessfulthrowhasvalueofeither2or3points.Athrowisworth2pointsifthedistanceitwasmadefromdoesn'texceedsomevalueofdmeters,andathrowisworth3pointsifthedistanceislargerthandmeters,wheredissomenon-negativeinteger.Vasyawouldliketheadvantageofthepointsscoredbythefirstteam(thepointsofthefirstteamminusthepointsof...
02014年12月4日3,627模拟
「CF493B」Vasya and Wrestling
Vasyahasbecomeinterestedinwrestling.Inwrestlingwrestlersusetechniquesforwhichtheyareawardedpointsbyjudges.Thewrestlerwhogetsthemostpointswins.Whenthenumbersofpointsofbothwrestlersareequal,thewrestlerwhosesequenceofpointsislexicographicallygreater,wins.Ifthesequencesoftheawardedpointscoincide,thewrestlerwhoperformedthelasttechniquewins.Yourtaskistodeterminewhichwrestlerwon.InputThefirstline...
02014年12月4日2,950模拟
「CF493A」Vasya and Football
Vasyahasstartedwatchingfootballgames.Hehaslearnedthatforsomefoulstheplayersreceiveyellowcards,andforsomefoulstheyreceiveredcards.Aplayerwhoreceivesthesecondyellowcardautomaticallyreceivesaredcard.Vasyaiswatchingarecordedfootballmatchnowandmakesnotesofallthefoulsthathewouldgiveacardfor.HelpVasyadetermineallthemomentsintimewhenplayerswouldbegivenredcardsifVasyawerethejudge.Foreachplayer,Vas...
02014年12月4日2,887模拟
「BZOJ2342」[SHOI2011] 双倍回文
Description Input输入分为两行，第一行为一个整数，表示字符串的长度，第二行有个连续的小写的英文字符，表示字符串的内容。Output输出文件只有一行，即：输入数据中字符串的最长双倍回文子串的长度，如果双倍回文子串不存在，则输出0。SampleInput16ggabaabaabaaballSampleOutput12HINTN<=500000题解p[i]表示i和i+1为中心的最长回文子串长度/2（str[i-k]=str[i+1+k]）。。。用manacherOn计算p数组题目要求计...
02014年12月3日6,764manacher
「BZOJ3769」「SPOJ 8549 BST again
Description求有多少棵大小为n的深度为h的二叉树。（树根深度为0；左右子树有别；答案对1000000007取模）Input第一行一个整数T，表示数据组数。以下T行，每行2个整数n和h。Output共T行，每行一个整数表示答案（对1000000007取模）SampleInput22132SampleOutput24HINT对于100%的数据，1<=n<=600,0<=h<=600,1<=T<=10题解f[i][j]表示大小i，深度小于j的二叉树数量则f[i][j]=(1<=k<=i)Σf[k-1]...
02014年12月3日3,018递推与动规