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

vfleaking的博客

My name is VFlea King

 
 
 

日志

 
 

省选前衡八题目汇总梳理(1090-1099)  

2012-04-17 19:40:29|  分类: 衡阳八中 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
1090:字符串折叠:引用丽洁语:“晕。。SCOI这种类型的题目怎么这么多囧。。这道题差不多吧,也是Dp,比压缩还简单,就不说了。。”(压缩题号:1068)
1091:切割多边形:计算几何题。枚举切割顺序,然后让程序慢慢自己切……
1092:蜘蛛难题:这题本来数据有误,我把这题的数据给改对了。这道题是连通器原理的题。如果不知道什么是连通器原理……请去补物理……其实这题只要模拟水面上升的过程即可。
1093:最大半联通子图:首先强连通分量中某个点如果在最大半联通子图中,那么整个强连通分量肯定在最大半联通子图中,不然就不是最优的。所以首先缩点,然后就变成了求DAG(有向无环图)的最长路问题了。大家知道怎么做了吧……拓扑序一下,然后DP之。缩点最好用Kosaraju,此算法自带拓扑序。
1094:粒子运动:计算几何题。枚举两个粒子,暴力模拟算最近距离,然后取最小值输出即可。这题有点物理思想在里面,变换参考系让问题变简单了。
1095:捉迷藏:这道题我即使有八张嘴巴也说不清……请去膜拜曹钦翔的论文:《数据结构的提炼与压缩》
1096:仓库建设:斜率优化即可。
1097:Problem is not Available!!
1098:Problem is not Available!!
1099:Problem is not Available!!

知识点总结:
括号序列:(就是解1095时用到的)把树弄成一个序列,然后用线段树维护。神方法,秒杀树节点的距离查询。

虽然我看得见后面的题,但鉴于大家都看不见后面的题目,我的衡八题目汇总梳理到这里就要告一段落了……感谢大家对这一系列题解的各种围观……thanks!
  评论这张
 
阅读(676)| 评论(4)
推荐 转载

历史上的今天

评论

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

页脚

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