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

vfleaking的博客

My name is VFlea King

 
 
 

日志

 
 

APIO2012 全题解  

2012-05-25 22:47:24|  分类: APIO |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
APIO考废了,非常不爽,回来果断把题目全A了。

派遣:
这道题是贪心,我考场上写的splay+启发式合并,结果忘开long long,痛失50分。(我怎么总干这种事 T_T)
有个漂亮的做法:我考场上一直想的是怎么维护前几小的值,使总值不大于m,因此想到了splay。其实根本不用这么麻烦。为什么要维护前几小的,可以维护最大的值啊!如果总值超过了m,就把最大的弹出去。因为要支持合并操作,果断用爆好写的左偏树。
截止这篇日志发表,我这道题在衡八上的用时排名第一,684ms。

守卫:
即下面的问题:
给k个忍者,要放在n个灌木丛中,你一些信息,某些区间内忍者数大于0,某些为0,问哪些灌木丛不放忍者会悲剧。
首先对于给定的条件,如果说某区间忍者数为0,那么就当这一段从来没有出现过。把所有的区间都删掉这一段。也就是——把区间进行重标号。我是利用前缀和进行重标号的。
那么接下来,专心对付那些要求有忍者的区间。如果说是下面的情况:
APIO2012 全题解 - vfleaking - vfleaking的博客
B包含了A,那么显然B是没用的家伙。
所以说我们要去掉那些包含了其它区间的区间,那么最后如果把区间按左端点从小到大排序,右端点也会是有序的。
怎么搞呢?具体办法就是用栈,按左端点递增的顺序往里丢,进去一个弹一堆。(自行YY吧)
于是最后区间肯定变成这样的了:

APIO2012 全题解 - vfleaking - vfleaking的博客
左右端点严格单调递增!
扯了这么久,现在来看看我们要面对的问题:问哪些灌木丛不放忍者会悲剧。
这是一个判定性问题,现在我们把它转成最优化问题:如果某个给定的灌木丛不放忍者,那么满足要求最少要放多少个忍者?
讨论这个问题有什么用?假设答案为ans,那么当ans>k时,这个灌木丛不放忍者会悲剧!
那么如何处理这个最优化问题?
首先来看看如果所有灌木丛都可以放忍者的情况,显然把区间从左往右扫,如果区间内有忍者就不管,没有忍者就在右端点处放一个,这个方法一定能得到最优解。
所以说我们只用考虑那些是区间右端点的点就行了。
当某个区间右端点不能放忍者时,显然在右端点往左一个的位置放忍者是最优的。(如果右端点往左一个的位置已不在区间里,那么区间长度为1,这个灌木丛一定要放忍者)(可以证明此时不在右端点放忍者,以后也放不了)
预处理一个数组f,f[i]表示i到len这些区间,最少要用几个忍者才行。(很好处理吧……)
然后从左往右扫,边扫边用prev记录下前面放了几个忍者。每到达一个区间v,就假设v的右端点不能放忍者,二分查找到第一个区间左端点>=v的区间右端点的区间u,那么如果v的右端点不放忍者,最少要使用prev + f[u]个忍者才能满足条件。如果大于了k,汇报结果。
接下来二分找到第一个区间左端点>v的区间右端点的区间w,v = w,继续循环。
问题解决了。

苦无:
这题……如果把它当成一道题就不好做了……其实这是两道题。
1.求出每个苦无的生命长度。
2.计算矩形面积并。
大家都会求矩形面积并吧……不会的话请先去AC POJ 1177(矩形周长并)
(话说我去年刚学线段树时就做了这题,然后居然是用的可能退化到O(n^2)的假冒O(nlogn)的算法A的……)
那么现在我们来看看怎么求每个苦无活了多久……(话说我也不知道我用的方法是不是标程的方法,我感觉这个算法太暴力了)
首先苦无一共有四种相撞方式:x相同,y相同,x + y相同,x - y相同。

下面我们来看看我们能干些啥。
知道哪些苦无最先相撞是很容易的,最暴力的方法就是暴力把每两个苦无都检查下,但其实根据四种相撞,把大家都排个序,检查相邻的就行,取相撞时间最早的那几个。
随着“嘭”的一声,在O(n)时间里,那几个苦无化为了灰烬……
下面我们貌似不知道该怎么做了,因为刚才的碰撞导致了有一些本来不相邻的相邻了,本来相邻的不相邻了。真是讨人嫌……
现在考虑最简单点的情况,如果在同一行、同一列、同一主对角线、同一副对角线上的苦无至多只有两个,那么一个苦无死了,至多只会影响它周围的四个苦无。常数级别的苦无个数!
如果我们能很快算出哪些家伙是相邻的,那么对于这个简单情况,只要开个堆,维护碰撞事件就行了!如果谁出车祸死了,就把周围的苦无的情况更新下,把原来和它相关的事件删了,把新的碰撞事件往堆里丢。
那么如果在同一行、同一列、同一主对角线、同一副对角线上的苦无要是很多呢?
其实也是一样的做法。把周围的苦无的情况更新下,不管原来和它相关的事件,直接把新的碰撞事件往堆里丢。但是每当遇到碰撞事件中包含了已经坠毁的苦无,就当这个碰撞事件不存在一样。(自己画个图意会下吧)
现在问题是如何快速计算出相邻的苦无。
那么……开4*4个set维护苦无编号。(后面还要乘个4因为飞向不同方向的苦无分开存)
维护编号做什么?维护编号的意义在于,我们可以用编号来描述苦无的相邻程度,所以在所有的事情开始之前,先要把苦无按x坐标排序,x相同排y坐标。
要删除苦无就删编号,要查询相邻的,就把编号v放在其它set里查询个lower_bound,然后各种迭代器++ --的纠结。
这题两题合一题,数据结构大合集,平衡树+堆+线段树,至于你觉得纠不纠结,反正我觉得纠结了。

给日本神题跪了!!
  评论这张
 
阅读(1712)| 评论(1)
推荐 转载

历史上的今天

评论

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

页脚

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