爱悠闲 > 分类 >

BZOJ 第41页

BZOJ 3613 Heoi2014 南园满地堆轻絮 二分答案/线性做法
题目大意:给定一个序列a,求一个单调不减的序列b,使max{|ai-bi|}最小 逗比题。。。。。 二分答案做法: 每次验证时从右向左扫描 如果当前数字小于等于右侧的数字,就把这个数字向上调整到极限(到达右侧的数字或调整的值到达上界) 如果当前数字大于右侧的数字,就把这个数字向下调整到与右侧数字相等 无法如此做则返回false #include <cstdio> #include <cstring
BZOJ 1570 JSOI2008 Blue Mary的旅行 网络流
题目大意:给定一张有向图,每条边每天最多经过有限次,一个人每天只能经过一条边,T个人从1号点出发,问多少天之后能到达n点 将图分层,每一天分作一层,每一层的点向下一层连边 从源点向第0层的1号点连边 每层的n向T连INF的边 从1开始枚举天数,每多一天就多建一层然后跑最大流,如果当前T个人已经能到达点n则输出答案 由于1~n的路径长度不会超过n,因此T个人排队走这条路径总天数不会超过T+n 故只需
BZOJ 3163 Heoi2013 Eden的新背包问题 多重背包
题目大意:多重背包,多次询问某个物品不能选择时以某个总价钱最多能获得多少价值 求问正解是啥QAQ 维护一个前缀多重背包和一个后缀多重背包 每次询问时 枚举前面选多少和后面选多少 暴力统计答案即可 时间复杂度O(n^2logn+nq) 这3E的复杂度居然只跑了600sQAQ 正解到底是啥QAQ #include <cstdio> #include <cstring> #include <iostre
BZOJ 2081 Poi2010 Beads Hash
题目大意:给定一个数字串,求所有的k满足当将这个数字串从左到右分成大小为k的块时不同的块数量最多 反转同构算一种 枚举k,对于每个k将不同的串插入哈希表去重 反转同构啥的每个串的哈希值乘一下反串的哈希值就行了 时间复杂度O(n/1+n/2+...+n/n)=O(nlogn) #include <cstdio> #include <cstring> #include <iostream> #incl
BZOJ 3890 Usaco2015 Jan Meeting Time 拓扑排序
题目大意:给定一张拓扑图,每条边有两个边权,求两条1到n的路径,第一条用边权1,第二条用边权2,要求两条路径长度相等且最短 注意到边权<=100,n<=100,因此一条路径的长度最大只有10000 拓扑序DP一下用bitset做就行了 #include <bitset> #include <cstdio> #include <cstring> #include <iostream> #includ
BZOJ 3885 Usaco2015 Jan Cow Rectangles 单调队列+二分
题目大意:平面上有一些红点和黑点,求一个矩形包含最多的红点,不包含黑点,在此基础上要求面积最小 首先不考虑面积最小这个条件 由于x,y<=1000 因此可以利用单调队列/悬线法搞出所有的极大子矩形 对每个子矩形可以O(1)计算出里面有多少红点更新答案 现在要求面积最小 那么我们就对于每个极大子矩形二分消去四周没有点的部分即可 时间复杂度O(n^2logn) #include <cstdio> #i
BZOJ 1409 Password 矩阵乘法+线性筛
题目大意:求p^F[n] mod q 其中F是斐波那契数列,p是质数,q<p 由于pq互质因此可以套用欧拉定理 然后就是矩乘求斐波那契的事情了- - 垃圾题卡O(√q) 求Phi的时候要枚举质数 不能一个一个枚举 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace
BZOJ 3319 黑白树 并查集+线段树
题目大意:给定一棵树,有两种操作: 1.询问某个点到根的路径上遇到的第一个黑色边的编号 2.将某条路径涂黑 首先将每条边归到它下面的点上 记录每个点到根路径上深度最大的黑点 那么将一个点涂黑就相当于把子树中所有的点的最深黑点取个max 这个用线段树就可以维护 由于一个点最多只会被涂黑一次 因此时间复杂度是O(nlogn)的   现在问题就是如何在每次修改时找到路径上所有白点 这个用并查集就可以搞了
BZOJ 1018 SHOI2008 堵塞的交通traffic 线段树
题目大意:给定一张2*n的网格图,多次改变某条边是否可用,多次查询某两个点是否联通 多(yi)年前的我看到这题的第一反应是:这题尼玛能做? 两个点之间的路径可能是这样的: 也可能是这样的: 甚至可能是这样的: 这题能写? 这题其实好写爆了 我们首先忽略第三种情况,假设所有对答案有贡献的边都在两个点的中间 那么我们以每一列为一个叶节点建立线段树 线段树的每个节点开一个二维数组a[2][2] 其中 a
BZOJ 3903 比赛 最小割
题目大意:给定一个无向图,一些点有点权,一些点的点权可以自己指定,每条边的边权为两端点权值的异或,求边权最小值 按位拆开,每一位跑最小割 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 550 #define S 0 #define T (M-1) #define INF