NOIP 2018 划船记

四年前

开心地学了 Pascal,到递归的样子。2014末以及后来六个月写了一道巨大模拟题,三千多行,叫作 Free 1.0。打了绍兴的小学生比赛。到初中就放水忘完了。初二下巧合重逢代码。

一年前

回想起来,其实去年打普及组也努力了,然而当日衢州天气恶劣,冷得我脑子都坏了。当时 T3理论上想到了解法,但因为平时做题极少,不知道一丁点广搜技巧,代码极长,bug一大堆,不断打补丁,最后也没调出来。T4始终就是个二分答案的壳留在那里。很晚赶回,感想很具体:游了一天的船,然后躺在轻且小的船上做了一梦。

普及二等奖非常打击自信。见到人都不敢提,假装自己去年没参赛。

初中是个中考且住宿学校,跟搞竞赛矛盾。不过班主任还是给我和同班同学(Youth|吹雪、轻于水)练习机会。有段时间中午去机房做洛谷里的水题,积攒了我现在成堆的红题和橙题。后来全体老师打压。中考是正业,你可了解?周六还是出来上课,不过除此以外没时间搞信奥,初二下以来都是。

没保送成功(放弃保送学车)。我在学校状态不妙,也担忧中考不进,只能更少操作键盘,代码水平更迅速退到起始。

中考非常刺激,不盲目自信的话,数学大概率爆炸。结果竟然还行,首先考虑回到信奥。但是同班同学散了。

暑假

集训。六月末几日努力做了几道题,好像拾回点知识。七月不幸敲起 Free 3.0,进步之事废了。还好八月中抓紧一点点。

初赛

没怎么学文化科,但信奥又没什么进步。听说 Youth|吹雪 也在准备 NOIP 2018,他是学军的,还跟我一起在洛谷做历年初赛题。

团支书事情一堆,初赛除了几张真题也没别的准备。考前一天不知哪里来的自信,和室友颓单击个膜到半夜两点多。第二天强制睡到正午。不知道是不是早就发车了?

还好赶上出发,到豪华的杭十四中分校。打铃开考,似乎出题人“不针对我”,时间分配很糟,但除了最后几空还是自信的。出门畅谈,立刻发现错误,上车校对 Dilute 的看程序写结果,我又炸了。本来数学题自信,对了答案,居然我错?草草一估计,仅几题下来我就只剩 72 了。按去年分数线是不可能过了。

车上窝着睡觉。回家接着睡觉。回校仍然颓废睡觉。我想,没过也不退役。

等一年吧。

一年太久。

想想这些时间花下来,连初赛都过不了,气得不行。

我干什么去当团支书呢?

怎么没去学军呢?

依然不顾这些,找老师在集训停课申请单上签名,因为我觉得还有一星希望。但是停课集训又没什么进步。熬了两星期,初赛成绩出了。然后才醒悟了一样,打算收拾电脑回去了。

我始终不看初赛成绩表,就睡觉。结果 失落的神犇 远在学军发私信:

*xx,你的初赛... *

分数线没消息。过两天 FFFeiya 奶了一口分数线 68,据说他这么预言是“为了让我通过”。看来我是 68 分。

再过两天,走到机房,他摇我肩膀道:分数线 68!你卡线进了!

太假了。但是不断听说分数线 68。室友说大难不死。Youth|吹雪:

!!!!

有点东西的你

压线××

那么就继续停课。模拟赛难啊,后来越来越频繁不交卷,下午经常是写 Free,或看“别人看直播”,或者 FL,晚上修博客,看新闻,李咏、金庸去世了!震惊并难过。

其实前期并不这么颓废,训练场还是打了。但是又又没进步。

考前一天冲刺

周五openday。我上午看别人打游戏,下午自己打游戏,晚上出去吃东西。

其实回来突然慌了,赶紧看了一下卢卡斯和分块和莫队,回看做题记录。

Day 1

起太早,冷。到豪华的学军分校,车上饺子真好吃!

8:30

解压密码是金庸小说串烧短诗的四字的拼音,插入随机符号。开始。

打开卷子,看标题觉得大概不太友好。有中考的感觉。读题吧。等等……

……没错,T1是洛谷上有的(我还不知道是2013原题),大概三星期前就做到了。当时还看了题解,记忆犹新。打了打了。记住!出考场一定要告诉大家这件事。

8:40

T2给人一种“大凯的疑惑”的感觉。出题是不是和去年有重合啊?但好像不是数学。大胆猜测了一个背包,简单证了一下,好像行,但此方法超时。大胆猜测了一个优化,简单证了一下,好像行,打了打了。

9:25

好像还有点时间,那就测一下大样例,自己也做一个水数据试试吧。要不要拍一下哦。

但是不会写暴力怎么办?有点慌,算了,小心T3很难。

9:45

看T3,肯定不简单,貌似恶心的DP?

不对不对,要二分答案,壳先打着。

10:20

思路还没明确,似乎可以贪心匹配、贪心上传?简单证了一下,好像行。实现,一开始只有n方的,要T。O(n)大概是洛谷某道熟悉的坐船?然后可以内部再一个……

//震惊,又是二分!

监考看到我打这个注释,好像在我的身旁停顿了一会儿。

不得不假设是对的,赶快打完,测大样例。

11:10

大样例居然答案对了。

但是为什么用了半秒?完了一定是我复杂度分析错了。

但是删了最慢的 sort 也半秒。

不断删,发现一个O(n)的地方如同变成了n方。

好像是 while 里RE了。少了个越界判断。本机表现成TLE。

加上就可能行了。

今天题咋回事?下午水知乎看见投诉三道原题的。明天肯定难爆,但应该没树、没贪心了,肯定有字符串和DP,Tarjan 来不来?晚上打森林冰火人。

Day 2

寝室里冷,出门不冷。车上包子真好吃!到了大厅赶紧到处问 AC自动机。

8:30

又是金庸密码。

果然T1又考树,果然又是贪心。树就有60分。环,可能可以枚举断边,但是花了2s估计复杂度,得有n三方吗?(估计都估计错了)

环上贪心吧,快。挂了,想了想,有问题。改了改,挂了,想了想,有问题。改了改,证了证,节奏乱了。加上并查集以后,代码3K。小样例过了,不敢测大的,因为:

9:50了!

不能乱节奏,喝口矿泉水,怎么有面包味儿?

T2大概是DP,想想,到时候标程肯定非常短,大胆猜结论,简单模拟了一下,2过了,3偏小(输出96),我模拟错了吧!三十几行敲出来跑一遍,模拟没错,是算法出锅。稍等,这错算法还能简化成乘法,一简化更明显错了。再等,错算法好像也打错了。然后改成正确的错算法再模拟,2过了,3偏大(输出144)。到底少考虑了什么?先看看T3,果然又是树。可能有暴力分,打算十一点半再说。然而突然发现T2忽略的情况,才知道这道题有多不容易想。

所以直接T3暴力保分。而且T3只测了小样例。

11:45

暴力才调出来。T2还有可能吗?测T1大样例吧。

环贪心写挂了。

11:59

T2 dfs 来不及打,先特判小数据,其它就用错的DP吧,虽然大概率没分。

出来听见T1应当枚举断边,冷静分析好像不会超时。悔。不过面包好吃。

现在根本无法预料会不会fst。说不定来个文件名打错之类的惊喜。

Day 3

测了一下,day2T2怎么,错的DP还帮我拿了一点分。

期望最高得分 100 + 100 + 100 + 60 + 16 + 44 = 420

洛谷测试 300 + 68 + 55 + 44 = 467

实际在官方数据下,这点分也还是没有的,何况我的实力更低于这个,题目要不是这样,可能我考得还要低。但是,只对这次而言,运气虽好,但也没发挥什么水平,尤其是打day2心态不对,以及错误地分配大量时间在T2上。

回想停课期,玩的是开心。

Day 11

实际在官方数据下,300 + 68 + 50 + 44 = 462。

其实话说回来,494是最低暴力分。

原文地址:https://www.cnblogs.com/cicos/p/10330074.html