爱悠闲 > 分类 >

BZOJ 第6页

BZOJ 2338 HNOI2011 数矩形 计算几何
题目大意:给定n个点,求一个最大的矩形,该矩形的四个顶点在给定的点上 找矩形的方法是记录所有线段 若两条线段长度相等且中点重合 这两条线段就可以成为矩形的对角线 于是我们找到所有n*(n-1)/2条线段,按长度排序,长度相等按照中点排序,然后对于每个点向前找符合要求的,计算面积,更新ans 注意避免一切double!长度切记不能开根号,直接用long long存储,否则第三个点有两条长度极其接近的
BZOJ 2716 Violet 3 天使玩偶 CDQ分治
题目大意:初始给定平面上的一个点集,提供两种操作: 1.将一个点加入点集 2.查询距离一个点最小的曼哈顿距离 K-D树是啥。。。不会写。。。我只会CDQ分治 对于一个询问,查询的点与这个点的位置关系有四种,我们现在只讨论左下角,剩余三个象限同理 设询问的点为(x,y),查询的点为(x',y') 则dis=(x-x')+(y-y')=(x+y)-(x'+y') 于是我们要找到查询的点左下方所有点中x
BZOJ 2599 IOI2011 Race 树的点分治
题目大意:给出N(1 <= N <= 200000)个结点的树,求长度等于K(1 <= K <= 1000000)的路径的最小边数 树的点分治,统计方法同POJ1741,不过比较讨厌的一点是最小值不支持区间减法,所以直接把所有路经长=k的方案都计入ans,然后就可以相减了,最后从左到右扫一遍即可~ 写的好慢。。。基本就是卡时过的 RANK1那家伙到底写了啥。。。 #include<cstdio>
BZOJ 1131 POI2008 Sta 树形DP
题目大意:给定一个n个点的无根树,要求找到一个根节点,使深度之和最大 令f[x]为以x为根的子树的深度之和 首先我们找到任意一个节点进行深搜,统计出每棵子树的大小,以及所有点的深度之和 然后再以该节点为根深搜一遍,此时状态从父节点转移至子节点,转移方程如下: 当我们将根节点从4节点变为5节点时,橙色部分每个点的深度+1,绿色部分每个点的深度-1 故得到状态转移方程: f[x]=f[fa[x]]+n
BZOJ 3675 APIO2014 序列分割 斜率优化
题目大意:给定一个序列,可以分割k次,每次分割的得分为两段序列的和的乘积 求最大得分 首先我们可以推出序列的分割顺序是不影响得分的 比如说我要把一个序列分割成四份ABCD 我先分割A BCD或者先分割AB CD最后的得分是一样的 证明?嗯……易证。显然嘛。哈哈。好吧我不会证。。。自己画一下推推就好 好吧这是神犇的证法:比如我将ABCD分割为AB CD 那么A就和CD各乘了一次 B也和CD各乘了一次
BZOJ 1087 SCOI2005 互不侵犯King 状压DP
题目大意:给定n*n的国际象棋棋盘,在上面放k个国王,要求国王之间互不攻击,求方案数 n<=⑨ 状压DP,将每一行的方案二进制压成一维,令f[i][j][k]为第i行用去j个国王状态为k的方案数,然后状态转移如下: f[i][j][k]=Σf[i-1][j-digit[k]][l] 其中l&k=0,l>>1&k=0,l<<1&k=0,digit[k]为k的二进制中1的个数 暴力转移即可 记得开lo
BZOJ 2208 JSOI2010 连通数 Tarjan+拓扑排序
题目大意:给定一个n个点的有向图,求有多少点对(x,y),使x沿边可到达y 设f[i][j]为从i到j是否可达 首先强联通分量中的任意两个点均可达 于是我们利用Tarjan缩点 缩点之后是一个拓扑图,我们求出拓扑序,沿着拓扑序从后向前DP,状态转移方程为: f[i][k]=or{ f[j][k] } (i有直连边到达j,1<=k<=n,n为强连通分量的个数) 鉴于每个点的值只会是1或者0,所以我们
BZOJ 2588 Count on a tree 主席树+倍增LCA
题目大意:给定一棵树,每个节点有权值,询问两个节点路径上的权值第k小 这题很卡时间。。。 树链剖分+二分+树套树的O(nlog^4n)做法可以去死了 没有修改操作,树链剖分+二分+划分树O(nlog^3n),还是死了 我怒了,裸学了一发可持久化线段树(不看任何代码OTZ,我是怎么做到的0.0),二分+主席树,O(nlog^2n),居然还是死了! 最后发现我SB了,完全没有必要二分,直接把4个参全传
BZOJ 2097 Exercise 奶牛健美操 二分答案+树形DP+贪心
题目大意:给定一棵树,可以删掉k条边,求删掉后森林中所有树直径的最大值的最小值 最大值最小,典型的二分答案 此题我们二分树的直径,每次二分DFS一次,对于每个节点统计出所有子树删边后的dis,排序,贪心删掉最大的,直到最大的两个子树相加不会超过二分的答案为止 时间复杂度O(nlog^2n) 老子的二分居然写挂了。。。桑不起啊啊啊啊 #include<cstdio> #include<cstring
BZOJ 1015 JSOI2008 星球大战 starwar 并查集
题目大意:给定一个无向图,求联通块个数,以及k次每次摧毁一个点后的;联通块个数 将边和摧毁的点全记录下来,反着做即可。 注意被摧毁的点不能算作联通块 #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define M 400400 using namespace std; struct abcd{