vectorwyx 的博客

vectorwyx 的博客

My left brain has nothing right, my right brain has nothing left.

NOIP2020 游记:炸!就硬炸!/dk

posted on 2020-12-05 21:02:46 | under 游记 |

得继续走,前面是坟和野百合。走过了坟地和百合后是什么呢?

唔……尽管考的不理想,但游记还是要写的,毕竟停课了三个月,不留点什么总感觉对不住自己。

这次NOIP又是和别人拼车去的,一路上的风景明显要比CSP-S时萧瑟的多。坐在座位上想睡觉却找不到舒服的姿势,于是就在睡与醒的交替中度过了全程。临睡前AC了exgcd的模板题,甚至还在玩MC的时候通过劫掠拿到了不死图腾,自我感觉良好(伏笔1)。

23:00躺到床上,但是房间里的空调温度过高,连续起来调了好几次,结果整到24:00才睡着……

早晨起来后有点精神不振(伏笔2),本来想和dwt面基来着,结果我到达的时候他们已经进场了,只好作罢。

进场之后开始码缺省源,发现这个键盘极其,极其难用(伏笔3)。码完缺省源后就又码了spfa和Dijkstra并写了个对拍,发现fc指令慢的要命,多试了几次就变得飞快了。搞完这些刚好下发密码,含义是“选手加油1205”,针不戳。

解密后就开始看题,看到T1的时候我愣了一下,这么简单的吗?来个拓扑排序不就100了。我赶紧又读了几遍题,似乎没有什么特殊的地方。一通码码码,我丢,这个键盘真的搞心态啊QAQ,每个键位都窄了一圈我还能忍,\键在enter键左面就离谱。我每码一个字符差不多就得错按两三个,尤其是打"\n"的时候,真让人窝火。我码到一半实在按捺不住摔键盘的冲动,但转念一想怕被禁三,只好强迫自己平静心态。左面没人,我就偷偷敲了敲左面那个机位的键盘,果然一样难使,真令人头大。硬着头皮码过了所有样例,测了发极限数据竟然炸掉了,这时我才反应过来分母是会爆ll的。简单算了一下发现即使边乘边约分也照样会炸,必须得用高精度,而且甚至得写高精取模,高精除和高精乘。顿时失去了写它的信心。回头瞟了一眼数据范围,竟然有80%的点k=1,诶那我不用高精的正解和直接dfs的分是一样的啊/fad,我写正解干嘛.jpg。写出dfs来后拍上,又惊奇的发现一开始写的正解即使在范围小的情况下照样有可能炸ll,dfs反而不会。仔细分析了一下,感觉正解如果有些地方处理的不好的确会在中途炸掉,而dfs就直接一步到位了,因此风险更小。这使得我更加凌乱了,胡乱搞了个部分分分治,此时已经过了一个小时,赶紧去看其他题。

T2T3没大看懂,T4倒是读懂题了,自己感觉能有30+10=40分(伏笔4)。但是,炸了。本以为自己能快速刚出30分做法然后再拿个10分,结果被30分做法刚了。想推式子,但愣是推错了两遍,还找不到自己错哪了。一个半小时过去我发现我T2不会T3不会T430分还不知道多久能调出来的时候,心态就彻底炸裂了。当时脑子里嗡嗡的,全是浆糊的那种感觉,压根不清楚自己在想什么,要干什么,就这样晕晕乎乎的又过了10分钟,啥也没干,啥也没想,啥也没有进展。想放弃治疗,但转念一想,自己总不能连T2的部分分也不写吧?就弃掉了T4去看T2(这和CSP-S简直惊人的相似,但是这次心态可真的比CSP炸多了)

看完T2后推了推,发现最暴力的方法能通过预处理出很多东西使得它的复杂度降为O(T*(nlnn+26n))。简单的说就是枚举AB的长度len和指数i(用哈希判字符串相等),然后问题就转化成了求S[1~len]这些前缀中有多少个前缀的F值小于等于某段后缀的F值。因此只需要预处理出每个前缀后缀的F值、S[1~i]这些前缀中有多少个F值小于等于某个数的前缀( $O(26n)$)就能做。自测了极限数据,有点卡时限,但这时候只剩下不到1个小时,我已经没有心思去优化常数了,手忙脚乱的打了个暴力,码了5min后又调了15min,心态愈发的炸裂。对拍的时候一上来就WA了。发现多测没有清空,竟然还能过大样例,吓出一身冷汗,改过来就没事了。

这时候还剩大概半个多小时,又去看了看T3,发现我连checker怎么用都不会,炸,就硬炸,于是暴力也没打就再去尝试调T4。发现T4自己犯了个sb错误,改过来后过了前两个样例,但是在第三个样例WA掉了。于是我就开始了自闭模式。还剩10min处决定放弃30分做法,转而去打15分的最低档暴力,又双叒叕炸了,连第二个样例都差老远。真的搞不明白为啥暴力还能挂掉。查了5min,啥也没查出来,hoho!于是T3T4就以0分收场了,不 愧 是 我。(考完后一查就看出来T4错哪了,我把w[c[i]]打成了w[i],多么经典的错误,我竟然调了一个小时都没看出来。技不如人,甘拜下风。)

出来考场后成功面到了dwt,真帅啊.jpg。本来想和他合个影的,结果一不留神他就走了。同时遇到了lmq,yxy和yrz神仙,yrz说他抱灵了,我是一点都不信。最后和lmq,yxy神仙合了影,我最丑最菜实锤了(。


分数?自己估分 80+84+0+0=164,SD源代码还没出,但估计只少不多。恐怕没法去省选了,是真的自闭啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊


反思与总结:

这次的出彩之处是T1与T2这两道基础题都拿到了自己水平应得的分数(70+84),而且所花的时间也在接受范围内(平均一题五十分钟左右)。

但不足之处是更加明显和突出的:高端题。T3连checker都不会用,直接导致了我只能把所有时间拿来做T4,而且也大大压缩了自己的得分空间。对于T4,我认为它是最大的败笔。考场上太慌乱了,以至于犯了极其低级、典型且致命的错误:把w[c[i]]打成了w[i]。原本的预期是一个小时之内拿到T4的40分,但由于这个错误我多消耗了一个小时,而且甚至并未查出来。更糟糕的是,当我试图在考试即将结束前码出最低档的15分暴力时又犯了这个错误,以至于T4用了两个小时一分都不一定能拿到。