CSP-S 2019 · AFO游记

打算写一篇游记,以便以后能够回想起这段美好的颓废时光。

然而一直没有时间写游记,因为最近来机房的次数变少了。其实几周前就已经写完在草稿纸上了,而且一部分已经打到家里的笔记本上了,然后忘了保存到QQ里,因此打算再重写一篇。

内容较多,语言冗长,请见谅。

Day -1

上午一题没写,虽说有场模拟赛但并不想打。在Github和知乎上来回切换颓了一上午加一中午,中午还刷了会(低俗)微博?

下午Loli召开神圣的经验传授大会,大佬们纷纷讲话,当然好多大佬都回家休息了。轮到我时就只能说说自己的骗分和爆零经历了,然而有些想说的微不足道的注意事项上台全忘了。开完会继续颓废,然后找R一起看了一道Tarjan。

从R的一个暴力的基础上优化成可过,但是要再写多个小算法。R准备写的时候看到了我的此题的记录,好像Tarjan后只需几行(我很久前AC时大概率是抄的题解,已经全忘了),稍微一下觉得有锅,出了几组数据把暴力都hack了。又手推了几组数据想出了正确思路,然后样例过了,提交全WA。再看代码,多读入一个数字M,竟然过了样例。删去后,样例反而过不去了,一顿查错调试改了好几处小错误,终于AC了。

AC完并没有很激动,反而我们都很慌。这种错误在NOIP中年年都有,从AC到零蛋,从省队到送退役。又和R讨论发现明天此时已经快到日照了,都开始慌了。之后全员打扫机房,做好退役的准备。

晚上请假回家颓废,收拾行李。

Day 0

早上想打打板子,发现AK司在打一场名为模板题大赛的洛谷个人赛。我也跟着报名了,这大概是退役前最后一场模拟赛。看题后,发现并不是模板题,T1打了一个DFS,然后被毒瘤输出(全文比较,不忽略空格及换行)卡了,很久才通过。再看排行榜,Rank1仅通过3题,总共5题,AK司通过2题。

又看了T2,也不是模板题,而且并没有什么思路,只知道是个DP,但还需要一些性质或者其他算法结合一下。此时已经中午,先想了个三分处理就去吃饭了,回来发现还是不会。打算再意识写写的时候已经12点,该出发去校门口集合了。

然后就很正常的坐上了车,开始颓手机。

到达考点校区已经五点多了吧,先去了宿舍,和几个学弟(学长),ArachnidaKing和Juan_Feng在一个宿舍。然后去吃饭,逛超市,准备试机。

中途还与AK司讨论了上午的模拟赛,T2思路复杂,而且显然过多难以证明因此放弃,并认为CSP不会考这种智力题。

因为SDSC来过的原因,所以对校区比较熟悉,几行人就直接去了考场大楼(实验实训中心)。在楼下面LED滚动屏上还看到了祝CPS考生考试顺利!,纷纷拍照留念。这次对没来过的人挺友好的,楼内都有路标,这样绕来绕去也不会晕了。

排队进入考场,找到座号,一切顺利。系统Win7,键盘可用,调试可用。然后顺次打了快读、SPFA、LCA,打的过程中想到明天就在这看题了,就觉得又稳又慌。等到打一半模拟退火时试机结束了。我本想跑回宿舍,然而中途被带队老师叫住跟着大部队!

晚上先和学弟颓了会王者,用着极慢的网速还拿了MVP,感觉RP++了。再打开之前准备的NOIP算法索引,最后再看看代码。大概十一点半多久睡着了吧。

Day 1

进考场前都非常正常,并没有RP–的事情发生。进了考场,先建好文件夹,准备输入压缩包密码。密码是认真思考2019组合起来,等待解压,打开PDF。

先大概记了一下时限和内存,还有编译指令。顺序开题,T1题面较复杂,然而看到前一半,后一半的时候就觉得是个log做法,递归或者二分。再看到数据范围$N < 64$时发现比较稳,直接开始写代码。虽然只过了第一个样例,但是立刻发现填0后紧接着要去反,然后样例都过了。又看到数据范围$K < 2^{64} - 1$,再想到ULL最大就是这个数字,我改成ULL。又发现代码中让K自加了,因此特判了$2^{64} - 1$的点。又开始美化代码,将$(1 << i) / 2$美化成$(1 << (i - 1))$,然而比赛后才发现这竟然是个坑点,碰巧没踩中。此时大概半个小时,写了个暴力vector和string对拍一下都过了,就觉得100稳了。

再看T2,一开始觉得不可做。当看到从1出发时,才觉得可做。立刻想到一个$O(N)$的正确性未知的处理单个串做法,发现和普通的括号匹配只差了个计数。只需要维护两个计数器,遇到(清零连续计数器并放入栈内,遇到)时将计数器赋值为栈顶+1并且弹出,在维护一个答案计数器,然后按题意即可。再考虑回溯,用手工栈和系统栈结合一下就过了样例一。然而样例二没过,发现是少了一条语句,补完过了样例二。又手动开栈过了样例三,感觉很稳就没有对拍。

此时已经2h,觉得自己200比较稳,就休息了一下。看完T3题面,并没有读懂,好像读颠倒了。然而做起来只是逻辑关系更混乱了,并不影响答案。先写了个10分全排列,然后猜了个性质。想了好久,打个了个LCA+BFS,连样例二都没过,又调试微调也没什么用。全部删掉打了个随机化发现和暴力没啥区别。此时就剩整理文件、检查考号、文件名的时间了。

出了考场,遇到了asuldb和R,交流发现我T1并没有踩坑,然后T3确实很难。吃完饭回宿舍,先是和学弟颓了局王者,然而网速非常慢,全场被队友带飞。又玩了4399小游戏,玩了小学时爱玩的造梦西游3和一些小游戏。四点多的时候想起了机器人赛跑,六七个人一起玩,都非常愉悦。然而中途Loli敲门,我去开门,幸好大家反应快,只奶了几句就走了。

晚上看知乎,上午T3的出题人匿名发题解。T2被吐槽样例恶臭,而且非常水,引起了一定恐慌。再复习了些代码,十一点半熄灯,很快就睡着了。

Day1期望得分:100+100(?)+10=210

Day 2

起床,吃饭都非常正常。与ctz、ArachnidaKing走在去考场的路上,中途偶遇Loli,他拍了拍ArachnidaKing的肩膀:别着急,慢慢来。进了考场,肚子感到不适,此时离开始还有二十多分钟,又申请出了考场。回来时只剩下十几分钟了,依然是考前准备,听到密码是抓紧时间和几个字符组合。

一样的流程,顺序开题。T1看了觉得是DP,但是数据范围又很复杂,差点看晕了。计算了复杂度为$O(M^N)$的DFS,包含多个范围,能拿到32分的好成绩,那就先打上了。再仔细思考,感觉正解肯定效率也不太高。又感觉是舞蹈链,但是差别有点大,而且CSP应该不会考。

只好去看T2,题目形式化的东西看起来不可做。但是发现时自行设置划分数,就觉得没那么难。先想到一个$O(N)$预处理和统计答案时就开始写,倒序的思想,然而过不去样例二。出了几组数据hack后,发现可以用单调栈。其实是自己傻了,把栈想成先进先出了,连样例一都过不去。写了个dfs对拍,发现倒序是正确的,只是预处理有问题。然后单调栈改成单调队列依旧没有调出来,只能改成$O(N^2)$能拿64分。

此时已经2h多,计算一下两天总分刚过300,有点慌张。抓紧看了T3,看到题目名称是树的重心就知道必不是树的重心。题目描述比较清楚,暴力做法大概就是麻烦的DFS。又看数据范围,$O(N^2)$可拿40分,一条链的再多拿15分,二叉树并不熟悉,先不考虑。然后急匆匆的打完部分分,样例过了,再手推二叉树,发现连二叉树具体是啥都不知道,只能放弃。

然而比赛只剩半个多小时,回去看T1。仔细想了想,觉得自己想不出正解,想出了也写不完了,仔细思考数据范围,发现有个$O(N^M)$的DP,能多32分。但是这种DP我并不熟悉,似乎记忆化并不可行(?),大概是想简单了。写完后就离考试结束只剩十分钟了,然而样例并没有过,因为是3维数组所以不易调试(现在想想应该先打2维的)只能放弃,恢复成原来的代码。最后再检查程序、文件夹然后就交卷了。

出考场交流好像很多人都挂的很厉害,似乎我分数还行,不会被Loli强制退役?问了潮发现今天T1确实可以多维数组DP,还是自己平常没怎么打,一到正式比赛把细节都忘了。

下午觉得自己今天T1没有取摸,可能只有24分了。晚上回家又听说学弟D1T2挂了,然后我也默写提交试一试。提交后只有55分,发现是一条语句没加,导致只能处理一条链的情况。细思极恐,也不知道是默写忘了还是考场上就没加,毕竟样例又那么水。

又看了SDOI群里,听说390左右能清北冬令营?怕是自己真的就差了今天T1没打完的部分分。

Day2期望得分:32+64+55=151

Day 5+

拿下源程序,都没写挂。在Luogu和Loli的数据上测了,发现D2T2还多了24分,怕是数据水(确实是)。然后看到csp.ac的数据是361,才知道Luogu是真的数据水。。。再看牛客,大家都莫名其妙挂了分,只能等着CCF发成绩了。

Day Inf

官方成绩100+100+10+32+64+55=361,和考场上估计的一模一样。虽然这个分数也不算差,但是还是有很多遗憾。

和THUWC、PKUWC无缘了,只能盼望着CCF给我去NOIWC见见世面的机会了。

# ,

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×