CSP – S 2019游记

这是一篇流水账式游记。

主要写第二轮。

Day -1

今天巨佬搬过来和我坐了。

打了一些板子。

然后中途写题。

一道题都不会写。

wtcl。

Day 0

上午打了一点板子。学了一下单调队列优化多重背包。到现在也还没学斜率优化，如果像去年那样考个板子就很尴尬。

下午一点就出发了。

路上听了一些以前下的歌。把一直没听清楚的歌词看了一遍。忽然好喜欢你戳。

大概三点钟的时候到了神大对面的宾馆。简单收拾了东西之后写了一道博弈论的题。然而什么都没搞懂。

房间临水，水声听起来很舒服。

五点多和其他小朋友们出去吃饭。忽然想起去年的Day 0也是这个点去吃饭的呢。（我在走到图中同样的位置时截下了这张图。比去年早了8分钟）

晚饭吃的还算好，人均43.75。

拍这张图是想拿来让偷偷跑走的另外四位神犇犇嘴馋的。一时间觉得发了也没多大意思，就没发给他们了。

虽然其实写这个游记也没多大意思…

中午没睡觉，于是晚上吃饭的时候很晕很恶心，一度感觉自己不在状态。可能我需要一瓶脉动？

不在状态的时候居然被几对情侣虐了。于是在旁边的超市买了几块巧克力。

回到房间看了B站上一个关于Vae的互动视频。

于是就到现在了。现在（20:53）在补这篇游记从到达酒店开始的部分。

教练讲了一些注意事项。

希望明早的T1不要太难吧。就当成是参加了两天的面包矿泉水自助餐了。

希望明早起来就不头晕恶心了。

希望不要考我任务列表的最后这几点未完成任务。

然后用小凶凶的微博安慰一下自己。

放平静。

Day 1

晚上醒了几次，不过也还算好。有些时候晚上睡太饱会导致第二天频繁走神。

七点钟准时起了床，在宾馆旁边的店里吃了早饭。

在某谷打了卡。居然是中吉。kkk不是说一定会大吉的么？

看来特别设定的大吉都对我无效了。

wtcl。

爆零必不可免了。

忽然收到我妈微信发来的红包。原来今天是自己的农历生日呢。

半点和大佬们一起过天桥到对面的神大。不过已经来过两次了，没有很紧张。感受也和之前差不多。真的没有很紧张。

唯一的不同是，去年NOIP和今年省选不是禁止坐电梯上楼么，现在电梯居然被人占满了。

不过我依然走的楼梯。

考场在五楼。怕到时候人多，所以先在四楼上了个厕所。心里想着就算一道题都不会做也要多嫖一点考场的面包和矿泉水。怎料刚上楼面包和矿泉水就没了。

坐到位置上忽然觉得有点奇怪：这显示器为啥是正方形的？镇定一下才想起前两次来用的显示器都是正方形的。

旁边坐了一位很小很小的妹妹，应该是小学来的吧。最开始她都不知道怎么从FTP上下载试题。

我想起去年拿到压缩包的时候，我怎么输密码都解压不了。当时用普通话问了一下旁边的选手（还没到开考时间），可惜他似乎不太想理我。可能他在担心这是一种作弊行为？

这个时候我也有点犹豫，如果我就告诉她怎么下载会不会也被判为作弊？不过旁边的一位选手咳了几声，在自己的电脑上演示了一次。可惜小妹妹还是不懂。

折腾一会之后监考老师请还没看到题的选手举手。小妹妹手太短了。我跟监考老师对视了一眼，指了一下旁边的小妹妹。

那么就仁至义尽了。

这个时候我已经打开虚拟机，然后看了几眼题。

开考时间已到，监考老师开始传草稿纸。我坐在最左边，不幸的是传到最左边的草稿纸多了一张。我拿到了两张。可能是被CCF的禁赛警告搞自闭了，这个时候我心里想的全是“多拿草稿纸会不会被当成作弊然后被禁赛啊”之类的。

可惜监考老师跑后面传纸了。一直等到检查准考证我才给他说了这事。

“你拿着就是了。”

…

然后来说说做题。

先照例打了快读的和最值更新的函数。

读T1。题面有些长，没读完的时候以为要让我生成格雷码，瞬间有些慌：T1都这么难么？

不过还是和神奇的幻方一样，题目给出了生成方法。

第一感觉是，递归下去，每次n的规模减小1不就行了。

注意到题目范围给到了。嗯，不就是unsigned long long 吗，没关系。

在NOI Linux下用测评软件测试了一下自己的程序，99，OK，不用管了。

插播一下有关T1的后续：下午没事，听说牛客网可以测测。于是靠记忆敲了一次。用yms大佬给的数据才发现一个问题：我的算法用到了这个运算。虽然结果在ull内，可惜中间结果溢出了。就必炸。交上去果然只有95分。

幸好原题也只有一个点满足。

说回考场。做完并且测完T1已经是8:55了。

然后做T2。看前两行，有点一道很经典的动态规划题（UVA1626，洛谷 P1241 ）的味道。可惜我很久没看过这道经典题了，第一次交的时候似乎也只是半懂。

不过这道题的区别在于，空串不能算作一个合法的括号串。

暂时没想到什么思路，只是隐约觉得一个位置能从前面的位置继承过来。看到有链的分，在想能不能推一个适用于链的转移方程。又想起前两天听到“大神经验分享”里，“大神”们要求无论如何都先把暴力打出来，然后再搞正解。

一时间几种选择摆在面前，还是有点慌的。但淡定了一下，决定再看看T3。然后又淡定地在虚拟机里把后面两道题的数据都配置在了Arbiter里。

这时候忽然脑海里有一个声音：这是D1啊，想想去年，应该T2是能做的吧。

于是开始专心做T2。先推了链上的情况，想到用栈来维护能和当前位置匹配的位置。既然要继承，第个位置的答案应该用之前的答案，加上以第个位置结尾的字串的答案。于是考虑用表示以位置结尾能扩展多少个。然后乱糊了一通，期间前缀和乱入了，后来发现状态转移不需要前缀和，只是统计答案需要。

然后一想，既然是树形，深度优先遍历再加上回溯，不就可以让刚刚链上的方法适用了吗？

然后测了一下在Arbiter里测了一下T2，看样子应该是过了。

看了下时间，大概是10:11。

总觉得哪里不对，又反复测了一下T1和T2，然后检查文件名和输入输出。

然后就开始干T3了。

开始以为菊花图上的答案就是，只需要不断把当前中心的那个数字放到编号相同的结点上就行了。不过似乎如果本身就在号结点上就不行了。

于是瞎搞链，乱贪心。

最后11:49才把样例的链过了。可惜第一阶梯的数据还没打暴力。

不过也懒得打了。

又在Arbiter里测了一下程序。又检查了几次文件名。差不多就颓到12:00了。

咦，我好像还没嫖到面包和矿泉水呢。

所以Day 1预估：95+100+(0~25)。也就195～210吧。

下午和几位巨佬玩了两个小时的4399大富翁。程序写的很精致，可惜设计有些问题。因为一个人死都不能破产。这个游戏似乎可以永远进行下去。

然后和lch julao玩了十几分钟森林冰火人。这个时候教练忽然来访……

教练走后在宾馆瞎逛，又遇到教练，被教练牵桥邀请和辰星凌巨佬散步。可惜辰星凌巨佬不想。

lch julao也不想。

再然后本来约了跟几位他校julao面基，后来julao不来了。我也就自己在神大里逛了逛。

天呐，好多情侣啊，我为什么要找虐。

还在神大里再次偶遇教练了woc。

lch julao等我回房间一起点外卖。于是我就掉头回了。再不回也受不了这些恶臭的情侣们了。

路上看Q群消息，同校的其他julao们出去吃饭了。

lch julao和我点了一些外卖。等外卖的时候我和他校另外两位julao在宾馆外谈笑风生。可惜他们只知道装弱。我实在无法和他们沟通了。

忽然发现这个游记的流水账太流水了。还有些细节就不谈了吧。

22:12。今天就写到这里。

Day 2

昨晚睡觉前居然流了鼻血。

看来我必然会爆零了。

大吉。

很惊喜的是外面起了很大的雾。

昨天的题把比我强一些的大佬们的分卡到和我差不多的样子了。但今天心里还是有点忐忑。

很高兴成功嫖到了场地提供的两个小面包。

和昨天完全相反。今天草稿纸传到我这里就没了。主动向监考老师要了一张。

周围没什么键盘声。我想敲，恐禁三。

于是就只是默默开了虚拟机，改了一下IDE的配色。

奶了一口今天的密码： 9Zi%Xi*DuTi! ，可惜是 抓紧时间。

非常失望。于是开始干题。

通读整个题面，T2和T3题意似乎很好懂。

但想的是T1应该能拿满吧，于是开始干T1。很可惜的是DP方程推不出来，暴力搜索打不出去。一直搞到9:40左右。开始慌了。

这个时候感觉马上要做出来了，但就是做不出来。心跳忽然加速，有一种绝望的感觉。我D2不会就这么爆零了吧。

尝试深呼吸，一度引来右边小妹妹迷惑的目光。

然并卵。

遂决定出考场走走。向老师请假上了个厕所。

回来的时候心跳差不多平静了。决定先放弃第一题。

看了下T2，打了一个的暴力。在Arbiter里测试了一下，应该可以拿到的分数。

此时大概十点多吧。

被刚刚的T1整怕了，不敢回头去做。所以开始做第三题了。

嗯，我一定不要先想正解。我一定要先打暴力。否则又会像T1那么惨不忍睹。

于是打了一下暴力。忘了打完是几点了。好像还挺早的。

又在Arbiter里测试了一下。暴力分应该稳了。

打完两道题的暴力，心情稍微好了一点。又看了一下几个特殊点，发现T3链上的情况可以做。又花了点时间打链上的分。Arbiter里测试通过。

这个时候大概是11:30。嗯，把目标定小一点就很空闲了。

这个时候心情差不多更好了，所以回头去看了第一题。最开始迟迟没把第一做出来，就是因为自己非要想把暴力优化一下。这么一想，我决定开始打 纯 暴力。时间复杂度大概是吧。过了前两个样例，开心。

可惜没过第三个小样例。

这个时候，乱检查了一下，加了一个的判断，过了。但是我想，我的这个算法加不加判断都无所谓啊。

忽然发现其实是一个地方数组只开了3的大小。虽然这个复杂度只能过的数据，但是后来我把整个数组下标右移了。

然后再次测了一下。T3有的分吧。此时大概是11:55？真险。

反复在Arbiter里测试了一下三道题，非常担心这个垃圾软件因为刷新不及时迷惑我的眼睛。手动刷新了几次，应该可以确认无误了。

今天的预估分数就是：32+36+55=123.（所以应该倒序开题！）

两天一共：95+100+(0~25)+32+36+55=(318~343)=AFO。

好了。中午吃了碗兰州拉面，回房间收拾东西，坐了一会之后就上车回学校了。

下午放假。打了支疫苗。回家。

那就等分数出来了再更。（我打赌今年CCF又会在出初评成绩的时候咕咕咕几下。）

Day 3

今天教练来文化课班里说程序已经公开了，要给我们发程序。

晚上回家发现他忘了。没发。

在几个OI群里问程序，没人有。

聪明的我想到，如果有人拿到了SC源程序，应该会在洛谷的讨论区里发吧。所以就一页一页地往前翻今天的讨论，果然看到了SC的源码。

重新下回来电报，然后在笔记本里解压。等等，为什么我的D1T1代码是空的？有文件没有代码这种。注意这里面的code是0字节。

我解压又删除了整整三次，都是一样的结果。

他说我刚刚修改过，但是我解压完就是这样子。真的没有修改过啊。而且只有00153和00154的代码是这样的。

我差点被吓死了。

然后非常淡定地打开台式电脑的Windows 10，传包，解压。

太好了，发现自己的代码还在。

在洛谷交了一发，居然有350分。我自己都不信。

在nowcoder交了一发，318，刚好是我自己估分的下限。（看上文，我估的分数是318～343，这25分的差距来自于D1T3链上的情况）

现在也就坐等官方数据公开了。

早睡身体好。

to be continued..

2019 12 04，下午第三节课到机房收拾东西 顺便更新：

1号晚上就查了分了，一直没更新这篇游记。318。果然AFO了。

这大概是最后一次所有人都坐满机房了吧。

大佬们还是和以前一样颓游戏，颓知乎，虐题库。

还是挺感慨的。

OI生涯总算告一段落了。

不过结束就是新的起点吧。

想起初中毕业那天上线并且在毕业晚会上放过的歌：

等到记忆只剩精华 等到笑容不掺伪装 我们相约老地方

等到人已不再奔忙 等到心也不再轻狂 我们相约老地方

THE END