爱悠闲 > 分类 >

BZOJ 第43页

BZOJ 1109 POI2007 堆积木Klo LIS
题目大意:给定一个序列,可以多次将某个位置的数删掉并将后面所有数向左串一位,要求操作后a[i]=i的数最多 首先我们假设最后a[i]=i的数的序列为S 那么S满足随着i递增,a[i]递增(相对位置不变),i-a[i]单调不减(后面的不会比前面移动的少) 这是一个三维偏序问题 要是不看题解我就真去写CDQ分治了233 我们发现i=(i-a[i])+a[i] 也就是说如果一个序列满足i-a[i]单调不
BZOJ 3594 Scoi2014 方伯伯的玉米田 树状数组
题目大意:给定一个序列,可以选择k次区间并将区间内每个数都+1,求操作之后LIS的最大值 我的做法不是标解。。。5E的复杂度为何跑的飞起。。。 首先一个显而易见的结论就是我们选择的k次区间右端点都是n时才能保证最优 知道这个我们就可以DP了- - 令f[i][j]表示前i个数上升j次的最大LIS 那么有f[i][j]=max{f[k][l]|k<i,l<=j,a[k]+l<=a[i]+j}+1 看
BZOJ 3007 拯救小云公主 二分答案+对偶图
题目大意:给定一个矩形和矩形内的一些点,求一条左下角到右上角的路径,使所有点到这条路径的最小距离最大 最小距离最大,果断二分答案 现在问题转化成了给定矩形中的一些圆形障碍物求左下角和右上角是否连通 然后就是对偶图的问题了 左下角和右上角连通等价于对偶图中左上两条边和右下两条边不连通 因此将所有相交的圆之间连边,从左上两条边广搜即可 时间复杂度O(n^2log(min(r,l)/EPS)) #inc
BZOJ 1108 POI2007 天然气管道Gaz
题目大意:给定平面上的n个黑点和n个白点,一个黑点只能和右下方的白点匹配,代价为曼哈顿距离,求最小权值完备匹配 STO OTZ STO OTZ STO OTZ ans=Σ(y黑-y白+x白-x黑) =Σy黑-Σy白+Σx白-Σx黑 然后。。。233333333333333333333 #include <cstdio> #include <cstring> #include <iostream>
BZOJ 1818 Cqoi2010 内部白点 树状数组
题目大意:给定平面上的一些黑点,其它位置都是白点,一个白点如果上下左右都有黑点就会变成黑点,求最终会有多少个黑点 语文题? 总之我们现在得到了一些横向和纵向的线段(注意线段不能包含两端点!),求出交点数后+n就是答案 我们可以将横向线段看做修改,纵向线段看做询问,那么一个询问可以拆成两个 然后我们离线做,将询问按y坐标排序,对于每个询问将y坐标小于等于这个询问的修改都加入树状数组,然后查询这个询问
BZOJ 2176 Strange string 最小表示法
题目大意:给定一个串S,求最小表示法 n<=1000W,实在不敢写后缀自动机,就去学了最小表示法= = 记得用unsigned char不然WA= = 数据真是逗- - #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 10001000 using namespace st
BZOJ 2947 Poi2000 促销 set
题目大意:给定n天,每天先插入一些数,然后取出最大值和最小值,付出最大值-最小值的代价,求n天后一共付出多少代价 堆/线段树/平衡树裸题 #include <set> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int n,m; long lon
BZOJ 3832 Poi2014 Rally 拓扑排序+堆
题目大意:给定一张拓扑图,要求删掉一个点使最长链最小,求删掉的点以及删掉后的最长链 这题真是神思路- - 首先我们建立源点和汇点 源点连向所有点 所有点连向汇点 那么图中最长链就变成了S到T的最长链 然后我们拓扑序DP求出S到每个点的最长链f[x]和每个点到T的最长链g[x] 我们令一条x->y的边的权值为f[x]+g[y] 那么这个图的最长链就转化成了所有边的边权的最大值 更进一步说 是这个图的
BZOJ 1061 Noi2008 志愿者招募 单纯形
题目大意:给定n天,第i天需要ai个志愿者,有m类志愿者,每类志愿者工作时间为[l,r],花费为ci,求最小花费 裸单纯形。。。。。 这里推荐一下wyfcyx的《线性规划与单纯形算法》 http://wenku.baidu.com/view/ce5784754a7302768f99391d #include <cmath> #include <cstdio> #include <cstring>
BZOJ 3112 Zjoi2013 防守战线 单纯形
题目大意: 单纯形*2。。。 #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define EPS 1e-7 #define INF 1e10 using namespace std; int n,m; namespace Linear_Programmi