爱悠闲 > 分类 >

BZOJ 第58页

BZOJ 1150 CTSC2007 数据备份Backup 堆+贪心
题目大意:给定一个长度为 n−1 的序列,要求选出 k 个不相邻的数使得和最小 费用流显然能跑,而且显然过不去- - 考虑用堆模拟费用流 一个错误的贪心是每次取最小,这样显然过不去样例 我们把【每次取最小】改为【每次选择一个区间取反】,用堆来维护这些区间即可 每次取出最小的区间,然后将两边合并 (比如现在堆里有[1,3][4,4][5,5])这三个区间,我取走了[4,4]并计入答案,那么我删除[1
BZOJ 2118 墨墨的等式 堆优化Dijkstra
题目大意:给定 n 个物品,每个物品有一个非负价值,问 [L,R] 区间内有多少价值可以被凑出来 好题!!! 如果物品数量可以为负,显然求个 gcd 就行了 现在物品数量必须非负 任选一个 ai>0 ,如果一个价值 k∗ai+x(0≤x<ai,k≥0) 可以被凑出来,那么显然 (k+1)∗ai+x,(k+2)∗ai+x,... 都可以被凑出来 显然如果我们对于每个 x 都找到最小的 k 满足 k∗
BZOJ 2217 Poi2011 Lollipop
题目大意:给定一个由1和2组成的序列,多次询问是否存在一个区间满足区间和= x 如果 x>sum 显然无解 如果存在一个前缀和为 x 则直接输出 否则一定存在一个前缀和 [1,i] 等于 x+1 然后我们将左右端点同时右移 显然如果某一时刻 a[l]=1 或者 a[r+1]=1 那么我们就找到解了 记录 exti 表示从 i 开始有多少个连续的 2 如果 ext1<exti ,那么解为 [1+ex
BZOJ 1449 JSOI2009 球队收益 费用流
题目大意:给定 n 支球队,第 i 支球队已经赢了 wini 场,输了 losei 场,接下来还有 m 场比赛,每个球队最终的收益为 Ci∗x2i+Di∗y2i ,其中 xi 为最终的胜场, yi 为最终的负场 求最小化收益 考虑一只球队,其收益与在接下来的比赛中的胜场数关系为: 赢 0 场 Ci∗win2i+Di∗(di+losei)2 赢 1 场 Ci∗(wini+1)2+Di∗(di+los
BZOJ 3168 Heoi2013 钙铁锌硒维生素 矩阵求逆+匈牙利算法
题目大意:给定一个 n∗n 的满秩矩阵 A 和一个 n∗n 的矩阵 B ,求一个字典序最小的 1...n 的排列 a 满足将任意一个 Ai 换成 Bai 后矩阵 A 仍然满秩 我们考虑建立一个二分图,如果 Ai 能换成 Bj ,就在 i−>j 之间连接一条边 那么这个图怎么建呢? 考虑一个行向量 Bi ,我们在 A 中找到最小的行向量集合满足 Bi 可以被这些行向量线性表出,那么显然 Bi 只能替
BZOJ 2797 Poi2012 Squarks
题目大意:现在有 n 个互不相同的正整数 xi ,两两之和共有 n∗(n−1)2 个和,现在给定这些和,求 x1,x2,...xn 最小的数一定是 x1+x2 次小的数一定是 x1+x3 由于比 x2+x3 小的数只能是 x1+xi ,因此 x2+x3 只能是第 3...n 小的数,枚举之 现在我们知道了 x1+x2,x1+x3,x2+x3 ,我们可以解出 x1,x2,x3 剩余数中最小的那个数一
BZOJ 2091 Poi2010 The Minima Game 动态规划
题目大意:给定 n 个数,两个人轮流取,每次可以取走任意一些数,获得的分值是这些数中的最小值 两个人都想让自己的分值-对方的分值最大,求最终先手得分-后手得分 显然每个人取走的都是当前剩下的数中最大的一些数 那么考虑倒着做,令 fi 表示剩余最小的 i 个数时先手-后手的最大差值 那么有DP方程 fi=max{aj+1−fj}(0≤j<i) 维护个最大值就行了 #include <cstdio>
BZOJ 1513 POI2006 Tet-Tetris 3D 二维线段树
题目大意:给定一个矩阵,初始每个位置上的元素都是0,每次选择一个子矩形,将这个子矩形内的值修改为这个子矩形内的最大值+ h ,求最终所有位置上的最大值 我们需要维护一种数据结构,支持更新子矩形的值和查询子矩形最大值 似乎二维线段树就可以了? 但是YY了一下我们会发现两个没法解决的问题: 1.标记的下传 2.信息的上传 其实。。。 第一个很好办嘛!不下传不就好了! 标记永久化,无需下传,只要查询的时
BZOJ 2216 Poi2011 Lightning Conductor 动态规划
题目大意:给定一个序列 ai ,对于每一个 i 求 ⌈max{aj+|i−j|−−−−−√}−ai⌉ 看了题解才知道是决策单调性。。。 那我这个做法可以算是乱搞了? (似乎这个做法也可以拓展到所有满足决策单调性的1D1D上?) 显然我们可以做两遍,第一遍只考虑 j<i ,第二遍只考虑 j>i 首先根号这东西有个性质。。。 n−√ 的增长速度随 n 的增大而减小。。(其实就是函数上凸) 这意味着什么
BZOJ 2926 Poi1999 空立方体问题
题目大意:给定一个空间上的 n(n≤5000) 个点,你需要输出一个点 (x,y,z) ,满足: 1. 0≤x,y,z≤106 2.不存在一个点 (xi,yi,zi) 满足 0<xi<x,0<yi<y,0<zi<z 3.在此基础上最大化 xyz 考虑二维怎么做 我们将点按横坐标排序,维护一个纵坐标单调递减的序列,那么答案一定是某对相邻点 (p1,p2) 之间的最大矩形 (x2,y1) 现在是三维,