NOIP2021 游记

感觉自己对 $\text{NOIP}$ 有点 “$\text{PTSD}$” 了。

去年 $\text{T1}\ 100\to 60$,$\text{T3,T4}$ 压根不会,直接垫到全省一等奖底部。上个月的 $\text{CSP}$ 靠着误打误撞碰到了正确的开题顺序,发挥得不错,不过那些都没啥用,还是得看 $\text{NOIP}$......

高二赛季的 $\text{round 1}$ 了,希望自己能不辜负自己吧。

Day -Unknown

学校的社团节要开始了,这应该是我校十分有名,而且也十分盛大的一个活动。由于社团节一年一度,我并不希望错过,于是一直尝试着在上午集训结束之后去排队买票。

不过咋感觉今年票巨大难买,根本排不到。甚至出现了和 $\text{i}\red{\text{odwad}}$ 在原地排队排了 $\text{15 min}$ 之后被告知票买完了的情况/qd。

$\text{Z}\red{\text{cus}}$ 不知道怎么搞到了一大堆的票,然后在机房里疯狂哄抬物价/kk。

后来想了想,社团节开幕式正好是 $\text{NOIP}$ 前一天下午,如果我去看了,结果 $\text{NOIP}$ 考砸了,我很难不把一部分原因怪罪到去看了社团节这回事上。如果因为这样导致这么多年在 $\text{OI}$ 上的努力白费,我可能都原谅不了自己。况且本身也没买到票/hanx

Day 0

在机房自闭,打了打一些不是很熟悉的板子 比如每次考试前都一定会写的后缀数组,感觉根本没办法平复心情。

上午开了一个动员大会,我校 $4$ 个集训队选手都上去讲了一些话,其中包括但不限于:“去年我 $\text{NOIP}$ 后两题怒砍 $\text{45pts}$”,“我初中三年差联赛一等奖 $1,5,9$ 分”,“这种构造题应该不会出现,你们当我没说”。

下午听说同学得知我没买到开幕式的票,然后帮我搞到了一张!!!一把子感动.jpg。然后就去社团节了,并祈祷 $\text{NOIP}$ 没事。

结果晚上教练就在家长群里说,他觉得考前去看开幕式不是明智的选择。

于是晚上继续在机房写板子,主要是觉得回家的话自己会更加焦虑。希望人没事。

睡前收到了 $\text{l}\red{\text{k}}$ 很长的一段信息,一把子感动。真的很感谢学长们的关心。

Day 1

早上 $7:00$ 左右就从学校坐车去了考场,大概在 $7:40$ 左右到达考场。感觉自己真的有点紧张,总害怕万一自己复习得不彻底,到时候在考场上遇到突发情况怎么办。只能不停地读之前写的考试总结、各种代码......

到考场之后得知还不能进入,于是在外面干等了 $\text{30 min}$,我尝试通过跟同学们聊聊天来缓解自己紧张的心情,感觉有一点效果。

坐到座位上,赶紧配好所有配置 然后发现键盘是离谱的大 Enter 键,特意将电脑时间设置提前 $\text{3 min}$,然后静等开考。

解压密码好像是 IronHeart@413,希望自己也能有 $\text{Iron Heart}$ 吧。

打开题目,首先扫一下所有题。看完 $\text{number}$ 就秒了,接着看完 $\text{sequence}$ 也秒了,但是 $\text{variance}$ 没有一眼的想法,$\text{chess}$ 题面长得离谱。

由于担心先写代码的话,后程脑子会转不动,于是准备尝试复刻 $\text{CSP}$ 的考试策略:先压一手 $\text{T1,T2}$,切掉 $\text{T3}$ 之后一起写。

首先我根据数据范围猜测最终的复杂度应该是 $\mathcal{O}(na^2)$,且应该会存在一个 $\mathcal{O}(n^2a)$ 的部分分做法。于是快速编了一个看起来没啥正确性可言的贪心:

大概是枚举一个“中心”,让两侧的元素尽量靠近中间,“靠近”的有效次数只有 $\mathcal{O}(na)$。当时就感觉他不太对,不然这个第三题也太【数据删除】了。实现了一下发现果然不对,于是赶紧写了一个 $\text{BFS}$,试图从中找出最优决策方案。

盯着看了许久,没啥结果。此时已经大约 $\text{1h}$ 了,于是赶紧切换策略,先把前两题写完。

$\text{number}$ 我直接冲了一个看起来带调和级数的东西,实际上跑得飞快,只需要 $\text{0.3s}$ 就可以在考场电脑上完成所有的预处理。$\text{sequence}$ 写的是一个 $\mathcal{O}(n^4m)$ 的东西,常数看起来不大,很快写完了,甚至连编译也没调,并一次过了两个样例。

写了 $\text{number}$ 的暴力,并对比了 $1\sim 10^7$ 的所有答案,没啥大问题。$\text{sequence}$ 也直接拍上了。

接着回来思考 $\text{variance}$。根据之前一贯的经验,开始思考对序列进行差分。然后莫名其妙做了前缀和,然后没有发现任何规律。开始罚坐。

去上个厕所缓解下心情,回来突然发现自己咋做的前缀和,明明应该差分啊啊啊。然后就发现了操作本质是交换差分数组相邻元素的事实。

把方差的 $n\sum a_i^2-(\sum a_i)^2$ 带入差分之后,得到了一个超级丑陋的式子,盯着看了很久,压根不知道应该如何利用他。

接着又意识到差分数组中,本质不同的元素个数只有 $\sqrt{2a}$ 个,然而我还是不知道如何用......

把 $\text{BFS}$ 改成输出差分数组,很快观察到最优方案中,差分数组中除了第一个元素无法移动之外,其他部分貌似是“单谷”的,跑了很多自己手造的数据,发现都满足这个规律。

于是直接会了 $\mathcal{O}(2^{n-1})$,这就已经得到 $\text{48pts}$ 了。感觉自己离正解不远了,于是准备把 $\text{chess}$ 的暴力时间往后压一点,毕竟如果只过两题,还是不太理想。

感觉上这个正解应该就是把这个暴力枚举放左边、右边换成 $\text{dp}$,注意到贡献只和 $\sum a_i,\sum a_i^2$ 相关,是不是可以设 $\text{dp}_{p,j,k}$ 表示前 $p$ 个差分,$a_i$ 之和是 $j$,$a_i^2$ 之和是 $k$ 的最优答案?

后来想到应该可以去掉 $k$ 一维,虽然没有得到一个具体的做法,但是我认为这个思路至少可以推出一个 $\mathcal{O}(n^2a)$ 的做法。

我开始尝试是否能将复杂度优化至 $\mathcal{O}(na^2)$,从而通过此题。进行了一些尝试之后无果,试着编一下 $\mathcal{O}(n^2a)$,发现失败了!!!

于是开始乱搞,写了个贪心,每次看放左边更优还是放右边更优,并无法通过样例。但我注意到一次贪心的复杂度仅仅是 $\mathcal{O}(n)$,于是套了个随机化,跑的次数和 $n$ 的大小成反比。

发现他的表现十分不错,可以通过所有的样例,并且竟然能过 $n\le 20$ 的小范围拍。此时只剩 $\text{40 min}$ 左右了,我赶紧去写 $\text{chess}$ 的暴力。

艰难地看完题面之后,准备先冲 $\text{24pts}$,并意识到了 $\text{32pts}$ 实际上可以直接用 $\text{24pts}$ 的代码拿到。但是因为时间太紧迫了,所以我直接使用了 $5000\times 5000$ 的数组而不是 vector,准备在调完之后再改成 vector

于是开始写记忆化搜索,由于题目中各种条件,写起来难度不算很小。写完后无法通过第一个样例。于是开始 $\text{debug}$,并逼自己必须在 $12:50$ 之前结束 $\text{debug}$。

实际上 $\text{debug}$ 的时间稍微超出了我的预计,由于我实际上明白我的时间比其他人早 $\text{3min}$,因此我将结束 $\text{debug}$ 的时间延后到了我电脑时间的 $12:55$。

最后发现自己在复制部分代码之后,有一个细节处没有修好,改好后过了前两个样例,测第三个样例的时候我双手合十,幸亏直接过了。

此时我想尝试将其改成 vector,但是实在没有时间了,我还要留出一些时间检查前面三题,于是不得不含泪放弃这 $\text{8pts}$。

最后我又将每一题我能过的样例进行了一次测试,发现 $\text{variance}$ 的最后一个样例错了,再运行一次就能对。于是我立马调整了一个随机的参数,再运行了两次,都可以通过了。

很快之后,考试就结束了。看到 $\text{i}\red{\text{odwad}}$ 好像考得不错,但是 $\text{b}\red{\text{igmurmur}}$ 告诉我他不会 $\text{sequence}$,可能要退役了......听到这里我真的好难过......

出考场的时候大概估计了一下自己在省内的排名,感觉应该有机会上队线,但是像 $\text{CSP}$ 一样苟进 $\text{A}$ 队线应该是很难了。

出考场交流了一下,$\text{l}\red{\text{k}}$ 感觉发挥的不是很好 但他是集训队他考得不好有锤子关系,$\text{h}\red{\text{uhao}}$ 好像是 $70+100+100+100$???属于是不想 $\text{AK}$ 了/qd。貌似现役的选手们差距都不是很大,感觉这种没有区分度的场有点恐怖啊,如果挂了一点咋办......

坐车回学校,回机房取鼠标的途中,突然意识到好像自己 $\text{variance}$ 拼的 $\mathcal{O}(2^{n-1})$ 没有运行????好像自己在对拍的时候把 if(n <= 20) brute::solve() 改成了 if(n <= 0) brute::solve()。/px/px/px,那这 $\text{48pts}$ 也不稳了,希望随机化能给力点了......

下午一直在担心一些奇怪的东西:比如文件有没有开错,考号有没有写错之类的......后来听说隔壁的选手打错了考号......只能为他感到惋惜并祝文化课顺利了......

为了缓解一下,和 $\text{i}\red{\text{odwad}}$ 一起快乐 $\text{APEX}$,一开始打得像老年人复健,后来竟然有一把差点吃鸡了,体验海星。

接着代码和数据陆续来了,测了一下,前两题没啥问题,果然 $\text{variance}$ 的暴力没跑成/ll/ll/ll,咋犯这种低级错误啊......

立马得知了 $\text{InfOJ}$ 已经造好了 $\text{variance}$ 的数据,去交了一发,在等待评测的时候继续 $\text{APEX}$。打完一把 $\text{APEX}$ 跑去看评测结果,发现自己的随机化直接 $\text{AC}$ 了???

卧槽卧槽卧槽卧槽,这东西这么优吗???

之后陆陆续续测了几个地方的数据,发现我的随机化全都能跑过/jy/jy/jy。希望最后的数据也能如此吧......

$\text{l}\red{\text{k}}$ 拉了一份数据测了全省代码,发现我在过了 $\text{variance}$ 的情况下,前面仍然有两个人,而且后面的分数追得很紧......看起来我低估了这一年 $\text{HN}$ 的实力啊。

晚上心情舒适,开始文艺复兴。重新看了一遍《西虹市首富》,感觉很有意思。

Day 2

上午睡得很舒服

发现小图灵的数据下我的 T3 挂了 3 个点......希望最终数据抬一手。

收到了大两届、现在在 $\text{THU}$ 的学长的信息,得到了鼓励,真的很感激。

下午回机房了,和大家进行了很多的讨论,并醒悟了 $\text{variance}$ 就是个做法二合一的题/tuu,不过好在这个事实让我意识到我的随机化应该可以有理有据地得到 $\text{72pts}$,很惊喜。

希望正式数据能抬我一手把/ll/ll/ll,孩子已经高二了/ll/ll。

估分:$100+100+[48,100]+24=[272,324]$

实际:还没出来/hanx

添加新评论