The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

Unfinished Battle——Astar队比赛总结

 Astar队成立已经一个多月了,还记得我们集体参加的第一场比赛是8.8号南航的官方练习赛,由于正值暑假期间,各大OJ都没有正式的比赛,所以这个比赛吸引了众多的大牛参加。我认为这次比赛对于我们队的意义倒不是比赛的结果,而是通过这场比赛我们有了初步的磨合,队员与队员之间开始达成默契。最后通过几个小时的努力,我们AC了6题,排名大概在15左右。这是我们队参加的第一次正式比赛^_^。

      当时是计划暑假至少参加两次练习比赛的,第二次的比赛本来想选择天大,后来听说8.23号有北大的月赛,于是便坚定地再战POJ了.比赛前我们分好了题,开始的时候先各自看了一会题,我时不时盯一下board,比赛开始不久我发现A题已经有人过了,于是大家一起商量了下,决定dfs暴力这道题,并且由沸腾来写这个题,其它人看别的题,过了没多久,A题AC了。我们开的第二道题是一道概率题,求安全通过不踩到雷的概率,我初步分析了下,这道题可以转化成一个递推数列的问题,我直接敲了一个递归的算法,交上去,TLE了,于是不得不考虑其他的算法。其实这道题可以用差分方程直接算出来,这样可以跳过中间的递推,大家商量后,由张俊华推公式,开始Wa了1,2次,最终AC了,由于有公式,代码非常短。这道题也提醒了我差分方程的重要性,尤其在对数列方面的题上。最终我们队AC了两题,大致排在前100位左右,比赛完后很以外的看到了“another crazy man"队 ,神奇的是,和我们队贴在一起了 呵呵。

      再来看网络赛的情况,第一场合肥网络赛。题目比较“友好”,和平时做的题目,衔接度比较大,但是也有所创新,我觉得说它完全是陈题是不恰当的。分好题之后,大家各自开始看题,我首先看到了上升子序列那道题,和阿义商量了一下,很熟悉,不过暂时没有想法,所以直接跳过看别的题,于是看到了那道计算几何,由于暑假在家里做了计算几何的专题,这样的题目做了很多,主要是叉积的运用,不过由于早已总结出模板,直接套用模板,处理了一下输入输出就过了。等过了第一题,貌似开始觉得有希望的题已经被别的队做出来了,只好开始看另外的题。这时候注意到了已经有很多人过的A题,压力比较大,刚开始的时候大家都没有什么想法,后来我想到了背包问题,大家一起讨论,阿义突然说他有想法,貌似是他见过的一道题,航电上面的,当时听到很多队说它们用N^3的算法超时了,阿义说他用的是N^2的算法,敲好了之后处理了一下模除,顺利AC.这时剩下的只有两道同构的题目还有一道通过率为0的题目,由于同构的题目以前从来没有接触,图的同构更是NP问题,几乎没有什么想法,只能上网搜索资料,后来听说窦煜峰组过了,问了一下,原来用充分条件巧妙地AC了那道题,思路并不复杂,数据比较弱而已。这次比赛给我们的启示主要出自同构的那两道题,其实有的时候并不需要使用标准算法,比赛亦有技巧可用的。像图的同构本为NP问题,既然标程都不可能使用绝对正确的算法,那么这题肯定可以使用做题技巧来解的。

      接下来,第二场网络赛,刚开始的时候非常郁闷,网络不是很好,等真正拿到题目开始做题,几乎半个小时过去了,然后看到了那道通过率比较高的hello,world,看到题目我的第一反应是汇编,不过显然不可能,后来看到每一行代表一个字符,每一行有5个16进制数,而每一个字符由5个竖行表示,应该是一个16进制数代表一列的信息,数进制转换无疑。不过正准备敲的时候,有同学发消息说这题已经过了,于是只好放弃看其他的题目。之后的1个小时,大家在看题,互通每道题目的意思,前两个小时大致弄明白了没道题目的意思,这一点我们做得很好。沸腾说题目难的话就做一道模拟题,于是他着手做了A题,我和阿义两个人同时写一道点线关系的题目。

关于那道计算几何题,我们使用的是扫描+hash,可惜一直TLE,优化了很多次,还是TLE,直到比赛结束。赛后问了下中山大学的ACMer,它们用的也是hash判重的方法,过了,不过为什么我们的一直TLE?至于沸腾的那道题,应该是很有希望过的,不过由于时间原因,最后没有写完,略微有些遗憾。

     哈尔滨网络赛,写总结之前,忽然听说了现场赛要推迟的消息,原因是为了控制流感疫情,哈尔滨的几所大学要采取应急措施,取消近期一切室内活动。不知道比赛究竟会被推到哪天进行。。。BTW,比赛开始以后,还是按照惯例,先分好题,阿义看的是后面,发现很快就有人AC了J题,我们想会不会是一个模拟题呢?于是我首先去模拟这个题,用了数组模拟然后优化,可惜TLE了,后来联想到树,不过好像已经被其他组过掉了,只好放弃,做别的题目。等大家把题目都看的差不多了,我们开了一道数列的题,我们很直观的想到了差分方程求解数列的通项公式,然后再求位数。张俊华负责推出公式,可是后来我发现发现这个想法无法实现,因为计算中会出现小数,大数模板没法处理小数。。。一时陷入了僵局。最终我们决定放弃这道题,不过时间已经所剩无多。赛后有人说这道题可以用模拟科学计算器的方法来做,这才恍然大悟。这次网络赛对大家的启示在于对题目的灵活转换上面,有的问题并不是你不能,而是你没有意识到。 爱因斯坦说的对,想象力比知识更重要。

     总结就到这里,所说的一切只属于过去,我相信,我们还会继续不断地向前走,不断地超越自我,我们的集训队也会变得更加强大。

posted on 2009-09-17 00:56 abilitytao 阅读(175) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理