显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

 
 
 
 
 
 

搬家了

2015-6-26 11:32:45 阅读73 评论1 262015/06 June26

网易博客貌似没多少人维护了
bug层出不穷
于是乎
http://www.cnblogs.com/sagitta/

作者  | 2015-6-26 11:32:45 | 阅读(73) |评论(1) | 阅读全文>>

bzoj 1107 POI2007 驾驶考试egz 线段树优化轮廓线DP

2014-7-9 16:46:30 阅读396 评论0 92014/07 July9

这题网上题解貌似不多的样子 于是就决定写一篇多骗点访问量233
首先有一个很明显的性质 ——以一条纵向路作为起点
那么如果它能到达所有的路 它一定能到达最左和最右两条纵向的路
为了方便统计这样的路的数量 我们可以将所有的边反向
这样对于不加边的情况 从最左出发和最右出发能到的纵向路的交集就是这样的路的数量
接下来就是DP过程了 由于这是轮廓线DP
我们可以用F[i]记录到第i条纵向路(的底端) 至少需要添加的边的数量
然后用线段树来更新到该条纵向路的每一个纵坐标至少需要添加边的数量
(注意这里为了卡常数 线段树上并不是记录的对应区间的最小值 

作者  | 2014-7-9 16:46:30 | 阅读(396) |评论(0) | 阅读全文>>

bzoj 2234 Sgu394 Berhatton

2014-6-30 8:49:51 阅读216 评论0 302014/06 June30

好久没写数据结构题了 再不写就又要成为一个大坑了 赶快拿点什么来练手==
-----------------------------------------------------------------------------------------------------------------
首先这题在网上可以搜到的题解主要是用 坐标变换+扫描线+BIT做的
首先把每个点坐标换为 x-y,x+y 然后每个点可以影响到的范围就是以该点为中心的
边长为2*d 的正方形 然后再把每个点拆成三个 一个是该点自身(作为询问点)

作者  | 2014-6-30 8:49:51 | 阅读(216) |评论(0) | 阅读全文>>

bzoj 3319 黑白树 离线并查集做法

2014-6-24 8:15:19 阅读369 评论4 242014/06 June24

碰到一道可以不用那几种数据结构的方法做的数据结构题,于是便决定好好写下
首先 我们可以用fa记录父亲 fa2记录从该点往上走延伸到的最远点(满足两点之间的路径全黑)
然后逐渐维护到最终状态,并且记录一个时间戳(边的最早的染色时间) 
这一部分就是O(n)的
然后fa2重新利用(这点很坑的样子 大家可以新建一个数组) 
记录从该点往上走延伸到的最远点(满足两点之间的路径全白)
然后从后往前回答,并且进行维护
如果用基数排序的话,这一部分的复杂度为O(n)
大概就是这些了 细节可以看看代码

作者  | 2014-6-24 8:15:19 | 阅读(369) |评论(4) | 阅读全文>>

bzoj 3320 seq 点分治+队列

2014-6-11 16:14:22 阅读253 评论0 112014/06 June11

好久没写数据结构类题了 刚好做的一套题(似乎是去年HN集训)中有一道不错的点分治的题 便决定在做完之后把这题改改
由于很久没写点分治 遍先打了一个第一问n^2,第二问n的暴力 然后发现可以卡着时过6个点
最后 在把点分治模板题——<=k路径数 重写了一遍后 便有信心写这题了(毕竟题解中说这是“noip难度”的题)
这题只要通过那道模板题(<=k路径数)稍稍改下就可以了 只要注意两点即可
1 权值要从边上改为点上
2 贡献值要在calc函数中顺便更新
点分治后面队列就比较简单了 想到就能写出来了

作者  | 2014-6-11 16:14:22 | 阅读(253) |评论(0) | 阅读全文>>

查看所有日志>>

 
 
 
 
 
 
 
 

湖北省 武汉市 双鱼座

 发消息  写留言

 
博客等级加载中...
今日访问加载中...
总访问量加载中...
最后登录加载中...
 
 
 
 
 
 
 
模块内容加载中...
 
 
 
 
 
 
 
博友列表加载中...
 
 
 
 
 
 
 
心情随笔列表加载中...
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017

注册 登录  
 加关注