感觉自己对 $\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{Q}\red{\text{iuly}}$ 发来信息给俺加油，睡前还收到了 $\text{l}\red{\text{k}}$ 很长的一段信息，一把子感动。真的很感谢大家的关心。

Day 1

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

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

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

解压密码好像是 IronHeart@413A，希望自己也能有 $\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{72pts}$，很惊喜。

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

Day 3

我超，看到某网站自测中我 $\text{variance}$ 只有 $\text{20pts}$，那我岂不是输光了？？？？？

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

实际：上界。

好像 $\text{HN-01}$ 又没了，只能爬了。