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

vfleaking的博客

My name is VFlea King

 
 
 

日志

 
 

省选前衡八题目汇总梳理(1060-1069)  

2012-04-14 22:28:18|  分类: 衡阳八中 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
今天题目描述我不想说了囧……因为都说不清楚……自己看题吧。
1060:时态同步:这题是贪心,由于标程没开long long,所以部分数据错误,导致我A不掉这题。后来……不也把long long改int,AC了。

下面都是NOI2008的题,真心纠结,解法说不清楚……见谅……
1061:志愿者招募:根据题目,引入新的变量把不等式转等式,然后把这坨等式搞成流量平衡条件,最小费用最大流即可。超清晰的题解:http://www.byvoid.com/blog/noi-2008-employee/
1062:糖果雨:此题纠结了我整个WC……大概写了6天吧……这题是数形结合的题,把云抽象成平面上的点,然后分类讨论在什么情况下能看见云,得到8个不等式,于是就成了求平面上满足其中任意一个不等式的点的个数。貌似仍然不可做……然后发现,平面上满足不等式的地方是四个平行四边形!然后变成了平面上有一堆点,求在给定的四个平行四边形内点的个数。然后,把原图分为两个,一个点由(x,y)变为(x,x+y),另一个由(x,y)变为(x,x-y),然后四个平行四边形全变成了矩形。点都是整点,因此用二维树状数组解决。
1063:道路设计:树形DP。
1064:假面舞会:首先先构个图,然后各种讨论……
1065:奥运物流:首先图肯定是一个环,环上长着很多树。其实就是求每个点的“贡献值”之和。然后自己推推公式,发现计算每个点的贡献值是相同的。然后可以发现,要改的话最优就是改到根上去。接下来就是树规了。
(NOI2008系列结束)
1066:蜥蜴:拆点,构图,然后最大流。
1067:降雨量:RMQ大纠结题!
1068:压缩:区间DP即可。
1069:最大土地面积:首先一上来先凸包,然后使用旋转卡壳。

知识点总结:
最大流:我用的isap。(sap是一大类算法!isap才是我们通常说的sap)
最小费用最大流、最大费用最大流:做法一:多次SPFA 做法二:转为线性规划问题,然后单纯形。(膜拜Vani)
二维树状数组:见胡伟栋论文《二维树状数组》
凸包:我用的graham scan
旋转卡壳:就是用平行线夹凸包。注意要用旋转卡壳的话,一定要求一个纯净的凸包才行。
  评论这张
 
阅读(747)| 评论(5)
推荐 转载

历史上的今天

评论

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

页脚

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