算法 - Page 39 - hzwer.com

「BZOJ3791」作业
Description众所周知，白神是具有神奇的能力的。比如说，他对数学作业说一声“数”，数学作业就会出于畏惧而自己完成；对语文作业说一声“语”，语文作业就会出于畏惧而自己完成。今天，语文老师和数学老师布置了许多作业，同学们纷纷寻找白神寻求帮助。白神作为一个助人为乐的人，便答应下来。回到家，白神将这N份作业按顺序摊开，发现语文作业数学作业混在一起，这就让白神苦恼起来，他如果对连续一段作业喊出“数”，那么里面...
02014年12月15日2,756递推与动规

「BZOJ3158」千钧一发
DescriptionInput第一行一个正整数N。第二行共包括N个正整数，第个正整数表示Ai。第三行共包括N个正整数，第个正整数表示Bi。Output共一行，包括一个正整数，表示在合法的选择条件下，可以获得的能量值总和的最大值。SampleInput43451298309SampleOutput39HINT1<=N<=1000,1<=Ai,Bi<=10^6题解可以证明，任意两个偶数满足2两个奇数满足1(2a+1)^2+(2b+1)^2=2(2a^2+2b^2+2a+2b+1)一定不是完全平方数所以...
12014年12月15日4,553最小割
「BZOJ1822」[JSOI2010] Frozen Nova 冷冻波
DescriptionWJJ喜欢“魔兽争霸”这个游戏。在游戏中，巫妖是一种强大的英雄，它的技能FrozenNova每次可以杀死一个小精灵。我们认为，巫妖和小精灵都可以看成是平面上的点。当巫妖和小精灵之间的直线距离不超过R，且巫妖看到小精灵的视线没有被树木阻挡（也就是说，巫妖和小精灵的连线与任何树木都没有公共点）的话，巫妖就可以瞬间杀灭一个小精灵。在森林里有N个巫妖，每个巫妖释放FrozenNova之后，都需要等待一段时间，...
62014年12月15日5,049最大流,二分法,几何
「BZOJ2882」工艺
Description小敏和小燕是一对好朋友。他们正在玩一种神奇的游戏，叫Minecraft。他们现在要做一个由方块构成的长条工艺品。但是方块现在是乱的，而且由于机器的要求，他们只能做到把这个工艺品最左边的方块放到最右边。他们想，在仅这一个操作下，最漂亮的工艺品能多漂亮。两个工艺品美观的比较方法是，从头开始比较，如果第i个位置上方块不一样那么谁的瑕疵度小，那么谁就更漂亮，如果一样那么继续比较第i+1个方块。如果全都一样...
02014年12月15日4,540字符串,其它
「BZOJ2348」[Baltic 2011] Plagiarism
Description世界编程大赛的选手们提交N份程序文件f1,…,fN给评测系统。在将评测结果正式公布之前，评委会想要排除一切可能的剽窃现象。他们已有一个对比程序，用来比较两份程序文件，并判断它们是否太过相似了。然而程序文件的数目相当大，把每两份（一对，pair）文件都进行比较的话将花太多的时间。另一方面，许多对(pair)可以直接被排除，如果文件的大小相差太大的话。更准确地说，评委会决定，如果每两份文件（一对，pair）中...
02014年12月15日3,242二分法
「BZOJ1823」[JSOI2010] 满汉全席
Description满汉全席是中国最丰盛的宴客菜肴，有许多种不同的材料透过满族或是汉族的料理方式，呈现在數量繁多的菜色之中。由于菜色众多而繁杂，只有极少數博学多闻技艺高超的厨师能够做出满汉全席，而能够烹饪出经过专家认证的满汉全席，也是中国厨师最大的荣誉之一。世界满汉全席协会是由能够料理满汉全席的专家厨师们所组成，而他们之间还细分为许多不同等级的厨师。为了招收新进的厨师进入世界满汉全席协会，将于近日举办满汉...
02014年12月15日5,5572-SAT
「BZOJ4016」[FJOI2014] 最短路径树问题
cxjyxx_me:先求一个最短路图然后再这个图上dfs对于一个点的所有出点按编号从小到大dfs这样可以保证dfs树就是题目要求的树然后在这棵树上跑树分治f[i][j][2]表示前i棵子树从根出发链长为j[0：最长长度][1:这个长度条件下的方案数]对于第i+1棵子树单独跑一个f’[i][j][2]意义一样枚举这颗子树上链长和f一起更新答案然后用f‘更新f[crayon-6847b4724c34f481847819/] ...
52014年12月15日8,300STL,dijkstra,点分治
「POJ3683」Priest John’s Busiest Day
DescriptionJohnistheonlypriestinhistown.September1stistheJohn'sbusiestdayinayearbecausethereisanoldlegendinthetownthatthecouplewhogetmarriedonthatdaywillbeforeverblessedbytheGodofLove.ThisyearNcouplesplantogetmarriedontheblessedday.Thei-thcoupleplantoholdtheirweddingfromtimeSitotimeTi.Accordingtothetraditionsinthetown,theremustbeaspecialceremonyonwhichthecouplestandbeforethepriestandac...
22014年12月14日5,0322-SAT
「BZOJ1355」[Baltic2009] Radio Transmission
Description给你一个字符串，它是由某个字符串不断自我连接形成的。但是这个字符串是不确定的，现在只想知道它的最短长度是多少.Input第一行给出字符串的长度,1<L≤1,000,000.第二行给出一个字符串，全由小写字母组成.Output输出最短的长度SampleInput8cabcabcaSampleOutput3HINT对于样例,我们可以利用"abc"不断自我连接得到"abcabcabc",读入的cabcabca,是它的子串题解kmp。。。答案是n-fail[n]，随便画画应该能得到...
02014年12月14日4,358KMP
「POJ3207」Ikki’s Story IV – Panda’s Trick
Descriptionliympanda,oneofIkki’sfriend,likesplayinggameswithIkki.TodayafterminesweepingwithIkkiandwinningsomanytimes,heistiredofsucheasygamesandwantstoplayanothergamewithIkki.liympandahasamagiccircleandheputsitonaplane,therearenpointsonitsboundaryincircularborder:0,1,2,…,n−1.Evilpandaclaimsthatheisconnectingmpairsofpoints.Toconnecttwopoints,liympandaeitherplacesthelinkentirelyinsidethec...
02014年12月14日3,6902-SAT
「CF494B」Obsessive String
Hamedhasrecentlyfoundastringtandsuddenlybecamequitefondofit.Hespentseveraldaystryingtofindalloccurrencesoftinotherstringshehad.Finallyhebecametiredandstartedthinkingaboutthefollowingproblem.Givenastringshowmanywaysaretheretoextractk ≥ 1non-overlappingsubstringsfromitsuchthateachofthemcontainsstringtasasubstring?Moreformally,youneedtocalculatethenumberofwaystochoosetwosequencesa1, a2, ......
02014年12月14日4,708递推与动规,KMP
「CF494A」Treasure
Malekhasrecentlyfoundatreasuremap.Whilehewaslookingforatreasurehefoundalockeddoor.Therewasastringswrittenonthedoorconsistingofcharacters'(',')'and'#'.Belowtherewasamanualonhowtoopenthedoor.AfterspendingalongtimeMalekmanagedtodecodethemanualandfoundoutthatthegoalistoreplaceeach'#'withoneormore')'characterssothatthefinalstringbecomesbeautiful.Belowtherewasalsowrittenthatastringiscalledbeautif...
22014年12月14日3,134贪心