爱悠闲 > 分类 >

BZOJ 第33页

BZOJ 3881 Coci2015 Divljak fail树+树链的并
题目大意:给定两个字符串集合S和T,初始给定S集合中的所有字符串,不断向T集合中添加字符串,以及询问S集合中的某个字符串在T集合中的多少个字符串中出现过 神题- - 首先对S集合的所有字符串构建fail树 T集合中每加入一个字符串,我们就将这个字符串在AC自动机上跑一遍,并记录经过的所有节点 根据fail树的性质,这些节点到根路径上的所有节点的并集的出现次数都加了1 因此我们要求的就是树链的并 求
BZOJ 3876 AHOI2014 支线剧情 费用流
题目大意:给定一张拓扑图,每条边有边权,每次只能从第一个点出发沿着拓扑图走一条路径,求遍历所有边所需要的最小边权和 有下界有源汇的最小费用流 裸的。。。 建图如下: 对于每一条边权为z的边x->y: 从S到y连一条费用为z,流量为1的边 代表这条边至少走一次 从x到y连一条费用为z,流量为INF的边 代表这条边除了至少走的一次之外还可以随便走 对于每个点x: 从x到T连一条费用为0,流量为x的出度
BZOJ 1560 JSOI2009 火星藏宝图 动态规划
题目大意:给定一个m*m的矩阵,上面有n个点,每个点上有一个正的收益,在两个点之间走的代价是距离的平方,求(1,1)到(m,m)的最大收益 直接排序并且DP的方法很容易想到 但是显然O(n^2)过不去 考虑平方的特性 由于A和B都大于等于0时(A+B)^2>=A^2+B^2 因此A->B->C一定比A->C更优 根据这个特性,我们可以将点按照纵坐标为第一键值,横坐标为第二键值排序 对于每一列我们维
BZOJ 1069 SCOI2007 最大土地面积 旋转卡壳
题目大意:给定一个点集,任选四点构成一个凸多边形,求面积最大的凸多边形 枚举四边形的对角线,每次固定一个点,扫对角线上的另一个点 每次找到对角线两侧离对角线最远的点,由于两边的点的移动是单调的,因此可以用旋转卡壳维护 此外四边形的面积用对角线叉积的绝对值除以2就可以算出来了- - #include <cmath> #include <cstdio> #include <cstring> #incl
BZOJ 1185 HNOI2007 最小矩形覆盖 旋转卡壳
题目大意:最小矩形覆盖 首先有一个结论:凸包上一定有一条边与矩形的一条边重合 证明:如果不存在一条边与矩形的一条边重合,那么我将这个矩形旋转一下一定会比之前更小 于是我们枚举其中一条边,对其余三个点卡壳即可 这旋转卡壳写的真叫一个卡壳- - 还好1A掉了- - #include <cmath> #include <cstdio> #include <cstring> #include <iostr
BZOJ 3316 JC loves Mkk 二分答案+单调队列
题目大意:给定一个环,要求在这个环上截取长度为偶数且在[L,R]区间内的一段,要求平均值最大 看到环果断倍增 看到平均值最大果断二分答案 看到长度[L,R]果断单调队列 对数组维护一个前缀和,对前缀和维护单调递增的单调队列 每扫过一个数sum[i],将sum[i-L]加入单调队列,再把距离i超过R的点删掉 长度为偶数?对奇数位置和偶数位置分别维护一个单调队列即可 每次找到大于0的子串之后记录一下分
BZOJ 1090 SCOI2003 字符串折叠 动态规划+Hash
题目大意:给定一个字符串,求按照题中所给的压缩方式最短能压缩到多长 区间DP 令f[i][j]表示[i,j]区间内的字符串最短能压缩到多长 普通的区间DP:f[i][j]=min{f[i][k]+f[k+1][j]} (i<=k<=j-1) 此外如果对这段字符串进行压缩,那么我们可以枚举循环节,用Hash来判断 如果k是一个循环节,那么有f[i][j]=min(f[i][j],f[i][i+k-1
BZOJ 3772 精神污染 可持久化线段树
题目大意:给定一棵树和树上的m条路径,求这m条路径中任选两条不同的路径时其中一条包含另一条的概率是多少 这题还真是精神污染- - 首先一个显而易见的结论就是如果路径A包含于路径B 那么就有A的两端点在路径B上 这是个充要条件 于是我们对于每个A路径的两段点x和y,将x开一个vector,把y存进去 这样对于每个B路径 我们要找的就是B路径上的所有点在vector中有多少出边也在这条B路径上 有些拗
BZOJ 2458 BeiJing2011 最小三角形 计算几何+分治
题目大意:给定平面上的一个点集,求这个点集所能组成的周长最小的三角形 与平面最近点对一个道理- - 这个题也是分治做法 做法如下: 1.记录全局答案ans 2.将所有点按照x值排序 3.定义Solve(l,r)为处理[l,r]区间内的最小三角形 4.对于每层Solve(l,r),将当前区间分成左右两部分,分别递归处理 5.两侧的最小三角形都以处理完毕,现在我们要处理的就是两区间之间的点构成的三角形
BZOJ 3251 树上三角形 暴力
题目大意:给定一棵树,每个点上有点权,多次修改点权,以及查询两点间路径上所有点权之间能否找出三个值构成三角形的三边长 被逗了- - 首先考虑如果一些数不能构成三角形的三边长,那么这些数最多有多少个? 显然当这些数构成斐波那契数列的时候数值的个数最多- - 那么2^31以内共有多少个斐波那契数?46! 也就是说当两点间路径上的点>=47时答案一定是YES! 那么小于47时只要暴力就行- - 时间复杂