Skip to content

Tag Archives: 5700XM

省赛总结

坐了一夜火车,在昨天上午十点多赶到紫金港校区,浙江省程序设计竞赛十二点即开始,OIBH队依旧。 嗯,省赛就是不一样,免费发T-shirt,还有免费的午餐和晚餐。由于预习生的缘故,我们属于观摩/旅游队,不计入最终排名。 到了机房里,看到墙上挂着的十二个不同颜色的气球就开始激动,好像都没参加过这么多题目的比赛的说。分配任务,我看A、D、G、J,tzf看B、E、H、K,ww看C、F、I、L。于是比赛准时开始了。 我对自己的四道题目各略读了一下,判断出A是极水的,D不可做,G略麻烦,J矩阵乘。于是在他们两个还没看完自己的题的时候随便就AC了A题。然后他们俩告诉我E和F极水,我看了一下先敲F,没想到挂掉了,我的判断是行末有空格,把输入的方式由gets(s)改成scanf(“%s”,s)就好了。(据说事实上是因为数据是Windows格式的换行符,嗯,对于输入输出的处理要想考虑周全也没那么容易呢。)然后敲了E,AC了。 这时秒杀题已经没有了,在我coding的时候tzf和ww讨论确定了B就是一个裸的最小生成树,没有带模板(事实上,我们没有带简单的算法的代码,比如说,带了最小树形图,但没带最小生成树),我敲了std::sort加并查集的Kruskal,迅速AC之。 接下来,摆在我们面前的是各自手中的三道可做之题,ww的小蘑菇题G,tzf的DP题H,和我的矩阵乘法J。这时,我们队的薄弱环节就暴露出来了,只有我一个coder。如果有两人甚至全部都可以coding的话,我此时做出的决策会是将连续coding了半天的我换下来做点低强度的事情,让别人coding他自己的题。但是,没有这种选择。我的决策是:让ww在纸上写G的伪代码,我敲H,J先放下。结果由于考虑不周全的错误H交了三次才过,原因应该是我的coding状态开始下降。 出去喝饮料、上卫生间、凉水洗脸,回来以后状态好了一些,写一开始就想到思路的矩阵乘的J题,在文件的第一行写上注释“I Love Tan Zhiyi!!!”(别乱想!TZY是我很喜欢的线代老师。)交了两次才AC,是因为输入处理的时候有一种特殊情况,本来已经考虑到了,但因为样例里没有,所以打算先过了样例,然后再把处理特殊情况的代码加上,但是过了样例以后就很高兴地拿去提交,忘了还有一段该写的代码没写,所以没AC。哦……我真啰唆。 ww很快就把G的伪代码写完了,也出了很多组测试数据,交给我coding。tzf推出了L的公式,两人讨论一下复杂度以后觉得可以做,又讨论K无果。我拿着ww给我的伪代码和测试数据、tzf给我的公式,在不长的时间里AC了G和L(事实上coding时还是很磕磕绊绊,没有前几题时的手感),加入到对K的讨论和思索中。想啊想,想出了用繁琐的位运算降低常数的招数,search了一下别人AC这道题的用时,觉得应该就是这样了。不过,我此刻coding手感已经极差了,调试了很久,才发现犯了局部变量未初始化的超低级错误,幸好没有乱提交,还是一次AC的。 这时候,AC了九道题的我们能选择的题不多了。C是计算几何题,我完全不会;D看起来非常难,我们都一点思路也没有;I是长达五页的蘑菇题。结合各题的提交和AC次数来看,D首先被排除,曾经钻研过计算几何的ww想到了C的O(NlogN)算法,意志坚强的tzf看完了I,觉得只是严格按照超级繁琐的题目描述coding而已。C与I之间,我,唯一的coding男,选择了写C,因为我真的不愿意去写蘑菇题的!(分享winsty关于蘑菇题的金玉良言。)从赛后的情况来看,这个选择是正确的,因为I直到最后一刻仍然是有人提交无人AC的,做出十题的金牌队伍都是比我们多了C题而已。 直到现在,我相信ww提供的精妙异常的O(NlogN)的I题算法是完全正确的,交了整整十次都没有AC,或者因为我没有实现正确,或者由于精度问题,我们都不知道计算几何题中究竟应当怎样控制精度。当然,相对于上次校赛卡在二分答案题上的OIBH队,这次我们队卡在计算几何题上,已经心甘情愿许多了。 最后一小时封rank,加上没有给我们发奖(如果我们是正式选手,应该得银奖),所以我现在也不知道我们这个不计入总成绩的队伍的最终排名,大约是12或者13吧。OIBH队在成长,仍没有克服它的致命缺陷。接下来期待暑期集训吧! 最后是用Nokia 5700 XpressMusic拍的两张照片: 为什么我拿着一本圣经?嗯,因为我新手赛rank1的那次就放了一本圣经放在键盘旁边,然后感到圣灵充满无往不胜,所以我打算以后每次参赛都把圣经拿去,作为我的……吉祥物。

2008年5月5日,凌晨

五一改短假了,但浙大有七天的“春假”,从上周一到周日,多么充实而颓废的七天啊! 拿到了新的手机,Nokia 5700 XpressMusic,非常喜欢。看重音乐功能、喜欢S60智能机、预算在两千以内,应该是满足这些条件的最佳选择了。用手机的标准来衡量,音质非常棒。照相功能比较弱,2M的镜头很烂,严重偏红,不过我对这方面的要求倒也不高。另外,“扭腰”的设计应该让所有第一次见到的人感到惊艳。完全不轻薄,这应该是目前S60智能机的共同缺点吧(SoariEz同学的超级水货E51不算的话……)。不过,最近读TAOUP,对操作系统的设计自然敏感一些,就觉得S60这目前最主流的手机操作系统令人不满的地方还是比较多。不知道BSD内核的iPhone怎么样?实在烧钱的说……我将来再买手机一定要选Unix类内核的操作系统,话说随着目前iPhone和将来Android的强势,未来Unix全面占据手机操作系统市场的可能性还是相当大的嘛,虽然目前而言Symbian仍是不二选择。 头三天,艳阳高照,陪妈妈姥姥和姥爷仔细地游览了灵隐寺、植物园、西湖几个景区。感想是……要门票的景色的确胜于免费的,飞来峰、三潭印月很赞。5700拍照就是方便快捷,随随便便就拍了好几百张……不过照的都是风景,加上摄影技术实在低能,就不发出来献丑了。遗憾是时间关系没去成白堤上传说中一百六十年历史的楼外楼…… 接下来的几天时间,除了写写马上要交的作业以外,就是在音乐和书籍中度过了。哦……好吧还有大量的上网闲逛。消耗前一段时间下载的无数音乐,以及继续更多地疯狂下载。Strauss、王若琳、Avril、Linkin Park、Tschaikovsky(疯狂喜欢啊),加上李志、陈绮贞、苏打绿、牛奶@咖啡(新了解到的,还好吧)是这几天的主旋律。极赞Ein Straussfest、Start From Here、Live in Roxy Theater、Meteora以及Piano Concerto No.1 in B flat Minor, Op.23, I – Allegro non troppo。话说名字里面带琳字的女生我都喜欢,像陈慧琳啊关之琳啊蔡依琳啊范佳琳啊林琳啊,现在又多了一个王若琳。买了社会契约论、中国历代政治得失、沉思录等一些书,不过还没开始好好看,TAOUP的进度倒是不慢。 发一张前几天的书架照供亲爱的fans们瞻仰,这几天新买的书当时还没有放上去,从中您可以看出我的阅读是多么驳杂,以及5700XM的镜头,呃,或者我的拍照技术有多么烂。 最后,今天又新手上路的说。照例发ranklist: Rank Nickname Solved A B C D E F Penalty 1 Stone Cold 3 0 62(1) 0 0 176(5) 16(1) 334 2 DD 3 0 31(1) 0 0 […]