数据结构 - Page 16

「CF480B」Long Jumps
ValeryisaPEteacherataschoolinBerland.Soonthestudentsaregoingtotakeatestinlongjumps,andValeryhaslosthisfavoriteruler!However,thereisnoreasonfordisappointment,asValeryhasfoundanotherruler,itslengthislcentimeters.Theruleralreadyhasnmarks,withwhichhecanmakemeasurements.Weassumethatthemarksarenumberedfrom1tonintheordertheyappearfromthebeginningoftherulertoitsend.Thefirstpointcoincideswiththe...
02014年10月20日3,950STL

「NOIP模拟赛」chenzeyu97要请客
题目背景众所周知，哲♂学家chenzeyu97由于在前面的许多场比赛中都取得了优♂异成绩！所以他在这场赛后要请客！题目描述chenzeyu97的家可以看成是一个n*m的矩阵，每块区域都有独一无二的海拔高度h（h>0）！其最大值为n*m。现在他要选择一个子矩阵摆放一张桌子，在他眼里，这样摆放桌子的美观度为这个子矩阵的最小值，他想知道，如果他要求摆放桌子的美观度为i，那么可以选择多少种子矩阵呢？对于所有可能的i值（1<=i<=n*m...
02014年10月18日4,124单调栈
「codecomb2098」stone
Descriptionn个石堆围成一圈，提供两种操作：1、每次将[L,R]堆的石子数量+k，其中，1<=L,R<=n,k>=0。2、询问有最多石子的那一堆有多少石子。现在，要求在线解决该问题。Input第一行两个整数n和m，n表示石子圈的长度，m表示操作数量。以下m行，首先一个是整数t，t=1或2，表示是哪种操作。如果t=1，则后面跟三个整数l,r,k，表示区间[l,r]的所有石子堆石子数量+k，如果t=2表示上述询问操作。 Output 对于...
02014年10月16日2,590线段树
「codecomb2096」lyz
Description滑冰俱乐部初始有1->n号码溜冰鞋各k双，已知x号脚的人可以穿x->x+d号码的鞋子。现在有m次操作，每次两个数r、x，表示r号脚的人来了x个，x为负表示离开。对于每次操作，输出溜冰鞋是否足够。Input第一行四个整数n,m,k,d。以下m行，每行一个操作。Output对于每一个询问，输出是否可行。若可行，输出TAK，反之，输出NIE。Sample Input4 4 2 11 32 33 32 -1Sample OutputTAKTAKNIETA...
02014年10月16日2,856线段树
「codecomb2097」rect
Description在一个n*m的格子棋盘上，有n*m堆石子，现在有两种操作：1、给(x1,y1)->(x2,y2)这个矩形内所有的石子堆加入k个石子。1<=x1<=x2<=n,1<=y1<=y2<=m。2、询问某格(x,y)上面有多少石子。Input第一行两个整数n和m，分别表示棋盘的长宽，n对应上述的x轴，m对应y轴。第二行一个整数p，表示操作数量。以下p行，首先一个是整数t，t=1或2，表示是哪种操作。如果t=1，则后面跟5个整数x1,y1,x2,y2,k，如上所...
02014年10月16日2,753树状数组
「codecomb2093」牛宫
DescriptionHzgd神牛准备给自己盖一座很华丽的宫殿。于是，他看中了一块N*M的矩形空地。空地中每个格子都有自己的海拔高度。胡张想让他的宫殿的平均海拔在海平面之上（假设海平面的高度是0，平均数都会算吧？）。而且，胡张希望他的宫殿是个矩形且尽量大，能够容纳更多的人来膜拜他。请问胡张的宫殿最后会有多大？Input Format第一行为N和M。之后N行，每行M个数，描述的空地的海拔。Output Format输出一行,表示宫殿最...
02014年10月15日3,760二分法,单调栈
「BZOJ1106」[POI2007] 立方体大作战tet
Description一个叫做立方体大作战的游戏风靡整个Byteotia。这个游戏的规则是相当复杂的，所以我们只介绍他的简单规则：给定玩家一个有2n个元素的栈，元素一个叠一个地放置。这些元素拥有n个不同的编号，每个编号正好有两个元素。玩家每次可以交换两个相邻的元素。如果在交换之后，两个相邻的元素编号相同，则将他们都从栈中移除，所有在他们上面的元素都会掉落下来并且可以导致连锁反应。玩家的目标是用最少的步数将方块全部消除...
02014年10月11日3,384树状数组
「BZOJ1023」[SHOI2008] cactus仙人掌图
Description如果某个无向连通图的任意一条边至多只出现在一条简单回路（simplecycle）里，我们就称这张图为仙人图（cactus）。所谓简单回路就是指在图上不重复经过任何一个顶点的回路。举例来说，上面的第一个例子是一张仙人图，而第二个不是——注意到它有三条简单回路：（4，3，2，1，6，5，4）、（7，8，9，10，2，3，7）以及（4，3，7，8，9，10，2，1，6，5，4），而（2，3）同时出现在前两个的简单回路里。另外，第三张图也...
22014年10月10日10,459递推与动规,单调队列,仙人掌
「BZOJ3110」[ZJOI2013] K大数查询
Description有N个位置，M个操作。操作有两种，每次操作如果是1abc的形式表示在第a个位置到第b个位置，每个位置加入一个数c如果是2abc形式，表示询问从第a个位置到第b个位置，第C大的数是多少。Input第一行N，M接下来M行，每行形如1abc或2abcOutput输出每个询问的结果SampleInput2511211122211221112123SampleOutput121HINTN,M<=50000,N,M<=50000a<=b<=N1操作中abs(c)<=N2操作中abs(c)<=M...
272014年10月8日24,705树套树,线段树
「NOIP模拟赛」魔兽争霸
小x正在销魂地玩魔兽他正控制着死亡骑士和n个食尸鬼(编号1～n)去打猎死亡骑士有个魔法，叫做“死亡缠绕”，可以给食尸鬼补充HP战斗过程中敌人会对食尸鬼实施攻击，食尸鬼的HP会减少小x希望随时知道自己部队的情况，即HP值第k多的食尸鬼有多少HP，以便决定如何施放魔法请同学们帮助他:) 小x向你发出3种信号：（下划线在输入数据中表现为空格）A_i_a表示敌军向第i个食尸鬼发出了攻击，并使第i个食尸鬼损失...
12014年10月6日5,070treap
「CF475D」CGCDSSQ
Givenasequenceofintegersa1, ..., anandqqueriesx1, ..., xqonit.Foreachqueryxiyouhavetocountthenumberofpairs(l, r)suchthat1 ≤ l ≤ r ≤ nandgcd(al, al + 1, ..., ar) = xi.isagreatestcommondivisorofv1, v2, ..., vn,thatisequaltoalargestpositiveintegerthatdividesallvi.InputThefirstlineoftheinputcontainsintegern,(1 ≤ n ≤ 105),denotingthelengthofthesequence.Thenextlinecont...
02014年10月6日4,578ST表,二分法,线段树
「BZOJ1098」[POI2007] 办公楼biu
DescriptionFGD开办了一家电话公司。他雇用了N个职员，给了每个职员一部手机。每个职员的手机里都存储有一些同事的电话号码。由于FGD的公司规模不断扩大，旧的办公楼已经显得十分狭窄，FGD决定将公司迁至一些新的办公楼。FGD希望职员被安置在尽量多的办公楼当中，这样对于每个职员来说都会有一个相对更好的工作环境。但是，为了联系方便起见，如果两个职员被安置在两个不同的办公楼之内，他们必须拥有彼此的电话号码...
02014年10月3日5,817深度搜索,链表,广度搜索