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

vfleaking的博客

My name is VFlea King

 
 
 

日志

 
 

HNOI2012 全题解(Day2)  

2012-04-30 16:57:15|  分类: HNOI |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
三角形覆盖问题:
对于统计面积并的题……通常有以下几种做法:
1.暴力算出多边形边界……然后求面积。
2.统计每个图形不被前面的图形包含的面积……然后求和。
3.扫描线法。
在考场上,我觉得前两种全是不可捉的……于是考虑第三种。
我首先求关键高度,关键高度有三种:三角形的底部高度,三角形尖尖的高度,三角形与三角形交点的高度。把关键高度排个序,那么扫描线处于相邻两个高度之间时,三角形把扫描线覆盖的长度一定是递增或递减的。所以只要类似求梯形面积一般根据扫描线处在相邻两关键高度时被三角形覆盖的长度求出面积即可。
求某高度时扫描线被三角形覆盖的长度是O(nlogn)的。即算出每个三角形把扫描线覆盖的区间,然后排个序……。
考场上我就是这么做的,60分。

那么……算法慢在哪里了呢……
首先,求个交点慢死了。于是我改成了,从某一高度开始,不断高度++,统计面积。结果反而慢了一些……50分
再观察到求某高度时扫描线被三角形覆盖的区间慢死了,而坐标又是整数,想到可以开一个巨大无比的数组,长度为坐标范围。
于是我得到了如下算法:
首先把三角形按底部高度从小到大排序。
然后从最低处开始,用一条扫描线从下往上扫,维护扫描线被三角形覆盖的长度len。扫到某一高度时,把底部在这一高度的三角形全部插入。把原来在扫描线上,高度增加后不在扫描线上的三角形删除。
插入三角形的方法是……把那个巨大数组的[x, x + d - 1]的位置的数全部++,如果某个数原来为0,则len++。记录下三角形覆盖的区间[l, r]
上移扫描线的方法是……把那个巨大数组的所有在扫描线上的三角形覆盖的区间的右端点处的数--,如果减了之后变为了0,则len--。然后把所有扫描线上的三角形的区间的右端点--,若区间变为空,则删除这个三角形。
于是,有80分了!orz。

进一步优化的余地在哪里?其实只要加一个小剪枝。注意到最后剩下的那两个超时的点,扫描线上的三角形数最多时候是2000多,能否进一步减少?
方法就是,插入三角形时,如果发现有一个三角形包含了这个三角形,就不插入。如果这个三角形包含了别的三角形,就把那个三角形删除。
扫描线上的三角形数最多时候只有200多了!!
交到BZOJ上只用了108ms。

射箭:
囧,考试时我一眼看出这题该怎么做,就是不会写……花2个小时写这题没写出来,最后骗了个分,考完了肠子都悔青了。
这道题是裸的判断半平面交解集是否为空的问题,用随机增量法即可。但是我不会写!考试之前我还把这个算法列入了我的TODO List,结果以为不会考就没去实现。结果考了orz!我真是蒟蒻啊……
kac神犇直接求半平面交居然AC了,无限orz!!再次表示我是蒟蒻!早知道我就不写啥随机增量了,就写个裸的半平面交算了……

吐槽结束……来讲解法……
首先我们可以列出若干个不等式,即low <= ax^2 + bx <= high
然后还要注意到抛物线不可能是下面三种:
HNOI2012 全题解(Day2) - vfleaking - vfleaking的博客
 
HNOI2012 全题解(Day2) - vfleaking - vfleaking的博客
 
HNOI2012 全题解(Day2) - vfleaking - vfleaking的博客
 所以加上限制条件:a <= 0,b >= 0

那么问题变成了,给你一堆不等式,问你按顺序最多可以满足多少个。
只有a,b两个未知数,所以可以把抛物线抽象成二维平面上的一点(a, b);然后每个不等式相当于一个半平面,所以问题变成了,不断添加半平面,问什么时候会交集为空?

你当然可以暴力求个半平面交动态维护,可以过。(ym kac!!)
但是这个问题仅仅是问我们是否为空,显然有更简单的方法。
下面介绍随机增量法。
首先,我们强行加上两个限制:a >= -inf,b <= inf,(inf为很大的值)加上之前的两个限制a <= 0,b >= 0,这样我们把解限制在了一个巨大的正方形内部。
随机增量法的大体思路是,每次维护解集中b值最大的点。我们记为cur
现在考虑最重要的部分:有一个新的半平面被添加进来了。
1.如果cur在新半平面内部,那么就不管它。
2.如果cur不在新半平面内部,就重新计算cur。

HNOI2012 全题解(Day2) - vfleaking - vfleaking的博客
(图中灰色部分为半平面交集,蓝色为之前的限制,红线为新的限制,cur不在新半平面内部,显然加了红线后,cur' 才是b值最大的) 

怎么重新计算cur呢?
首先……读者先用指甲壳想一想……cur' 肯定在红线上对吧。
既然cur' 在红线上,那么它一定满足红线的解析式。所以我们可以列出a与b的关系式。懂了么?后面的事异常简单!
因为我们有了a与b的关系式,所以原来的二维线性规划瞬间变为了一维!于是重新计算cur的方法是,扫一遍前面的限制条件,解关于a的不等式,求出b的最大的那组解。

好像这个算法很慢的样子诶……最坏是O(n^2)的。
但是要知道,如果半平面是随机的,那么在加进第i个半平面时重新计算一次cur的概率等于前i个半平面交集中b最大的点在第i个半平面上的概率,等于1/i。所以算法的平均时间复杂度为O(n)!是线性的。所以对于不刁钻的数据,这个算法还是很快的。

截止我写完这篇日志,我这道题在衡八上的用时是最少的,156ms。

永无乡:
这道题的在线做法就不说了,splay+合并。(albus神犇用这个方法70分,ds神犇用这个方法90分,再常数优化一下应该能过。)
下面来说说一个离线做法——DFS序+划分树。

我们的并查集同志可以把各个点给合并起来,形成一棵树。若不带路径压缩,那么在DFS它之后能得到一个DFS序。(DFS一个节点时,先把这个节点加入序列,再按加入到这棵树的先后顺序DFS它的儿子)那么,原来的联通块在DFS序中一定是连续的一段。
于是想到了什么?划分树!解决区间K小值问题!
但是不带路径压缩的并查集有人敢用么……慢死了。
这里有个优化,由于DFS需要的是一个节点的儿子列表,而并查集需要的是一个节点的父亲。两个互不干扰,为什么不能路径压缩?
不知读者懂了我的意思没,就是说若合并两个联通块,就像普通带路径压缩的并查集一样合并v、u的祖先,然后把u加入到v的儿子列表。要路径压缩时,只修改father,不修改儿子列表。这样,你用father访问到的树是经过路径压缩的树,而用儿子列表访问到的树是未经压缩过的!这种神奇的感觉实在是……

集合选数:
贴个链接膜拜matrix67:http://www.matrix67.com/blog/archives/1850(这道题在最下方)
于是这题就是个状压DP。如果不会,请先去做BZOJ 1087 互不侵犯。
  评论这张
 
阅读(2395)| 评论(6)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

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