算法 - Page 65 - hzwer.com

「BZOJ1307」玩具
Description小球球是个可爱的孩子，他喜欢玩具，另外小球球有个大大的柜子，里面放满了玩具，由于柜子太高了，每天小球球都会让妈妈从柜子上拿一些玩具放在地板上让小球球玩。这天，小球球把所有的N辆玩具摆成一排放在地上，对于每辆玩具i，小球球都会给它涂上一个正整数value[i]，以表示小球球对该玩具的喜爱程度，value[i]越小则表示他越喜爱。当然对于两辆不同的玩具u,v(u<>v)，亦有可能value[i]=value[j]，也就是说小球...
02014年9月9日2,721其它

「BZOJ1318」[SPOJ744] Longest Permutation
Description给你一个序列A含有n个正整数(1<=Ai<=n)。A的子集形式类如Au,Au+1...,Av(1<=u<=v<=n)，即必须是连续的。我们感兴趣的是一种子集，它含有元素包括1,2,…k。（k是子集的大小）。你的任务是找到这种类型的最长的子集。Input第一行，一个数n，表示序列A的长度第二行，n个数，第I个数表示元素AiOutput一个数，表示可选子集的长度SampleInput541232SampleOutput4HINT你可以选得子集从A1开...
02014年9月9日3,570其它
「BZOJ1123」[POI2008] BLO
DescriptionByteotia城市有n个townsm条双向roads.每条road连接两个不同的towns,没有重复的road.所有towns连通。Input输入n<=100000m<=500000及m条边Output输出n个数，代表如果把第i个点去掉，将有多少对点不能互通。SampleInput551223133445SampleOutput8816148HINTtarjan求割点把某个割点去掉以后，会出现几个连通块，它们之间不能互相到达即会分成上面一棵树，下面若干子树子树之间不互通，所有子树和上面那个...
02014年9月8日17,173图的连通
「BZOJ3685」普通van Emde Boas树
Description设计数据结构支持:1x 若x不存在,插入x2x 若x存在,删除x3 输出当前最小值,若不存在输出-14 输出当前最大值,若不存在输出-15x 输出x的前驱,若不存在输出-16x 输出x的后继,若不存在输出-17x 若x存在,输出1,否则输出-1Input第一行给出n,m表示出现数的范围和操作个数接下来m行给出操作n<=10^6,m<=2*10^6,0<=x<nSampleInput101111121371742132345362SampleOutput1-1222-1题解线段树写的又慢...
52014年9月8日8,820线段树
「CF464C」Substitutes in Number
AndrewandEugeneareplayingagame.Initially,Andrewhasstrings,consistingofdigits.EugenesendsAndrewmultiplequeriesoftype"di → ti",thatmeans"replacealldigitsdiinstringswithsubstringsequaltoti".Forexample,ifs = 123123,thenquery"2 → 00"transformssto10031003,andquery"3 → "("replace3byanemptystring")transformsittos = 1212.AfterallthequeriesEugeneasksAndrewtofindtheremainderafterdivisi...
02014年9月8日4,369快速幂,离线处理
「CF464B」Restore Cube
Peterhadacubewithnon-zerolengthofaside.Heputthecubeintothree-dimensionalspaceinsuchawaythatitsverticeslayatintegerpoints(itispossiblethatthecube'ssidesarenotparalleltothecoordinateaxes).Thenhetookapieceofpaperandwrotedowneightlines,eachcontainingthreeintegers—coordinatesofcube'svertex(asinglelinecontainscoordinatesofasinglevertex,eachvertexiswrittenexactlyonce),putthepaperonthetableandleft.Wh...
02014年9月8日3,628深度搜索
「CF464A」No to Palindromes!
Paulhatespalindromes.HeassumesthatstringsistolerableifeachitscharacterisoneofthefirstplettersoftheEnglishalphabetandsdoesn'tcontainanypalindromecontiguoussubstringoflength2ormore.Paulhasfoundatolerablestringsoflengthn.Helphimfindthelexicographicallynexttolerablestringofthesamelengthorelsestatethatsuchstringdoesnotexist.InputThefirstlinecontainstwospace-separatedintegers:nandp(1 ≤ n ≤ ...
32014年9月8日5,702贪心
「BZOJ3479」[Usaco2014 Mar] Watering the Fields
Description Duetoalackofrain,FarmerJohnwantstobuildanirrigationsystemtosendwaterbetweenhisNfields(1<=N<=2000).Eachfieldiisdescribedbyadistinctpoint(xi,yi)inthe2Dplane,with0<=xi,yi<=1000.ThecostofbuildingawaterpipebetweentwofieldsiandjisequaltothesquaredEuclideandistancebetweenthem:(xi-xj)^2+(yi-yj)^2FJwouldliketobuildaminimum-costsystemofpipessothatallofhisfieldsarelinkedt...
02014年9月7日3,405prim
「BZOJ2599」[IOI2011] Race
Description给一棵树,每条边有权.求一条路径,权值和等于K,且边的数量最小.Input第一行两个整数n,k第二..n行每行三个整数表示一条无向边的两端和权值(注意点的编号从0开始)Output一个整数表示最小边数量如果不存在这样的路径输出-1SampleInput43011122134SampleOutput2题解这题有点怪的点分治。。。我的做法也比较逗，就是开一个100W的数组t,t[i]表示权值为i的路径最少边数找到重心分成若干子树后，得出一棵子树的所有点到...
22014年9月7日8,225点分治
「BZOJ2152」聪聪可可
Description聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑（可是他们家只有一台电脑）……遇到这种问题，一般情况下石头剪刀布就好了，可是他们已经玩儿腻了这种低智商的游戏。他们的爸爸快被他们的争吵烦死了，所以他发明了一个新游戏：由爸爸在纸上画n个“点”，并用n-1条“边”把这n个“点”恰好连通（其实这就是一棵树）。并且每条“边”上都有一个数。接下...
22014年9月7日6,644点分治
「BZOJ2719」[Violet 4] 银河之星
题解容易发现可以将平面的所有点分为9类012345678即同类棋子可以通过第三种移动到达相同位置而一个棋子跨过另一个，如0跨过4到达8，则可以视为0和4可以合成8，则问题转换为能不将所有点通过一系列合成得到一个和目标格子同类的点还要注意一下这种情况（1为棋子，0为目标，棋盘大小为3*3）1XXX0XXX1这种情况下是不能将0与8合成4的，除非将棋子移动到棋盘外所以还需要处理出在当前的棋盘大小内，哪些棋子可以相互合成，可以...
02014年9月6日4,148深度搜索
「NOIP模拟赛」藏妹子之处
问题描述：今天CZY又找到了三个妹子，有着收藏爱好的他想要找三个地方将妹子们藏起来，将一片空地抽象成一个R行C列的表格，CZY要选出3个单元格。但要满足如下的两个条件：（1）任意两个单元格都不在同一行。（2）任意两个单元格都不在同一列。选取格子存在一个花费，而这个花费是三个格子两两之间曼哈顿距离的和（如(x1,y1)和(x,y2)的曼哈顿距离为|x1-x2|+|y1-y2|）。狗狗想知道的是，花费在minT到maxT之间的方案数有多少...
42014年9月6日4,051其它