数据结构 - Page 11

「BZOJ2738」矩阵乘法
Description　　给你一个N*N的矩阵，不用算矩阵乘法，但是每次询问一个子矩形的第K小数。Input　　第一行两个数N,Q，表示矩阵大小和询问组数；接下来N行N列一共N*N个数，表示这个矩阵；再接下来Q行每行5个数描述一个询问：x1,y1,x2,y2,k表示找到以(x1,y1)为左上角、以(x2,y2)为右下角的子矩形中的第K小数。Output　　对于每组询问输出第K小的数。SampleInput2221341212111223SampleOutput13HINT　　矩阵中数...
02015年1月7日6,770二分法,树状数组

「BZOJ2527」[POI2011] Meteors
DescriptionByteotianInterstellarUnion(BIU)hasrecentlydiscoveredanewplanetinanearbygalaxy.Theplanetisunsuitableforcolonisationduetostrangemeteorshowers,whichontheotherhandmakeitanexceptionallyinterestingobjectofstudy.ThememberstatesofBIUhavealreadyplacedspacestationsclosetotheplanet'sorbit.Thestations'goalistotakesamplesoftherocksflyingby.TheBIUCommissionhaspartitionedtheorbitinto...
42015年1月7日8,054二分法,树状数组
「codechefTASTRMAT」String Matching
其实我没有参赛。。。在比赛时间被人拉去做了这一道。。。你们就坑我吧设L=n-m对于B的第1个字符，其匹配的是A的一个区间1到1+L若其与A[1]不同，则hash值增加100001^m与A[1+K]不同，则hash值增加100001^(n-K)用数据结构支持查询1到1+L对hash值的贡献即第K位与B的第1个字符不同则hash值增加100001^(n-K)，相同增加0用个线段树or树状数组（实际上前缀和就行）接着考虑对于B的第2个字符，其匹配的是A的一个区间2到2+L若...
02014年12月28日2,935线段树,乘法逆元
「CF498D」Traffic Jams in the Land
Somecountryconsistsof(n + 1)cities,locatedalongastraighthighway.Let'snumberthecitieswithconsecutiveintegersfrom1ton + 1intheordertheyoccuralongthehighway.Thus,thecitiesareconnectedbynsegmentsofthehighway,thei-thsegmentconnectscitiesnumberiandi + 1.Everysegmentofthehighwayisassociatedwithapositiveintegerai > 1—theperiodoftrafficjamsappearanceonit.Inordertogetfromcityxtocityy(x <...
12014年12月25日4,623线段树
「BZOJ1078」[SCOI2008] 斜堆
Description斜堆(skewheap)是一种常用的数据结构。它也是二叉树，且满足与二叉堆相同的堆性质：每个非根结点的值都比它父亲大。因此在整棵斜堆中，根的值最小。但斜堆不必是平衡的，每个结点的左右儿子的大小关系也没有任何规定。在本题中，斜堆中各个元素的值均不相同。在斜堆H中插入新元素X的过程是递归进行的：当H为空或者X小于H的根结点时X变为新的树根，而原来的树根（如果有的话）变为X的左儿子。当X大于H的根结点...
22014年12月24日6,929可并堆
「BZOJ2333」[SCOI2011] 棘手的操作
Description有N个节点，标号从1到N，这N个节点一开始相互不连通。第i个节点的初始权值为a[i]，接下来有如下一些操作：U x y:加一条边，连接第x个节点和第y个节点A1 x v:将第x个节点的权值增加vA2 x v:将第x个节点所在的连通块的所有节点的权值都增加vA3 v:将所有节点的权值都增加vF1 x:输出第x个节点当前的权值F2 x:输出第x个节点所在的连通块中，权值最大的节点的权值F3:输出所有节点中，权值最大的节点的权值...
92014年12月23日7,829STL,可并堆
「BZOJ1922」[SDOI2010] 大陆争霸
Description在一个遥远的世界里有两个国家：位于大陆西端的杰森国和位于大陆东端的克里斯国。两个国家的人民分别信仰两个对立的神：杰森国信仰象征黑暗和毁灭的神曾·布拉泽，而克里斯国信仰象征光明和永恒的神斯普林·布拉泽。幻想历8012年1月，杰森国正式宣布曾·布拉泽是他们唯一信仰的神，同时开始迫害在杰森国的信仰斯普林·布拉泽的克里斯国教徒。幻想历8012年3月2日，位于杰森国东部小镇神谕镇的克里斯国教徒发动起义。幻想...
22014年12月22日6,147STL,dijkstra
「BZOJ3809」Gty的二逼妹子序列
DescriptionAutumn和Bakser又在研究Gty的妹子序列了！但他们遇到了一个难题。对于一段妹子们，他们想让你帮忙求出这之内美丽度∈[a,b]的妹子的美丽度的种类数。为了方便，我们规定妹子们的美丽度全都在[1,n]中。给定一个长度为n(1<=n<=100000)的正整数序列s(1<=si<=n)，对于m(1<=m<=1000000)次询问“l,r,a,b”，每次输出sl...sr中，权值∈[a,b]的权值的种类数。Input第一行包括两个整数n,m(1<=n<=100...
192014年12月21日18,352分块,莫队算法
「POJ3237」Tree
DescriptionYouaregivenatreewithNnodes.Thetree’snodesarenumbered1throughNanditsedgesarenumbered1throughN−1.Eachedgeisassociatedwithaweight.Thenyouaretoexecuteaseriesofinstructionsonthetree.Theinstructionscanbeoneofthefollowingforms:CHANGEivChangetheweightoftheithedgetovNEGATEabNegatetheweightofeveryedgeonthepathfromatobQUERYabFindthemaximumweightofedgesonthepathfromat...
02014年12月21日6,014线段树,树链剖分
「BZOJ1924」[SDOI2010] 所驼门王的宝藏
「问题描述」==============================================================在宽广的非洲荒漠中,生活着一群勤劳勇敢的羊驼家族。被族人恭称为“先知”的AlpacaL.Sotomon是这个家族的领袖,外人也称其为“所驼门王”。所驼门王毕生致力于维护家族的安定与和谐,他曾亲自率军粉碎河蟹帝国主义的野蛮侵略,为族人立下赫赫战功。所驼门王一生财宝无数,但因其生性节俭低调,他将财宝埋藏在自己设计的地下宫殿里,这也是今天HenryCurt...
02014年12月20日6,246递推与动规,STL,图的连通
「BZOJ3747」[POI2015] Kinoman
Description共有m部电影，编号为1~m，第i部电影的好看值为w[i]。在n天之中（从1~n编号）每天会放映一部电影，第i天放映的是第f[i]部。你可以选择l,r(1<=l<=r<=n)，并观看第l,l+1,…,r天内所有的电影。如果同一部电影你观看多于一次，你会感到无聊，于是无法获得这部电影的好看值。所以你希望最大化观看且仅观看过一次的电影的好看值的总和。Input第一行两个整数n,m(1<=m<=n<=1000000)。第二行包含n个整数f[1],...
22014年12月19日5,078线段树
「BZOJ3750」[POI2015] Pieczęć
Description一张n*m的方格纸，有些格子需要印成黑色，剩下的格子需要保留白色。你有一个a*b的印章，有些格子是凸起（会沾上墨水）的。你需要判断能否用这个印章印出纸上的图案。印的过程中需要满足以下要求：（1）印章不可以旋转。（2）不能把墨水印到纸外面。（3）纸上的同一个格子不可以印多次。Input第一行一个整数q(1<=q<=10)，表示测试点数量。接下来q个测试点，每个测试点中：第一行包含4个整数n,m,a,b(1<=n,m,a,...
02014年12月19日3,652链表