爱悠闲 > 分类 >

BZOJ 第27页

BZOJ 1821 JSOI2010 部落划分 Group Kruskal
题目大意:给定平面上的n个点,要求将这n个点划分为k个集合,使划分后任意两个集合中最近两点的距离的最大值最小,输出这个最小值 考虑这n个点之间所有的连边 我们要让长边保留 就尽量选取短边链接 于是就是求加入n-k条边的最小生成森林 由于输出下一个最小值 因此Kruskal加入第n-k+1条边时输出边权即可 #include <cmath> #include <cstdio> #include <c
BZOJ 2178 圆的面积并 Simpson自适应公式
题目大意:给定n个圆,求面积并 直接暴力套用Simpson自适应公式就行了 对于每一个x值,求出F(x)的方法是求出所有圆在直线x=x(重了233)上的截取区间 然后求区间并 返回区间长度即是F值 这样正常写就过样例了 然后 WA了。。。 尼玛我样例都过了你跟我说WA? 下面是注意事项: 1.此题卡精度 EPS要设为1e-13 设为1e-12会WA 2.标程精度不够 不能用long double
BZOJ 2822 AHOI2012 树屋阶梯 卡特兰数
题目大意:求n个矩形搭出n级阶梯的方案数 那个什么空心不能向上完全是逗你的- - 卡特兰数的应用之一- - Wiki上有说- - 具体证明不会- - 总之Python大法好- - n=int(raw_input()) temp=1 for i in range (1,n+1): temp=temp*(4*i-2)/(i+1) print temp
BZOJ 2961 共点圆 CDQ分治+凸包
题目大意:给定平面,多次插入点和圆,每次插入点时询问当前插入的点是否在之前插入的所有圆中并且至少在一个圆中 直接用数据结构维护这些点和圆不是很好写,我们考虑CDQ分治 对于每层分治,我们需要对于[mid+1,r]中的每个点求出[l,mid]中是否所有的圆都覆盖了这个点 设点的坐标为(x0,y0),那么这个点在所有圆内必须满足对于所有的圆心(x,y),(x-x0)^2+(y-y0)^2<=x^2+y
BZOJ 2226 Spoj 5971 LCMSum 数论
题目大意:给定n,求LCM(1,n)+LCM(2,n)+...+LCM(n,n) 枚举d=GCD(i,n),令F(n)为n以内与n互质的数之和 则ans=Σ[d|n]d*F(d)*n/d=nΣF(d) 现在就是F(n)的问题了 我们发现对于任意n>=3,如果x与n互质,那么n-x一定与n互质 故n以内与n互质的数能两两凑成和为n的数对,一共φ(n)/2对,故F(n)=n*φ(n)/2 注意n<=2
BZOJ 2876 NOI2012 骑行川藏 二分+数学算法
题目大意:给定n段路,每段长度为si,如果在这段路上以vi的速度匀速行驶,那么消耗的体力为ki*(vi-v'i)^2*si,求在不超过体力上限情况下的最大速度 我去年买了个表- - 去网上百度了半天一元三次方程的求根公式才发现函数是递增的- - 百度百科写的什么NM破玩应- - 好像没讲明白- - MS只要知道拉格朗日乘数法就能差不多搞懂这道题了- - #include <cstdio> #inc
BZOJ 2508 简单题 数学算法
题目大意:维护一个平面,支持三种操作: 0.加入一条直线(给的是两点式) 1.删除一条直线 2.询问到所有直线距离平方和最小的点 题解见 http://blog.sina.com.cn/s/blog_ab8386bc0101i1nj.html 我只是贴代码供参考的- - 注意我的abcdef和题解设的不一样- - 这简单题WA了两页- - #include <cmath> #include <cs
BZOJ 3238 AHOI2013 差异 后缀自动机
题目大意:给定一个字符串,求Σ[1<=i<j<=n]|Ti|+|Tj|-2|LCP(Ti,Tj)| 前两项是可以O(1)求的 我们要求的就是LCP之和 对反串建立后缀自动机 那么parent指针连成的树就是后缀树 直接在后缀树上DP就行- - 对于每个节点统计所有子树两两right集合大小乘积之和乘上这个节点的深度即可 QY神在学校讲了一天的SAM。。。 现在我觉得我还是回去学大型建筑机械吧233
BZOJ 2597 WC2007 剪刀石头布 费用流
题目大意:给定一个竞赛图,一些边没有指定方向,求一个指定方向的方案使竞赛图中三元环的数量最多 直接做不好做,我们考虑补集法 三个点之间如果不是三元环,那么一定有一个点有两条出边 于是我们可以得到ans=C(n,3)-ΣC(degree[x],2) 于是我们考虑费用流的模型 每条边化为一个点 从源点向每个点连n-1条边,流量为1,费用为0,1,...,n-2 一条边如果可以或必须成为一个点的出边 那
BZOJ 2683 简单题 CDQ分治+树状数组
题目大意:维护一个矩阵,单点修改,子矩阵查询,不强制在线 CDQ分治裸题。。。逗我。。。 同BZOJ 1176 Mokia 题解见 http://blog.csdn.net/popoqqq/article/details/39672705 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #d