爱悠闲 > 分类 >

BZOJ 第13页

BZOJ 1052 HAOI2007 覆盖问题 二分答案+DFS
题目大意:给定n个点,用三个边长相同的正方形覆盖所有点,要求正方形边界与坐标轴垂直,求正方形边长的最小值 最大值最小,很明显二分答案 但是验证是个问题 考虑只有三个正方形,故用一个最小矩形覆盖这三个正方形时至少有一个在角上 若有四个正方形该结论不成立 于是我们采用DFS的方式 每次用一个最小的矩形覆盖所有的点,枚举矩形的四个角 将正方形填进去 由于最大深度是3,所以时间上完全可以承受 #inclu
BZOJ 3545 ONTAK2010 Peaks Treap启发式合并
题目大意:给定一个无向图,每个点和每条边都有权值,多次询问从点v开始只能经过边权小于等于x的点中权值第k大 此题不强制在线,直接把边和询问都按照边权从小到大排序,初始每个节点是一个Treap的根节点 对于每个询问把小于等于这个询问的权值的边两侧的Treap进行启发式合并 然后求第k大即可 不知道是谁出了个强制在线版……回头研究一下 #include<cstdio> #include<cstring
BZOJ 2257 JSOI2009 瓶子和燃料 数论
题目大意:给定n个瓶子,选择k个,可以随便导油,问选择k个瓶子可以导出的油数量的最小值的最大值 首先易知k个瓶子能导出的油最小值一定是k个瓶子容量的最大公因数 于是问题转化成了在n个数中选择k个 使最大公因数最大 找出n个数的所有因数 排序 找出最大的且出现次数大于等于k的输出即可 #include<cstdio> #include<cstring> #include<iostream> #inc
BZOJ 1179 APIO2009 ATM Tarjan+堆优化SPFA
题目大意:给定一个有向图,每个点上有正权,求一条从起点出发到任意终点的路径,要求路上的点权和最大(一个点权只能被加一次) 首先Tarjan缩点,易知一个强连通分量内任意一个点权拿到就可以拿到强连通分量内所有的点权 然后这个图就没有环了,SPFA跑最长路即可 边数500W,所以要加堆优化 #include<cstdio> #include<cstring> #include<iostream> #i
BZOJ 2346 Baltic 2011 Lamp SPFA
题目大意:给定一个电路板,求改变最少的板子数量使电源与灯泡联通 在对角线之间跑最短路,如果需要改变边权就是1,否则就是0 注意别忘了输出NO SOLUTION #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define M 510 using namespace std; typedef pai
BZOJ 2300 HAOI2011 防线修建 平衡树维护凸包
题目大意:给定初始三个点(0,0)(n,0)和(x,y),以及若干其它点,q次询问,每次删除一个点或求一次上凸包长度 平衡树维护凸包……和cash同样的思路为何我时隔2个月后的代码整整短了150行…… 平衡树最好用set 链表的每个点存set的迭代器 直接erase很方便 这个题x值的下限和上限都是给定的 所以没有边界讨论 真赞~ 一气呵成写出来 调了一小时 尼玛加点我居然加反了0.0 #incl
BZOJ 1180 CROATIAN2009 OTOCI Link-Cut-Tree
题目大意:给定一座森林,每个点上有权值,支持以下操作: 1.询问两个点是否联通,若不连通则链接一条无向边 2.修改某个点的权值 3.询问两点间路径上点权之和,若不连通输出impossible 一道很裸的LCT,打了发模板,权当练练NOILinux的熟练度了 尼玛'p'写成'g'WA了一下午……明明LCT都没写错居然在这种逗B的位置出错…… #include<cstdio> #include<cst
BZOJ 1787 AHOI2008 紧急集合 倍增LCA
题目大意:给定一棵树,多次询问到三个点距离之和最小的点和距离 首先易知到两个点距离之和最小的点一定在两点间的路径上 于是到三个点距离之和最小的点一定在两两之间路径的交点上 然后很容易就会知道这个交点一定是其中两个点的LCA(其实是我不会证) 此外为什么不会是三个点共同的LCA呢?因为三个点共同的LCA一定是至少一对点的LCA 证明略(其实我也不会证) 然后就是枚举两两之间的LCA 求一下距离 取最
BZOJ 2330 SCOI2011 糖果 差分约束
题目大意:给定n个点和之间的大小关系,求每个点最少是多少(必须大于0) 差分约束系统,按照题目说的连边即可,记住少于和不少于的大小关系是不一样的 边集要开3倍 此外注意的是0到i的连边要从后往前连 不然TLE 坑B数据逗死我了 #include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorit
BZOJ 3685 普通van Emde Boas树 ZKW线段树
题目大意:维护一种数据结构,支持以下操作: 1 x  若x不存在,插入x 2 x  若x存在,删除x 3    输出当前最小值,若不存在输出-1 4    输出当前最大值,若不存在输出-1 5 x  输出x的前驱,若不存在输出-1 6 x  输出x的后继,若不存在输出-1 7 x  若x存在,输出1,否则输出-1 这题卡Treap,要写线段树 ZKW大法好啊 可惜我这个沙茶又写挂了…… #incl