Posted on 2009-11-14 21:41
王之昊 阅读(1093)
评论(2) 编辑 收藏 引用
新的一个赛季的第一场比赛。回来的时候已经开始一段时间了,再者又是我一个人做,实在是提不起什么劲来。
总共10道题:牛逼的前三家,5个小时解掉8道题。仰慕
题目
|
大致意思
|
An Industrial Spy
|
枚举 |
Common Subexpression Elimination
|
|
Divisible Subsequences
|
简单DP |
Fractal
|
分形,复数
|
Mountain Road
|
动归
|
Moving to Nuremberg
|
|
Room Assignments
|
|
Settlers of Catan
|
模拟 |
Simple Polygon
|
几何 |
Wormholes
|
|
An Industrial Spy
注意数字最多7个,能表示的最大的数是999,9999 不超过10^7,所以直接刷一个表就可以了。
假设是8个数字能表示10^8-1,那就可能只能用快速判素数来做了
Common Subexpression Elimination
最多有5万个节点,可以后序遍历这棵树,仅当左子树和右子树都用指针代替,这个树才可能用指针代替。所以用递归写起来很方便。
如果一棵树的两个儿子都是指针,这棵树就可以表示为 name + left_child_id + right_child_id ,接下去要查找这棵树之前有没有出现,
用map 或者 hash 都可以。
5万个节点。在自己电脑上标程unbuntu9.04能跑出答案,windows7暴栈
Divisible Subsequences
给你数字字符串长为n,求有多少个子串满足该子串元素之和能整除d。
对于每个x(0<=x < n)计算每个sumx = a0 + a1 + ...+ ax,如果sumx 和 sumy 同余则说明存在一个合法的串。
Fractal
分形,涉及到旋转缩放,用复数实现很方便。复数表示了二维点的所需信息,支持实数所支持的所有运算。旋转缩放也可以理解成一个乘除法。可以说复数是很奇妙的扩充。
Mountain Road
dp, 状态是dp[i][j][k] 表示从左边已过 i 辆车,右边已过 j 辆车, 最后一辆车从 k 方向过来。
dp[i][j][0] 的前继是dp[i-x][j][1] (0 < x <= i)
dp[i][j][1] 的前继是dp[i][j-x][0] (0 < x <= j) ,然后转移即可。用顺推更新后继的写法更快。
注意每辆车提供的两个属性为到达时间和路上
最小的花费,也就是说如果愿意的话可以在路上花费更多的时间。
Moving to Nuremberg
对树搞一搞
Room Assignments
simple polygon
随便选一个中心点(这里选原点),以其他点到该点的极角排序就得到了答案
Wormholes
题目大意一个特殊的存在负权的图,求最短路。这个图特殊在对于某条边,当你的总花费低于某个限制时,这条边会消失。这样就不会存在一个无穷小的花费了。题目用虫洞来描述,感觉相当有意思
解法不是很清楚,貌似是不断松弛,不断bellman-ford.但是复杂度怎么证明?