The Sun Also Rises

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

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  73 随笔 :: 6 文章 :: 169 评论 :: 0 Trackbacks
A Knights of the Round Table
模型:
给出一张图(|V| <= 1000),求所有包含在奇数环中的点。
算法分析:
对每一个连通的子图,找出图中的割点,然后这些割点可以将图分为几部分,对于每一部分,每个点都至少在一个环中,
因此如果该部分存在一个奇数环,则该部分所有点都属于一个奇数环。
对于某一个图中是否存在奇数环的问题,只需黑白染色判断是否是二分图即可~
复杂度|V| + |E|。
注意那些度数<=1的点,我的实现方法需要预先删除这些点。
CODE


The Cow Doctor
模型:
给出m个集合,里面存在n种元素。求这些集合中可以被其他集合并得到的(精确相等)。
m <= 200, n <= 300
算法分析:
设A能被其他集合B1, B2, ... Bi并得到,则B1, B2, ... Bi显然都属于A。
因此,我们可以找出所有属于A的集合B1, B2, ... Bi,求它们的并,看是否等于A。
复杂度O(m ^ 2 * n),具体实现可以使用bitset :)

C Wild West
模型:
给出n个长方体(0, 0, 0) - (ai, bi, ci),求它们并的总体积。
n, a, b, c <= 100000
算法分析:
首先想到用一个平行于xy的平面去截这些长方体。方便起见我们从最大的c开始截。
注意到保证所有长方体必定是以(0, 0, 0)点作为一个顶点的,所以平面向下移动的过程中截到的内容只增不减。
剩下的核心问题就是维护对长方形序列(0, 0) - (ai, bi)并动态报告它们的面积并。
注意到必定以(0, 0)为一个节点,所以我们每行只需要记录延伸的长度。
用线段树维护并且报告面积即可。
复杂度O(nlogn)

D Pixel Shuffle
算出目标置换,然后算出每个cycle的长度,求LCM~
Ural1024 Permutations 是一道单纯计算置换多少次可以回到原始的题。
ms就是Europe - Southwestern - 2005/2006的Pixel Shuffle,寒,欧洲人出题抄来抄去的。
uva3510

E Find the Clones
弱题,排序再扫描。

F The Warehouse
算法分析:
显然是搜索。不过似乎官方数据不会太强,如下的数据比赛的时候AC的程序就跑不出来。
8 6 1
E...2...
........
..222222
........
........
22222222
........
..2..2..
我用BFS + SET做的。似乎还可以DFS + 剪枝。
CODE


G Widget Factory
算法分析:
Gauss消元,注意判断各种情况。
复杂度O(n ^ 3)

Martian Mining
算法分析:
首先可以证明,对任一个n * m的部分,或者最后一列都用来bloggium, 或者最后一行都用来yeyenum。于是就可以dp了。
d[i, j] = 左上角的i * j部分的最大结果。
则d[i, j] = max(d[i - 1, j] + 最后一行的yeyenum和, d[i, j - 1] + 最后一列的bloggium和)
复杂度O(n * m)

I Nuclear Plants
模型:
给出一张图,求最大的平均环长度。
|V| <= 676, |E| <= 100000
算法分析:
我的算法是二分答案w, 然后将每个(u, v)边权当作w - len(u, v)来做,然后用Bellman-Ford判是否存在负权回路,存在说明可以,否则说明不可行。
另外这个题有标准算法。见CLRS

J Word Rings
模型:
经典问题了。给出一堆圆,半径只可能是r1 = 0.58 或 r2 = 1.31,求这些圆覆盖的面积和。
算法分析:
此题比赛时没有队过。
一种做法是解出所有交点连同圆的左右两边一起离散,切大条做,但传说中圆解交点误差很大……
一份解题报告中提出的做法是每次把空间一切为四然后每部分的面积加起来,递归处理。如果某一部分只和一个圆相交那么用解析的方法算出其精确值。
当每部分小到一定程度的时候用类似于撒点随机化之类的方法。


posted on 2008-02-03 21:32 FreePeter 阅读(1833) 评论(4)  编辑 收藏 引用 所属分类: ACM/ICPC

评论

# re: Central Europe 2005解题报告 2008-02-25 11:08 crackerwang
word rings 分完了之后再直接B-F好象过不了,直接SPFA好象也过不了.
我写法都直接按照书上写的,B-F是做E次.SPFA是进入队列V次.是不是有什么剪枝或者改进呢??  回复  更多评论
  

# re: Central Europe 2005解题报告 2008-02-25 17:46 FreePeter
@crackerwang
要用二分的方法过这个题需要常数写的比较小,我使用了临接表 + 估计上下界 + SPFA + 放宽二分精度(只精确到1e-3)

其实有一个标准做法,参见Introduction to Algorthms, P617, Karps' minimum mean-weight cycle algorithm.  回复  更多评论
  

# re: Central Europe 2005解题报告 2008-08-18 06:33 ecnu_zp
太感谢"圆桌骑士"的解释了。。
感激不尽. Orz  回复  更多评论
  

# re: Central Europe 2005解题报告 2008-09-27 04:09 ecnu_zp
Karps' minimum mean-weight cycle algorithm, 我的中文版,找了好久才找到。囧
379 页~~~~  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   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.