爱悠闲 > 分类 >

BZOJ 第2页

BZOJ 1493 NOI2007 项链工厂
题目大意:维护一个环,每个点有一个颜色,提供6种操作: 1.将这个环顺时针旋转k 2.沿点1所在直径翻转 3.将两个珠子互换 4.将一段区间染色 5.查询这个环上有多少颜色段 6.查询一段区间有多少颜色段 关于颜色段通用的处理方法是每个区间记录三个值,颜色段数、左端点颜色、右端点颜色,合并时颜色段数相加,如果左区间右端点和右区间左端点颜色相同则减一 然后用Splay维护区间即可 不过这题还是有一些
BZOJ 3196 二逼平衡树 树套树
题目大意:。。。BZOJ挂了自己看去 好吧既然BZOJ挂了我还是贴上来吧0.0 破服务器 维护一种数据结构,提供下列操作: 1.查询k在区间内的排名 2.查询区间内排名为k的值 3.修改某一位值上的数值 4.查询k在区间内的前驱(前驱定义为小于x,且最大的数) 5.查询k在区间内的后继(后继定义为大于x,且最小的数) 其实一开始觉得这题是划分树主席树之类的 然后去了解了一下发现完全写不了。。。 后
BZOJ 3262 陌上花开 CDQ分治
题目大意:给定一堆花,每个花有三个属性,定义一朵花比另一朵花美丽当期仅当三个值都大于等于另一朵花 定义花的评级为没有它美丽的花的数量 求评级为0~N-1的花的数量 CDQ分治的题,之前在HZWER神犇的博客里见到过,就写了写,今天BZ活了想去交才发现原来是只有会员才知道的世界。。。还好学校的大神有BZ的会员,借号交了下,半天过不去,最后发现原来我CDQ分治写脑残了。。。。妈妈再也不用担心我的学习了
BZOJ 2631 Tree Link-Cut-Tree(LCT)
题目大意:维护一棵树,提供四种操作: 1.将x到y的路径上所有的点权值+z 2.将x1到y1的边断开,然后将x2和y2链接,数据保证链接后仍然是棵树 3.将x到y的路径上所有的点权值*z 4.询问x到y路径上节点的权值和对51061取模 我就复制粘贴算了为何要重新打一遍 Link-Cut-Tree第一道功能比较全的题,比较水,水个*啊,很久以前就写完了,由于BZ挂了一直没交上去,今天交上去之后从中
BZOJ 1798 AHOI2009 Seq 维护序列 线段树
题目大意:维护一个序列,提供三种操作: 1.将区间中每一个点的权值乘上一个数 2.将区间中每一个点的权值加上一个数 3.求一段区间的和对p取模的值 2631的超^n级弱化版,写2631之前可以拿这个练练手。。。 线段树区间修改,让学校的大神指导了一下ZKW的区间修改方法,很好理解,但是代码还是快不了。。。回头再改改代码吧 可能是我写的太渣了 #include<cstdio> #include<cs
BZOJ 3282 Tree Link-Cut-Tree(LCT)
题目大意: 给定N个点以及每个点的权值,要你处理接下来的M个操作。操作有4种。操作从0到3编号。点从1到N编号。 0:后接两个整数(x,y),代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。 1:后接两个整数(x,y),代表连接x到y,若x到Y已经联通则无需连接。 2:后接两个整数(x,y),代表删除边(x,y),不保证边(x,y)存在。 3:后接两个整数(x,y),代表将点X上
BZOJ 3514 Codechef MARCH14 GERALD07加强版 Link-Cut-Tree+划分树
题目大意: 给定n个点m条边的无向图,求问当图中只有【编号在[l,r]区间内】的边存在时图中的联通块个数 强制在线 注意联通块是指联通了就是同一块,不是Tarjan求的那种块 看到这题的那一刻我就想小便有木有0.0 这尼玛怎么做?可持久化并查集? 暴力? 分块乱搞? 。。。 后来看了HZWER大神的博客才知道这种巧妙的算法0.0 太强大了 直接复制wulala的题解 讲得很清楚 不累述了 wula
BZOJ 1176 [Balkan2007]Mokia CDQ分治
题目大意: 维护一个W*W的矩阵,初始值均为S.每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数M<=160000,询问数Q<=10000,W<=2000000. POJ1195的加强版 没记错的话上午这题还没有中文题目描述的说0.0 好迅速 首先这题看到W就知道二维树状数组挂了 看到M就发现离散化了也搞不了 0.0 这题似乎是CDQ分治被发现之后第二个解决的题目。。。不过只有会员
BZOJ 2006 NOI2010 超级钢琴 划分树+堆
题目大意:给定一个序列,找到k个长度在[l,r]之间的序列,使得和最大 暴力O(n^2logn),肯定过不去 看到这题的第一眼我OTZ了一下午。。。后来研究了很久别人的题解才弄明白怎么回事。。。蒟蒻果然不能理解大神的思路啊0.0 首先维护前缀和,那么以第i个元素结尾的和最大的序列自然就是sum[i]-min{sum[j]}(i-r<=j<=i-l) 然后我们维护一个大根堆,每取走一个以i为结尾的元
BZOJ 1977 次小生成树 倍增LCA
题目大意:给定一个无向图,求严格次小生成树 这题纠结了我同学很久。。。首先如果是不严格的次小生成树(权值可以等于最小生成树),那么我们就有一个很简单明了的算法: 首先求出最小生成树 然后建立倍增LCA 枚举没进入最小生成树的边 在边的两端点的路径上寻找最大的边权 用最小生成树权值-最大边权+新边权去更新ans即可 但是这道题是严格次小生成树 那么也好办 我们记录一个次大边权 如果枚举到的边权和最大