算法 - Page 61 - hzwer.com

「BZOJ3631」[JLOI2014] 松鼠的新家
Description松鼠的新家是一棵树，前几天刚刚装修了新家，新家有n个房间，并且有n-1根树枝连接，每个房间都可以相互到达，且俩个房间之间的路线都是唯一的。天哪，他居然真的住在“树”上。松鼠想邀请小熊维尼前来参观，并且还指定一份参观指南，他希望维尼能够按照他的指南顺序，先去a1，再去a2，……，最后到an，去参观新家。可是这样会导致维尼重复走很多房间，懒惰的维尼不听地推辞。可是松鼠告诉他，每走到一个房间，他就可以...
22014年9月25日5,657深度搜索,树形动规

「BZOJ3433」[Usaco2014 Jan] Recording the Moolympics
DescriptionBeingafanofallcold-weathersports(especiallythoseinvolvingcows),FarmerJohnwantstorecordasmuchoftheupcomingwinterMoolympicsaspossible.ThetelevisionschedulefortheMoolympicsconsistsofNdifferentprograms(1<=N<=150),eachwithadesignatedstartingtimeandendingtime.FJhasadual-tunerrecorderthatcanrecordtwoprogramssimultaneously.Pleasehelphimdeterminethemaximumnumberofprogramshecanr...
02014年9月25日3,796贪心
「BZOJ2555」SubString
Description懒得写背景了，给你一个字符串init，要求你支持两个操作(1):在当前字符串的后面插入一个字符串(2):询问字符串s在当前字符串中出现了几次？(作为连续子串)你必须在线支持这些操作。Input 第一行一个数Q表示操作个数第二行一个字符串表示初始字符串init接下来Q行，每行2个字符串Type,StrType是ADD的话表示在后面插入字符串。Type是QUERY的话表示询问某字符串在当前字符串中出现了几次。为了体现在...
02014年9月25日9,025后缀自动机,link cut tree
「codechefSUBLCM」Subarray LCM
题解首先筛法求100w以内的素数，同时记录每个质数最小的质因数然后用last[x]记录质因数x的最后出现位置，用tmp表示max{i}（满足i到当前位置now间的所有数互质）每次读入一个数a[now]，对a[now]分解质因数，更新tmp，更新last[x]tmp=max(tmp,last[t]);last[t]=i;最后用i-tmp更新答案我表达能力极弱啊。。。[crayon-6876d5bd77b16594208452/] ...
02014年9月24日3,241筛法
「codechefGRID」Sherlock and the Grid
这个纯模拟吧[crayon-6876d5bd77e86425445671/]
02014年9月24日2,697模拟
「codechefSUBGCD」Subarray GCD
题解发现如果一段子序列的gcd=1的话那么整段的gcd也等于1。。。[crayon-6876d5bd781e2371188051/]
02014年9月24日3,604最大公约数与最小公倍数
「POJ1734」Sightseeing trip
DescriptionThereisatravelagencyinAdeltontownonZanzibarisland.Ithasdecidedtoofferitsclients,besidesmanyotherattractions,sightseeingthetown.Toearnasmuchaspossiblefromthisattraction,theagencyhasacceptedashrewddecision:itisnecessarytofindtheshortestroutewhichbeginsandendsatthesameplace.Yourtaskistowriteaprogramwhichfindssucharoute.InthetownthereareNcrossingpointsnumberedfrom1toNandMtwo-wayr...
02014年9月24日3,971floyd
「BZOJ3706」「FJ2014集训」反色刷
「题目描述」给一张无向图，边有黑白两种颜色，现在你有一堆反色刷，可以从任意点开始刷，经过若干条边后回到起点。现在要询问至少需要多少个反色刷可以使这张图所有边都变成白色。因为某种原因，边的颜色是会改变的，于是。。需要支持以下操作：1x把第x条边反色（编号从0~m-1）2 询问当前图中最少需要多少个反色刷「输入格式」第一行两个整数nm表示这张图有n个点m条边接下来m行每行3个整数uvc表示一条无向边和这条边的颜色(0为...
02014年9月24日4,054欧拉图
「FJOI2013」圆形游戏
题目描述在一个无穷大的桌面上有n个圆形，保证任意2个圆相离或者相含，不存在相切或相交。现在Alice和Bob在玩一个圆形游戏，以Alice为先手，双方以如下步骤轮流游戏：1) 选定一个圆A，把A以及所有完全在A内部的圆都删除；2) 如果在自己回合无法找到可删除的圆，则输掉比赛。假设Alice和Bob都非常聪明，请问最终谁能够取得胜利？请编程输出最终获胜的人。输入输入数据的第一行为一个正整数T，表示数据组数。接下来T组数...
42014年9月23日6,109几何,博弈论
「POJ2932」Coneology
DescriptionAstudentnamedRoundSquarelovedtoplaywithcones.Hewouldarrangeconeswithdifferentbaseradiiarbitrarilyonthefloorandwouldadmiretheintrinsicbeautyofthearrangement.Thestudentevenbegantheorizingabouthowsomeconesdominateothercones:aconeAdominatesanotherconeBwhenconeBiscompletelywithintheconeA.Furthermore,henotedthattherearesomeconesthatnotonlydominateothers,butarethemselvesdominated,th...
02014年9月23日3,863几何
「SPOJ7258」Lexicographical Substring Search
LittleDaniellovestoplaywithstrings!Healwaysfindsdifferentwaystohavefunwithstrings!Knowingthat,hisfriendKinandecidedtotesthisskillssohegavehimastringSandaskedhimQquestionsoftheform:IfalldistinctsubstringsofstringSweresortedlexicographically,whichonewillbetheK-thsmallest?AfterknowingthehugenumberofquestionsKinanwillask,Danielfiguredoutthathecan'tdothisalone.Daniel,ofcourse,knowsyourexc...
02014年9月23日4,945后缀自动机
「SPOJ1812」Longest Common Substring II
Astringisfinitesequenceofcharactersoveranon-emptyfinitesetΣ.Inthisproblem,Σisthesetoflowercaseletters.Substring,alsocalledfactor,isaconsecutivesequenceofcharactersoccurrencesatleastonceinastring.Nowyourtaskisabitharder,forsomegivenstrings,findthelengthofthelongestcommonsubstringofthem.Herecommonsubstringmeansasubstringoftwoormorestrings.InputTheinputcontainsatmost10lines,eachlineconsistso...
02014年9月22日4,443后缀自动机