Skip to content

Tag Archives: OIBH队

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…)