Day 1:

早上6点起床打车去车站,似乎好久没有这么早起床过了,困到不行,在火车上睡啊睡就睡到了南京。南航离南京南站很近,地铁一站就到了,在学校里看到了体验坐直升机的活动,感觉很强。报道完之后去吃了一波食堂,感觉南航食堂装修非常有情调,饭菜种类也很多,打菜的小哥很热情,看到我们用的是20元的饭票但没凑够20块,还送了饮料。

下午热身赛前没事干,给jsb传授了一些玩植物大战僵尸2的经验。热身赛的体验并不很好,机器很卡,没有我们平时习惯用的gedit,写代码的时候保存一下就会卡一会儿,一开始PC2就炸了,没法登陆,大概过了半个多小时才修好。B题是个atcoder原题,从二维变成了三维而已,C题稍微推推式子组合数搞一搞,写完之后还是没法提交,换lsmll学长写A题,PC2修好之后很快就1 Y了BCA题,然后突然发现我们似乎是唯一一个3题队,后来才知道A题好多队伍读错了题意。D题是个线段树区间加等差数列,询问的时候需要求个和式,和jsb讨论了下发现是个类欧几里得的式子,我掏出个类欧板子敲了敲,jsb写线段树部分,出了一些小细节错误,WA了2发。 AK之后来了两个校内记者来问了一些奇怪的问题。。。比如“程序员为什么都喜欢穿格子衬衫“,“担不担心发际线”之类的问题,心疼的抱柱又穿格子衬衫发际线又高的自己。

晚上去超市采购了一些能量食品,然后在宾馆翻以前的训练记录(其实是宾馆的网络太慢了,看不了番),大概十一点多一点睡觉,少了老队友reku都没人一起看非诚勿扰了嘤嘤嘤。

Day2:

正式赛的心态和练习赛还是不太一样的。早上去KFC吃了早饭,因为有些困,买了杯咖啡。

  开场我先读A题,感觉不是一眼题,接着看B,看到一半发现已经有2个队伍过A了,和jsb稍微想了会,但是好像并不会,大概到五分钟的时候A题已经被屠榜了,我们还不会,这时候已经开始有点慌了。于是只能上机去打表,然后打表程序写错了,一下子又没找到规律,把打表程序改对之后发现似乎都是先手胜,怀疑可能打表程序还是没写对,打印了一发在边上看,jsb先写J题。大概快半个小时的时候,才确认了A的做法,好在1Y了。这时候榜上D、G和I题都有队伍过了,I题是个非常明显的网络流,于是把机位让给lsmll学长,我和jsb在边上推G题的式子,结果不知道哪里少计数了,WA了一发后决定打表,很快发现答案就是个组合数。过了G和I之后榜上第一页终于出现了我们队。。。D题想不到什么很好的办法,jsb打算直接上模拟退火试一试。我去看M题字符串题,一开始其实有些抵触做字符串题,因为我完全不会后缀自动机之类的东西,稍微想了想发现原来是个傻屌题,把做法给lsmll学长确认了一些感觉没啥问题,大概需要一个马拉车和扩展kmp,但是字符串题平常都是jsb写的,我和lsmll学长基本没有碰,所以打算让jsb写完D后接着写M(甩锅成功)。我和lsmll学长接着讨论构造题K题。我感觉只要不断暴力随机两个人,用最少的步数让他们合并到一个格子就好了,最少的步数可以四维状态BFS出来,但是步数不会算,题目限制 50000步以内,应该卡不掉,和lsmll学长说了做法,觉得可行,但是有些难写,于是果断甩锅给lsmll学长写。

  中途jsb去厕所,让我帮忙抄扩展kmp的板子,写完之后直接过了样例,O(n)的做法交上去蜜汁TLE了。jsb对了下扩展kmp的板子,没发现错,于是怀疑是手写的马拉车部分写错了,看了十多分钟也看不出来。然后我再次看了下扩展kmp板子,发现我抄错了一个字母,改正后就过了(背锅)。l 之后看榜B大概有两三个队伍过了,H和L题都只有一个队伍过。B题虽然过的队伍比较多,但感觉是我们不知道的套路,我们商量了一会打算放弃,于是jsb想H题,我去想L题。我想到L的一个转化,把X看成1,Y看成2,其他数看成0,问题转化为给出一个只有012的数,每次可以把一个数挪到任意位置,要求最终序列不能有相邻的两个数一个是1一个是2. 然后考虑哪些数被挪过,这时候其实只要关心有多少个0被挪过,以及剩下的数中有多少个12相邻,dp的模型就很显然了。和jsb说了之后觉得可行,lsmll学长又非常稳健地写完了K题,1Y,我和jsb也把细节差不多讨论清楚了,感觉让我写代码不太稳,容易出现蜜汁错误,于是又把jsb赶上机,又是1Y。时间大概还剩下一个小时,在E题和H题之间徘徊了半个小时,最后半个小时大致搞出了E的做法,但是细节有些痿,jsb和lsmll学长轮流上机,写完过了样例就没时间了,用力提交了几发,可惜最后还是WA了。

  感觉比赛中出现的问题还是不少的,比如A题看到被屠榜还没想出来,心态就有些不对,没法冷静思考。G题明显很容易打表的,非要自己推式子,结果还推错了。M题抄错板子又没检查出来等等。如果这些小地方都做到完美,至少罚时可以优秀一些,甚至能腾出更多的时间给最后的E题。 另外也有运气好的一面,比如L题只有两个清华的队伍过,我们碰巧想到了。E题和L题都算是比较需要灵感的,B题则是套路,不会做说明我们掌握的姿势面还不够全面,继续努力吧。

05-11 09:21