算法 - Page 68 - hzwer.com

「BZOJ1751」[Usaco2005 qua] Lake Counting
DescriptionDuetorecentrains,waterhaspooledinvariousplacesinFarmerJohn'sfield,whichisrepresentedbyarectangleofNxM(1<=N<=100;1<=M<=100)squares.Eachsquarecontainseitherwater('W')ordryland('.').FarmerJohnwouldliketofigureouthowmanypondshaveformedinhisfield.Apondisaconnectedsetofsquareswithwaterinthem,whereasquareisconsideredadjacenttoalleightofitsneighbors.GivenadiagramofFar...
02014年8月27日3,127深度搜索

「CF461B」Appleman and Tree
Applemanhasatreewith n vertices.Someofthevertices(atleastone)arecoloredblackandotherverticesarecoloredwhite.Considerasetconsistingof k (0 ≤ k < n) edgesofAppleman'stree.IfApplemandeletestheseedgesfromthetree,thenitwillsplitinto (k + 1) parts.Note,thateachpartwillbeatreewithcoloredvertices.NowApplemanwonders,whatisthenumberofsetssplittingthetreeinsuchawaythateachresultingp...
02014年8月27日5,106树形动规
「CF461A」Appleman and Toastman
ApplemanandToastmanplayagame.InitiallyApplemangivesonegroupof n numberstotheToastman,thentheystarttocompletethefollowingtasks:EachtimeToastmangetsagroupofnumbers,hesumsupallthenumbersandaddsthissumtothescore.ThenhegivesthegrouptotheAppleman.EachtimeApplemangetsagroupconsistingofasinglenumber,hethrowsthisgroupout.EachtimeApplemangetsagroupconsistingofmorethanonenumber,hesplitsthegrou...
02014年8月26日3,156贪心
「BZOJ3545」[ONTAK2010] Peaks
Description在Bytemountains有N座山峰，每座山峰有他的高度h_i。有些山峰之间有双向道路相连，共M条路径，每条路径有一个困难值，这个值越大表示越难走，现在有Q组询问，每组询问询问从点v开始只经过困难值小于等于x的路径所能到达的山峰中第k高的山峰，如果无解输出-1。Input第一行三个数N，M，Q。第二行N个数，第i个数为h_i接下来M行，每行3个数abc，表示从a到b有一条困难值为c的双向路径。接下来Q行，每行三个数vxk...
22014年8月26日7,475线段树,离线处理
「BZOJ1324」Exca王者之剑
Description Input第一行给出数字N,M代表行列数.N,M均小于等于100下面N行M列用于描述数字矩阵Output输出最多可以拿到多少块宝石SampleInput221221SampleOutput4题解最小割[crayon-69114c15d9592118202717/] ...
02014年8月26日5,167最小割
「BZOJ2982」combination
DescriptionLMZ有n个不同的基友，他每天晚上要选m个进行[河蟹]，而且要求每天晚上的选择都不一样。那么LMZ能够持续多少个这样的夜晚呢？当然，LMZ的一年有10007天，所以他想知道答案mod10007的值。(1<=m<=n<=200,000,000)Input 第一行一个整数t，表示有t组数据。(t<=200) 接下来t行每行两个整数n,m，如题意。OutputT行，每行一个数，为C(n,m)mod10007的答案。SampleInput451527342SampleOutpu...
02014年8月25日4,081排列组合
「BZOJ2212」[POI2011] Tree Rotations
DescriptionByteasarthegardenerisgrowingararetreecalledRotatusInformatikus.Ithassomeinterestingfeatures:Thetreeconsistsofstraightbranches,bifurcationsandleaves.Thetrunkstemmingfromthegroundisalsoabranch.Eachbranchendswitheitherabifurcationoraleafonitstopend.Exactlytwobranchesforkoutfromabifurcationattheendofabranch-theleftbranchandtherightbranch.Eachleafofthetreeislabelledwithanintegerfro...
02014年8月25日6,011线段树
「BZOJ3224」JoyOI 1728 普通平衡树
Description您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：1.插入x数2.删除x数(若有多个相同的数，因只删除一个)3.查询x数的排名(若有多个相同的数，因输出最小的排名)4.查询排名为x的数5.求x的前驱(前驱定义为小于x，且最大的数)6.求x的后继(后继定义为大于x，且最小的数)Input第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号(1<=opt<=6)Output对于操作3,4,5,...
52014年8月23日23,894treap
「BZOJ3031」理科男
背景吃过草莓刨冰之后,Vani和cl有些疲倦地坐在一个长椅上。“呐,玩得开心吗?”Vani忽然问道。“嗯......很,很开心的说。”“那么,我有一个问题想要问你呢。”cl的脸有点红了起来。“嗯......好吧。问、问吧......我会告诉你的哦......”“那好。对于一个分数A/B......”“嗯......哎?哎?!”“......就是这个问题。我觉得这个问题好纠结啊......”Vani淡定地说完这句话。“啊?!哈啊?!”题目描述对于给定的分数A/B,求其在K进...
22014年8月23日3,573模拟
「BZOJ3680」吊打XXX
Descriptiongty又虐了一场比赛，被虐的蒟蒻们决定吊打gty。gty见大势不好机智的分出了n个分身，但还是被人多势众的蒟蒻抓住了。蒟蒻们将n个gty吊在n根绳子上，每根绳子穿过天台的一个洞。这n根绳子有一个公共的绳结x。吊好gty后蒟蒻们发现由于每个gty重力不同，绳结x在移动。蒟蒻wangxz脑洞大开的决定计算出x最后停留处的坐标，由于他太弱了决定向你求助。不计摩擦，不计能量损失，由于gty足够矮所以不会掉到地上。Input输入第一...
12014年8月22日6,479其它
「BZOJ3033」太鼓达人
背景七夕祭上，Vani牵着cl的手，在明亮的灯光和欢乐的气氛中愉快地穿行。这时，在前面忽然出现了一台太鼓达人机台，而在机台前坐着的是刚刚被精英队伍成员XLk、Poet_shy和lydrainbowcat拯救出来的的applepi。看到两人对太鼓达人产生了兴趣，applepi果断闪人，于是cl拿起鼓棒准备挑战。然而即使是在普通难度下，cl的路人本性也充分地暴露了出来。一曲终了，不但没有过关，就连鼓都不灵了。Vani十分过意不去，决定帮助工作人员修...
02014年8月22日5,709深度搜索,欧拉图
「BZOJ3032」七夕祭
背景七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。于是JoyOI今年举办了一次线下七夕祭。Vani同学今年成功邀请到了cl同学陪他来共度七夕，于是他们决定去JoyOI七夕祭游玩。描述JoyOI七夕祭和11区的夏祭的形式很像。矩形的祭典会场由N排M列共计N×M个摊点组成。虽然摊点种类繁多，不过cl只对其中的一部分摊点感兴趣，比如章鱼烧、苹果糖、棉花糖、射的屋……什么的。Vani预先联系了七夕祭的负责人zhq，希望能够...
02014年8月22日5,179其它