Posted on 2007-04-02 00:04
oyjpart 阅读(1613)
评论(9) 编辑 收藏 引用 所属分类:
ACM/ICPC或其他比赛
4月1日 校赛初赛开场，对我而言，这是人生中第一次ACM现场赛 总算没有丢师傅，大哥的脸，呵呵~~
序幕：
3.31 TopCoder TCO大赛 预选赛第二场 说起来很不好意思的就是第一场预选赛竟让没有通过。。第二个500分的题目害怕枚举算法超时，采用分类计算，结果代码敲得很糟糕，导致最后分数只有第一题的分 尽管在challenge环节中拿到宝贵的50分 可是还是没拿到复赛的入场券 昨天晚上第二次预选 终于正常一点发挥 无惊无险的进入复赛 看来要在TCO中加加油了 呵呵
4.1日早晨 昨天晚上3点多钟TCO比赛才结束 于是打算第二天早上睡大觉 然后下午就有精神去比赛了 谁知道早上8点就醒了 于是就开始起来想想下午的比赛 当时想出一个很恶毒的计划 哈哈 为自己做出了如此伟大的决定而兴奋不已 （就是我准备比赛的时候从后面做起 等别人都把前面选作了 我就跟着做前面的题目 这样就省去了选题目的时间） （后来才知道只是一大败笔 因为题目难度居然是前面要简单~~)
吃过饭突然接到郭老师一通电话 告诉我说四号院机房下午不开门。。我晕 赶紧抓上ASP赶到本部银河机房去比赛 时间很充裕 于是我们之前又去实验室拜访了一下大哥，小川，雯姐等几位大牛 然后奔赴机房~~
比赛正式开始：（比赛总时间4个小时 采用个人赛的形式）
比赛一开始我就看H题 一看 虽然是自己喜欢的图论题 但初看去可能是树形动态规划 先放放 G题吧 数学题 看上去很眼熟 但是先不乱动数学题 看F题 Bessie 一看就是一个典型的Dijkstra() 于是开始狂敲代码 大概10来分钟的时候提交了第一个题目 结果返回 Wrong Answer 郁闷 一想咋Dijk都写错啊 翻翻standing 一看A题已经10多20人过了 faint！A题啥子题？赶紧做了它！大概意思就是问x的哪一个倍数所有位为1？ 一个取余*10 的循环就可以轻松解决 2分钟后代码提交AC 接着开始看E题 看了看 是个广搜的题目 准备写 突然发现排名里面第一名居然已经3题了！顿时大喊失策失策！放下E题 开始追逐第一名的步伐！
这时候我发现我的排名还是超级低 心想这下就丢脸啦~~ 于是开始认真做 今天题目似乎特别难理解 那个Land & Sea的题目让我总是想起TopCoder里面一道变态的编程题 按照这种理解写了个复杂程序提交错误之后 看了N久后来才明白原来就是FLOODFILL 一顿乱敲 顺利通过 接着一看B题成了大家痛宰的题 我也来试试 稍微想了想 不久也得以顺利通过 接着后来又把那道E题广搜拿下 D题的动态规划 很快的写完之后很快的拿到WRONG ANSWER 郁闷了 由于在之前GHF几道题目和一些题意理解上浪费了些时间 虽然在1个半小时的时候4题AC 但是排名在5，6左右 看来还要努力！这个时候 我没有在那道动态规划上面纠缠 而是打开了最先写的F题 仔细读题后发现原来同2点之间可能有2条边，也就是通常我们说的重边 加上一个小小的修改 顺利AC 既然现在改成了从前往后做题的顺序 那么就继续做G题！一看题目的意思大概是求a^b的约数个数 其中a在1-2147483647之间 b在1-5之间 做法就是先求出1-65535之间的质数 我求了一下大概23000多个 然后对a进行因式分解 在乘上b 根据二项式定理 约数的个数就是各个因数的质数+1的成绩 （即每个因数取0-k个这些可能）同时要注意一些细节 1.有些数的因数要超过65536 要分开处理 2.对于0的任意次方输出0个约数 但是0的0次方要输出1 因为0的0次方=1 这个时候终于6题 比赛还有1个小时20分钟 排名升到了第二 后面几个人都5题紧跟 我知道我在罚时上面没有优势 于是赶紧开始看H题 题目大意是在一颗树上分布有一些marbles 要把这些分布到每一个节点上面一个marble 求最小步数 想了想 开始敲 提交上去居然又是Wrong Answer 看来今天Wrong Anwer粘上我了 一顿乱改之后 大概比赛结束前30分钟的时候发现题目中rooted tree的root并非确定 要预先判断根节点 改过之后 顺利AC 最后30分钟仔细看D题题目 发现自己理解错题意了 满怀信心改过之后终于8题全部AC 因为罚时的缘故排在第二名 第三名和第四名都是6题 最后一个小时出题不多
比赛经验：
多题WA之后没有慌张 多次自己的数据测试找到了程序的不足之处
不懈奋战 坚持到最后
呵呵~~ 下个礼拜就决赛了 加油~！