省赛总结
坐了一夜火车,在昨天上午十点多赶到紫金港校区,浙江省程序设计竞赛十二点即开始,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的那次就放了一本圣经放在键盘旁边,然后感到圣灵充满无往不胜,所以我打算以后每次参赛都把圣经拿去,作为我的……吉祥物。



