爱悠闲 > 分类 >

BZOJ 第44页

BZOJ 3265 志愿者招募加强版 单纯形
题目大意:同1061 不过每类志愿者能工作的区间是多段 这是卡网络流?不明 总之把1061稍微改改就能过了- - #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define INF 1e10 #define EPS 1e-7 using namespac
BZOJ 3550 ONTAK2010 Vacation 单纯形
题目大意:给定一个长度为3n的区间,要求选一些数,且任意一段长度为n的区间内最多选k个数,求选择数的和的最大值 单纯形直接搞 注意一个数只能被选一次 因此要加上xi<=1这个约束条件 不明白3n还有k<=10是为何。。。 #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algor
BZOJ 2466 中山市选2009 树 高斯消元+暴力
题目大意:树上拉灯游戏 高斯消元解异或方程组,对于所有的自由元暴力2^n枚举状态,代入计算 这做法真是一点也不优雅。。。 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 110 using namespace std; int n,m; int f[M][M],is_fr
BZOJ 3533 Sdoi2014 向量集 线段树+凸包+三分
题目大意:给定一个平面,维护下列操作: 1.插入一个向量 2.询问第l到r个插入的向量中与某个向量叉积的最大值 强制在线 首先答案一定在凸包上 而且如果y>0则在上凸包上 否则就在下凸包上 且答案在同一凸包上呈现单峰函数 满足三分性质 但是现在让我们维护某个区间内的凸包,因此我们可以使用线段树 由于凸包的合并是线性的,我们不能每插入一个点都路径维护一下 这个很好办嘛!反正包含未插入点的线段树节点一
BZOJ 3621 我想那还真是令人高兴啊 复数
题目大意:给定两个三角形,其中一个可以通过以某点为中心旋转并放缩的方式得到另一个,求这个中心 それはとっても嬉しいなって。 首先两个复数相乘的几何意义是【极角相加,长度相乘】 这两种变换正好对应旋转和放缩 那么我们不妨将所有点都放到复平面上 由于没有给定点的对应关系,故我们3!枚举这个对应关系 设其中一个三角形的三个顶点为A,B,C,另一个三角形中对应顶点为A',B',C' 设中心点为P,变换复数
BZOJ 2827 千山鸟飞绝 Treap
题目大意:自己看 首先我们可以写个哈希表来存坐标 当我们改变一个点的坐标时,被加入的集合中的点和这个点之间会产生相互的影响。。。 我们首先考虑集合中的点对这个点的影响 显然ans1是集合中的最大值 ans2是集合的大小 然后就是这个点对集合中的点的影响 首先连小学僧都知道如果一个一个改那么复杂度肯定会炸。。。 那么打个标记不就好了! 当一个点删除的时候把标记下传到节点上 一并带走即可 那么我们需要
BZOJ 2402 陶陶的难题II 二分答案+斜率优化+树链剖分+线段树维护凸包
题目大意:给定一棵树,每个点有两个坐标(x1,y1)和(x2,y2),多次询问某条链上选择两个点i和j(可以相同),求(y1i+y2j)/(x1i+x2j)的最大值 我竟没看出来这是01分数规划。。。真是老了。。。 二分答案ans,问题转化成验证(y1i+y2j)/(x1i+x2j)是否>=ans 将式子变形可得(y1i-ans*x1i)+(y2j-ans*x2j)>=0 加号两边独立,分别计算即
BZOJ 3564 SHOI2014 信号增幅仪 随机增量法
题目大意:给定长轴与x轴的夹角以及长轴与短轴的比值,求最小椭圆覆盖 把坐标变换一下,转化成最小圆覆盖 然后就是随机增量法了= = 【别问我这算法是咋回事】 #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 50500 #define EPS
BZOJ 1095 ZJOI2007 Hide 捉迷藏 动态树分治+堆
题目大意:给定一棵树,一开始每个点都是黑点,多次改变某个点的状态或询问距离最远的两个黑点的距离 《珍爱生命远离STL可是我还是可耻地用了STL系列》 传说中的动态树分治。。。其实并没有那么神嘛= = ↑别听这傻瓜瞎说这货被STL卡了一天QAQ 我们把分治过程中遍历过的重心都连起来 上一层的重心链接下一层的重心 可以得到一棵新的树 下面我们开始讨论这棵新树 显然这棵树的高度不会超过O(logn) 然
BZOJ 3435 Wc2014 紫荆花之恋 动态树分治+替罪羊树+Treap
题目大意:给定一棵树,每次添加一个节点并询问当前有多少点对满足dis(i,j)<=ri+rj 强制在线 吾辈有生之年终于把这道题切了。。。QAQ 什么?你想做这题? 1095切了么?没?去把1095切掉再说! 3065切了么?没?去把3065切掉再说! 什么?都切了?那还不会做这题?? …… 算了还是说说做法吧。。。 我们抛开那些乱七八糟的,考虑朴素做法 首先式子的形式是dis(i,j)<=ri+