NOIP2021 游记
NOIP2021 游记
今年我高一，来保龄了。
Day ?
听教练说考点变成了雅礼书院中学，感到很问问，湖大是什么神仙操作。
Day 0
写板子的同时打 gen，板子写了 AC 自动机、平衡树、左偏树、exKMP、2-SAT，gen 机房非法组队打到了 77 星（对于我这个手残来说已经很高了）。
晚上十点就睡了，还是在家里睡得安稳。
Day 1
一个晚上醒来了三次，第三次醒来的时候忍不住看了看时间，发现已经 5 : 40 了，然后就睡不着了。
到了雅礼书院，找考场就找了好一会儿。我一直找不到第二考场，转了很久之后发现第二考场的牌子被挡住了 /qd/qd
不久就可以进考场了，竟然不能带草稿纸，并且凳子左下方的主机很烦人，写代码的时候必须把身体扭着。开考前写了个头就发密码了，然后看题。
感觉 A 比较简单，但是想了一会儿之后始终没想出来正解。又过了几分钟想试试暴力的速度，写了一发直接 300ms，仔细想来发现常数确实小，过了大样例就没管了。然后看 B ，刚开始因为校内考过一个类似的题目（upd：实际上不是的，我记错了 /kk），思路想错了耽误了一会儿时间。后面开始想 dp，思考状态要包含什么。考虑在 \(v_0, \cdots, v_i\) 里面选，选了 \(j\) 个，当前共有 \(c\) 个 \(1\)，因为后面的选择不会影响到前面位的 \(1\)，所以只需要记录最后 \(\log n\) 位的状态，所以我们就有了一个四维的 dp 状态，转移也是顺水推舟了。算了一下发现时间复杂度是 \(\mathcal{O}(n^4 m)\) 的，分比较高就开始写。调了一会儿之后过了两个样例，于是直接测了一组极限数据，开了 -O2 之后居然只要跑半秒，这很好，于是就去看 C 了。这时只开考了一个小时，感觉非常良好。
C 的操作本质上是交换差分数组的两项，这一点在 CF1110E 和 AGC006C 里都出现过。但是只知道这一点好像没有什么用，于是开始推式子，半个小时后发现要最小化这个东西：
\[\sum\limits_i \sum\limits_j (\min\{i, j\} - 1)(n - \max\{i, j\} + 1) d_id_j \]把这个系数打出来发现每一列是单峰的并且这个峰会随着 \(j\) 的增大往下移，但这个性质还是没有什么用，目前依然只会 \(\mathcal{O}(n! \text{poly}(n))\)，又焦头烂额地想了一个小时还是没有结果，于是考虑随机化。把最优的 \(d\) 输出一下发现是单谷的（我竟然发现了这个还没有想到 \(2^n\)！！！），然后随便写了写发现能过前三个样例，第四个样例跑不出来，于是就放在那里了，没有写 \(\mathcal{O}(n!)\)。
来看 D。第一眼看上去像个儒略日之类的题目，看完之后发现并不简单，部分分只会前 \(32\) 分，于是赶紧 rush。因为键盘的 Enter 键是那种倒阶梯状的，所以我想打 | 的时候老是按到回车，非常不爽。还好没有调试太长的时间就过了样例。剩下不到半个小时的时间我都用来优化 C 的乱搞和检查了，因为分数太低，我还是没有写 C 的暴力。
出考场以后发现人均 \(100 + 100 + 48 + 44\)，然后问了 \(\mathcal{O}(2^n)\) 的做法，瞬间感觉我是傻逼。看出单谷但是没想到的人全 HN 估计就我一个了。。。发现大家都是很快过了 AB 然后 C 罚坐很久。
下午在机房没打多久摆就被班主任抓过去了。
走的时候仙牛蛙说我 InfOJ C 艹了 \(64\) 分，感觉既正常又离谱。
晚上测 luogu 民间数据，\(100 + 100 + 64 + 24 = 288\)，垫底力！D 的 \(7 \sim 8\) 个数据点我以为只有 \(1\)，原来有 \(0\) 和 \(1\) /kk
Day 2
第二天早上起来很晚，然后就看到小图灵分数了，排名还行，但是感觉非常不靠谱。
晚上补 whk，开启 whk 生活，感觉非常差劲。。。
希望 CCF 数据良心一点。