一转眼间又半个星期过去了,记忆已开始有点模糊了。于是赶紧把它记录下来,以免让其随岁月的流逝而消失。
第一幕 出征
思绪回到了11月19日的下午,我辞别了熟悉的东校区,匆匆地踏上了征途。兵马未动,粮草先行。而大姑娘上花花轿——头一遭的我却没有丝毫的准备,于是只好在火车站随锋哥去大快活(?)买了一个盒饭,¥21哦~~确实蛮心痛的,不过出品还挺好,两块又大又香的牛扒减轻了我的心痛感。
路上比较无聊,锋哥、Shoit、Goffe、辽哥几个赌徒一直就在打牌,我就随便找些什么趣味数学的闲书来打发时间。一路上倒也没有饿着,那全归功于我碰巧带上的三只大苹果和一盒牛奶。虽然比较单调但也算是有滋有味,不过怎看怎像某减肥女生的食谱,对我可怜的增肥计划来说倒也是一个噩梦。
有话则长,无话则短。转眼间已到了20日的下午,经过了22个钟的旅途后,我们已站在火车站前,呼吸着比广州低10度左右的空气。我们下榻的是一间叫“良安大酒店”的号称四星的酒店(郭老语),离地铁站很近,大大方便了我们的出行,于是我们当晚便决定到传说中的南京路一游。这是一条跟广州的北京路颇类似的步行街,而且很长,一直通往外滩。在路上不时有仿旧式火车的观光车叮叮咚咚地驶过。Goffe哥哥BG了我们每人一个雪糕,在冬天吃雪糕简直是爽歪歪了。
第二幕 试机
第二天早上是开幕式,没什么好说的。饭后是试机。一试就发现一个大毛病:键盘的Enter键能按下去却不能弹起来,于是便马上要求更换。试机的题都是老题,有两道比较简单,剩下一题却超难(大意是给你三堵指定长度的墙和一条指定路径,要你构造一个以该路径为最短路的迷宫。)结果全场有人做没人过。晚上郭老说上大人不要楼教主BS他们,弄了些不是人做的题目来,现在看来他们连试机也要给楼教主一点颜色看看。
试机过程中我没有敲题,而是反复在测试比赛的环境。具体配置就不赘述了,由于我们训练时都是用gedit,我就把它的选项全部摸了个遍,发现它的功能比集训用的好多了:语法高亮、行号显示、括号提示等等应有尽有,这么看来我倒可以对自己好些了,至少可以使用editplus而不用老逼自己用notepad了。大部分时间再测试那个C++库,比赛的说明文档摘自www.cppreference.com,使用GNU C++ 4.1.1,奇怪的是里面明明有hash_set、hash_map的实现,不知为何就是用不了。
第三幕 比赛
22日上午10点,比赛正式开始,我看前面,Goffe看中间,Shoit看后面。Goffe先上去设置选项,有好几项没有设,我不习惯,又上去调了一下。便开始看题,发现A题很水,便敲了,WA了,理解错了,改了,过了。于是看C,感觉应该是简单的树状动规,但前提是题目必须给出的是一棵树,而这在题目上恰恰没有明确说明!于是给Shoit继续理解去了,然后听Goffe讲D题题意,题意很简单清晰,给出100个平面上的点,求作一矩形,使矩形上的点数最多,输出点数。于是马上用O(n^4)的算法试一下(n=100嘛),TLE了,Shoit就叫我到一边去想想能不能预处理一下降低复杂度。他就去敲C,Goffe想I。马上发现其实D题的O(n^3)动规很容易想,也很好写,算法大致如下:
先离散化,然后对y方向求部分和,也就是使得与y轴平行的线段能O(1)地求出其点数,然后顺着X方向动规,设m[j][k]是(i,j)点与(i,k)点上的“冂”形折线段上最多的点数,s[i][j]-s[i][k-1]是(i,j)到(i,K)连线段上的点数,于是有maxRect=max( maxRect, m[j][k]+s[i][j]-s[i][k-1] ),m[j][k]=max( m[j][k]+ hasPoint[i][j]+hasPoint[i][k], s[i][j]-s[i][k-1])。
交上去返回WA,然后重读题目,按另一种理解交还是WA,便退下来慢慢找bug。这时Shoit和Goffe都先后搞定了手上的题,于是便让我慢慢调。我和Goffe出了好多组数据都没有找到错,于是初次参赛的我便有点浮躁,说不如乱改乱交吧,幸好被两位队友制止了(还好没成为千古罪人)。这时Goffe在帮我出数据,Shoit在反复帮我看程序,却也看不出什么毛病。无奈之下Shoit重写了一次,也是WA,便让我继续出数据测试。皇天不负有心人,终于给我找到一种退化情形的数据,稍改后便yes了。最后拿到银牌,郭老看起来很高兴,不过自己却一直暗暗惭愧——差点就成了全队的罪人了~~
第四幕 游玩
弹指之间,比赛已成为过去,照例是要认真体验一下上海特色的生活。如果从这个方面来想那今天实在是过于完美了。首先我们就领略到上海最典型的天气。在我们唯一能玩的一天里,阴雨竟下了大半天,整个上海都被云雾笼罩着。我们走外滩,看到的都是一片“高耸入云”的不太高的建筑;上东方明珠,更有一种“腾云驾雾”的感觉;上东方明珠前还有一个小插曲——游览了一条最“名副其实”的海底观光隧道——变幻莫测的激光把我们照了个目瞪口呆。然后我们还领略到上海最典型的服务员态度——基本上百分之九十九点九都是爱理不理的,在她们口里听得最多的是一句没有任何感情色彩的“当心!”,也不知道算不算中国特色社会主义。不过上海的治安看上去蛮好,从我们问路时路人们比较热心的态度可以看到出来。尽管在上海读书的欣茵同学表示反对——她有一次连问十多人都无人搭理的可怜遭遇。
午饭之后,我终于用电话联系到欣茵,本来在实验室有点事要忙的她一听到我来了上海,便说要出来陪我游玩(感激涕零!)。顺便提一下,那可恶的老天爷整天都在演绎着上海的经典天气。我们先去了淮海路——欣茵说是上海最奢华的地方。在那里,有很多高档的商场,要进去逛逛是需要一点儿胆量的,呵呵~~然后是城隍庙。看见的是一派仿古的建筑,在灯光的点缀下显得金碧辉煌。那里有很多家金店,还有很多卖地道上海小吃的店铺,不去实在可惜。
第五幕 归途
与昨天的阴雨绵绵形成强烈的对比,今天阳光普照,万里无云。可惜我们无法领略到太阳底下上海的风采,匆匆地收拾好行李,在大快活吃了一顿午餐,便登上了回广州的火车。与去时只需要走22小时的K100次列车不同,回来坐的是一辆声称需要28小时的K47次列车。说是“声称”,是因为它实际上的用时远不止这个数目,特别是进入广东,过了韶关之后,这部本不比汽车跑得快的火车还常常要停在路边让后边的火车先通过,简直用“一步一停”来形容都不以为过。有人说,这是因为晚点的车要让准点的车先过,晚得多的车要让晚得少的车先过。结果我们就被一拖再拖了。
posted on 2006-12-04 14:54
踏雪赤兔 阅读(748)
评论(8) 编辑 收藏 引用 所属分类:
岁月如歌