The Sun Also Rises

Algorithm, Mathematica, 计算机科学, C++, photography, GNU/Linux的讨论空间

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  73 随笔 :: 6 文章 :: 169 评论 :: 0 Trackbacks
这套题比较。。。有意思。。。

Assemble

据说是简单题

March of the Penguins
你看相传每个ice floes是有跳的次数限制的是吧。。。用经典的拆点流量限制法,每个ice floes拆成i和i',i到i'的流量上限为跳的次数,然后如果能从i跳到j连一条i'到j的边(流量无穷大)。。。点数好像有点多。。。不要客气~,dinic很快的~

Containers
推一下式子,在实数意义下可以求最值是吧。然后现在限制整数。。。上下浮动一下吧。。。

Youth Hostel Dorm
相当麻烦的状态压缩dp,还么写。。。

Escape from Enemy Territory
二分 +  bfs应该可以,或者排个序 + 并查集

Flight Safety
比较麻烦的计算几何题。大体的想法是二分答案 + judge。得知了答案r以后我们可以把整个多边形往外膨胀r个单位然后判断是否整条路线都在里面。具体实现的时候我们把整个图形拆成原来的多边形,一堆矩形(每天边对应一个矩形)和一堆圆(每个点对应一个圆),每一部分求一下航线有哪些部分在里面,最后判断是否整条航线都被包含了。。。
CODE

Summits
一道比较经典的思路题了,大体就是按照高度从高往低处理,每次合并当前高度和它周围的比它低的。最后判断每一块中能达到的最高的。
注意我合并的时候使用树形并查集,并且严格保证把低的合并到高的。。。处理的要自仔细考虑细节。
CODE

Obfuscation
字典树 + dp

Tower Parking
简单的模拟题

Walk
非常有趣的一道题。
首先我们在两点拉一条线,观察每一个封闭等高线被经过的次数。
如果某条等高线被经过偶数次,那么两点同在线内或线外,必然有办法不经过这条线。
如果经过奇数次,那么在不同侧,必须要经过一次,并且总可以有办法只经过一次。
接下来要确定经过等高线的次序。基本想法是这个顺序是唯一的,我是以最左边交到的点作为次序来排的。。。
另外关于刚好交在端点的情况需要考虑下。。。
CODE


posted on 2008-02-09 19:10 FreePeter 阅读(2531) 评论(0)  编辑 收藏 引用 所属分类: ACM/ICPC

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Creative Commons License
This site is licensed under a Creative Commons Attribution-Share Alike 2.5 China Mainland License. 本站采用创作共用版权协议, 要求署名、相同方式共享. 转载本站内容必须也遵循“署名-相同方式共享”的创作共用协议. This site is licensed under a Creative Commons Attribution-ShareAlike 2.5 License.