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不就行了。

注意到题目范围给到了2^{64}-1。嗯,不就是unsigned long long 吗,没关系。

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

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

幸好原题也只有一个点满足n==64

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

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

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

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

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

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

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

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

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

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

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

然后就开始干T3了。

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

于是瞎搞链,乱贪心。

最后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

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

看来我必然会爆零了。

大吉。

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

上午 7:39

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

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

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

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

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

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

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

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

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

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

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

然并卵。

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

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

看了下T2,打了一个n^3的暴力。在Arbiter里测试了一下,应该可以拿到\frac{9}{25}的分数。

此时大概十点多吧。

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

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

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

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

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

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

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

可惜没过第三个小样例。

这个时候,乱检查了一下,加了一个a[i][j]=0的判断,过了。但是我想,我的这个算法加不加判断都无所谓啊。

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

然后再次测了一下。T3有\frac{11}{20}的分吧。此时大概是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

留下评论

您的电子邮箱地址不会被公开。