Posted on 2007-09-19 22:44
oyjpart 阅读(1675)
评论(6) 编辑 收藏 引用 所属分类:
ACM/ICPC或其他比赛
上个礼拜6参加了湖大的邀请赛,一直没有时间写总结,终于空闲,来描画下.
分组:
ALPC T1: alpc117, alpc02, alpc12(me) (比赛中使用robust队名)
ALPC T2: alpc10, alpc25, alpc62 (比赛中使用alpc62队名)
ALPC T3: alpc05, alpc55, alpc16(比赛中使用icpc队名)
ALPC T4: alpc33, alpc07, alpc60 (比赛中使用alpcteam4队名)
成绩:(2题以上)
题目答题情况如下：
题目:
A题Cheesy Chess : 模拟题.按说深搜广搜都能过,我在最后30分钟敲的,没AC,主要原因是题意在敲之前没有理解透彻.
B题Frobenius :类似于质数筛法的思想(也可以理解成背包)把Frobenius数找出来.题目问有没有可能有超过1,000,000的Frobenius数, 其实仔细想想都可以知道 只要1,000,000之后加上10,000没有出现Frobenius数,后面就不可能出现.alpc117A掉的.
C题Mineshaft :题意很难理解,处于决策考虑,我们组最后放弃了这题.
D题Colour sequence 简单的DP,我A了.
E题Projects 还是一个DP, dp[i][j]代表前面i个工程由j个人来完成,在这个基础上作DP应该不难.注意计算概率的方式,还有这个题目可以直接用整数计算,就没有精度误差了.我敲的.
F题Booksort : 搜索+剪枝.看到题目基本上就可以明确是搜索题,而且也很好用迭代深搜来写.于是问题归结于如何剪枝.我想到了一种关于跳跃点的剪枝: 若连续的两个数不满足严格升序关系,则成为一个跳跃点(第1个数不是1或者最后一个数不是N也是跳跃点). 这样一次SHIFT操作最多只能减少3个跳跃点,也就是说2次最多减少6个,依此类推.直观的想,这个剪枝的效果应该是会比较明显的.ALPC02敲了这题,15MS宽裕的过了.
G题Oulipo : 典型的KMP,alpc117大敲一顿过了.
H题Lucky Light : 这道题我没有过问,这是我们上场敲的第一题,ALPC02 A了它,不过罚时较多.好在AC之后我们队越来越顺
I题Sightseeing : 首先是求最短路,然后分别对最短路和最短路+1做记忆化搜索.