hzwer.com - Page 66

「BZOJ1123」[POI2008] BLO
DescriptionByteotia城市有n个townsm条双向roads.每条road连接两个不同的towns,没有重复的road.所有towns连通。Input输入n<=100000m<=500000及m条边Output输出n个数，代表如果把第i个点去掉，将有多少对点不能互通。SampleInput551223133445SampleOutput8816148HINTtarjan求割点把某个割点去掉以后，会出现几个连通块，它们之间不能互相到达即会分成上面一棵树，下面若干子树子树之间不互通，所有子树和上面那个...
02014年9月8日16,957图的连通

「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,702线段树
「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,153快速幂,离线处理
「CF464B」Restore Cube
Peterhadacubewithnon-zerolengthofaside.Heputthecubeintothree-dimensionalspaceinsuchawaythatitsverticeslayatintegerpoints(itispossiblethatthecube'ssidesarenotparalleltothecoordinateaxes).Thenhetookapieceofpaperandwrotedowneightlines,eachcontainingthreeintegers—coordinatesofcube'svertex(asinglelinecontainscoordinatesofasinglevertex,eachvertexiswrittenexactlyonce),putthepaperonthetableandleft.Wh...
02014年9月8日3,475深度搜索
「CF464A」No to Palindromes!
Paulhatespalindromes.HeassumesthatstringsistolerableifeachitscharacterisoneofthefirstplettersoftheEnglishalphabetandsdoesn'tcontainanypalindromecontiguoussubstringoflength2ormore.Paulhasfoundatolerablestringsoflengthn.Helphimfindthelexicographicallynexttolerablestringofthesamelengthorelsestatethatsuchstringdoesnotexist.InputThefirstlinecontainstwospace-separatedintegers:nandp(1 ≤ n ≤ ...
32014年9月8日5,616贪心
「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,350prim
「BZOJ2599」[IOI2011] Race
Description给一棵树,每条边有权.求一条路径,权值和等于K,且边的数量最小.Input第一行两个整数n,k第二..n行每行三个整数表示一条无向边的两端和权值(注意点的编号从0开始)Output一个整数表示最小边数量如果不存在这样的路径输出-1SampleInput43011122134SampleOutput2题解这题有点怪的点分治。。。我的做法也比较逗，就是开一个100W的数组t,t[i]表示权值为i的路径最少边数找到重心分成若干子树后，得出一棵子树的所有点到...
22014年9月7日8,094点分治
「BZOJ2152」聪聪可可
Description聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑（可是他们家只有一台电脑）……遇到这种问题，一般情况下石头剪刀布就好了，可是他们已经玩儿腻了这种低智商的游戏。他们的爸爸快被他们的争吵烦死了，所以他发明了一个新游戏：由爸爸在纸上画n个“点”，并用n-1条“边”把这n个“点”恰好连通（其实这就是一棵树）。并且每条“边”上都有一个数。接下...
22014年9月7日6,537点分治
「BZOJ2719」[Violet 4] 银河之星
题解容易发现可以将平面的所有点分为9类012345678即同类棋子可以通过第三种移动到达相同位置而一个棋子跨过另一个，如0跨过4到达8，则可以视为0和4可以合成8，则问题转换为能不将所有点通过一系列合成得到一个和目标格子同类的点还要注意一下这种情况（1为棋子，0为目标，棋盘大小为3*3）1XXX0XXX1这种情况下是不能将0与8合成4的，除非将棋子移动到棋盘外所以还需要处理出在当前的棋盘大小内，哪些棋子可以相互合成，可以...
02014年9月6日3,977深度搜索
「NOIP模拟赛」藏妹子之处
问题描述：今天CZY又找到了三个妹子，有着收藏爱好的他想要找三个地方将妹子们藏起来，将一片空地抽象成一个R行C列的表格，CZY要选出3个单元格。但要满足如下的两个条件：（1）任意两个单元格都不在同一行。（2）任意两个单元格都不在同一列。选取格子存在一个花费，而这个花费是三个格子两两之间曼哈顿距离的和（如(x1,y1)和(x,y2)的曼哈顿距离为|x1-x2|+|y1-y2|）。狗狗想知道的是，花费在minT到maxT之间的方案数有多少...
42014年9月6日3,926其它
「NOIP模拟赛」工资
聪哥在暑假参加了打零工的活动，这个活动分为n个工作日，每个工作日的工资为Vi。有m个结算工钱的时间,聪哥可以自由安排这些时间，也就是说什么时候拿钱，老板说的不算，聪哥才有发言权！（因为聪哥是土豪，他是老板的老板）聪哥不喜欢身上一次性有太多的钱，于是他想安排一下拿钱的时间，使他一次性拿的钱中最大的最小。（最后一天一定要领钱）输入第一行2个数n,m接下来n行，每行一个数，代表Vi.输出最小的最大钱数。样例输入751...
22014年9月6日3,187二分法
「BZOJ1655」[Usaco2006 Jan] Dollar Dayz 奶牛商店
DescriptionFarmerJohngoestoDollarDaysatTheCowStoreanddiscoversanunlimitednumberoftoolsonsale.Duringhisfirstvisit,thetoolsaresellingvariouslyfor$1,$2,and$3.FarmerJohnhasexactly$5tospend.Hecanbuy5toolsat$1eachor1toolat$3andanadditional1toolat$2.Ofcourse,thereareothercombinationsforatotalof5differentwaysFJcanspendallhismoneyontools.Heretheyare:1@US$3+1@US$21@US$3+2@US$11@US$...
02014年9月5日4,158背包动规,高精度