Skip to content

Tag Archives: OIBH队

省赛总结

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

OIBH队第一次参赛记

今天下午我们OIBH队参加了POJ的一场比赛,花了三个小时做出了四道题,结果是第41名,我们对这成绩还是相当满意的。做这场比赛的地点相当ws,是……紫云四舍(女生宿舍)。这还是我从小到大第一次进入女生宿舍的说。哦……队里有女生,在哪里做比赛这种事情就随她吧,她不介意我们都跑去她宿舍我们也就不如从命了。 (以下是比赛后的随记,没什么意义的。) 3月23日比赛的过程:迅速找到最水的题B,dd队长也迅速想好了一个错误的贪心算法,第一次由于VC6的不标准而CE,把CE改过来以后WA。这时候ww在想C,tt找到了另一道水题I。于是dd放弃B去写I,一次WA是由于题意有两种理解的可能,一开始猜错了,第二次就AC。这时ww给dd说了她推出的错误的DP方程,dd才刚刚写了一点,ww就说自己的方程有问题,又说J题比较水。于是dd开始自己看J题,结果dd唯一自己看的一道题还把输出要求看错了,一次WA。同时ww和tt经过仔细讨论以后确定了B的肯定对的思路,交给dd写一次,在第三次提交里AC。接着tt给dd讲了G的题意,dd认为可以用位运算降低常数来AC。但是由于dd对位运算的确不太熟,花了不少时间写出来的程序连样例都不过,dd也没信心再去改了。下面的时间都在讨论C题,在ww的错误的DP方程的启发下,dd想到了可能用博弈论里的Sprague-Grundy定理来解。花了一些时间回忆这个定理的准确内容后,dd迅速写好了SG函数的求值过程,交上去以后WA。认为可能是SG函数的递推的边界条件给的不对,对于最初的那几个情况的SG值的不同组合尝试了好几次以后仍然WA。这时ww和tt都比较闲,dd就说我给你们讲一讲什么是SG函数好了。他们差不多理解了以后,大家便一起猜边界条件的SG值到底应该是多少。这时我们发现了队里有一位女队员的优势:我们亲爱的女队员ww同学凭借女人的直觉准确的给出了边界条件的SG值应该是f[1]=f[2]=f[3]=1、f[4]=f[5]=2,当dd抱着再一次试试看的心情点了提交后,竟然出现了Accepted,全队成员都大叫了起来。AC4题已经达到了我们的预定目标,而且余下几题的确没有好写的,就结束了比赛的过程。 校赛的分工:dd队长负责写所有的程序,tt和ww负责读题、发现水题、给出正确思路,由dd负责实现,写出来以后如果没有百分的把握就让ww看一下再交,或者让tt造各种数据来测试。如果能顺利地把所有的水题AC掉,下面主要由AC人数来决定做哪些题。这一阶段就需要大家集思广益,通过头脑风暴式的讨论确定算法。这一阶段如果某人对讨论的内容不是太熟悉可以在一旁负责做数据。在做比较难的题的时候,不应该因罚时患得患失,只要手上的数据都能过就交。

我们是OIBH队!

校赛的报名在几经延误后终于操作好了。队名很好,三个“研究生”很强大。(由于没有正式学籍不能用本科生身份报名,得到的指导意见是用“研究生”身份报名。Orz…)