Skip to content

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人数来决定做哪些题。这一阶段就需要大家集思广益,通过头脑风暴式的讨论确定算法。这一阶段如果某人对讨论的内容不是太熟悉可以在一旁负责做数据。在做比较难的题的时候,不应该因罚时患得患失,只要手上的数据都能过就交。

7 Comments

  1. Wangyin wrote:

    Orz…
    很强,真的很强

    Sunday, March 23, 2008 at 21:44 | Permalink
  2. winsty wrote:

    很强大 你们的策略很正确的
    不过校赛的时候切掉所有水题之后 你会发现剩下的题ac数都不会超过10…
    1个人coding真是辛苦了…2个倒是最好…

    Sunday, March 23, 2008 at 22:00 | Permalink
  3. 夜夜夜里听雪 wrote:

    膜拜 牛。。
    //by 某高一OIER
    //while alive=true do
    // 奋斗ing;

    Sunday, March 23, 2008 at 22:07 | Permalink
  4. tianyi wrote:

    一个人coding还好啦,只是我体力还是不够,最多连续coding三个小时之后脑子就变浆糊了。还好校赛时间没有五个小时那么长。
    他们两个转C不久,写程序的准确率的确不高。他们都说我写程序时的击键速度实在是很好很强大到疯狂的程度……

    Sunday, March 23, 2008 at 22:14 | Permalink
  5. tianyi wrote:

    如果说今天的比赛还有什么遗憾的话,那就是考高精度的A题没写。除了三道水题以外,AC人数最多的就是A题了……由于没有准备足够的模板而没有写A题是挺令人遗憾的。

    Sunday, March 23, 2008 at 22:25 | Permalink
  6. LittlePig wrote:

    dd大牛太强了!!!

    Tuesday, March 25, 2008 at 18:44 | Permalink
  7. donglixp wrote:

    开始向往大学生活……

    Wednesday, March 26, 2008 at 23:16 | Permalink

Post a Comment

Your email is never published nor shared. Required fields are marked *
*
*