NOIP 2021 游记

简介：意料之内的爆炸。 [原来的屑游记](https://www.luogu.com.cn/paste/gl8i31se) ### $\textrm{Day}\ 0 - 11.19$ 咍咍，XJ 模拟赛搞了我几个星期的心态，今天终于没有了。 然后就是颓颓颓，越颓越慌，想补补数数题，发现看了题解还是不会（ ### $\textrm{Day}\ 1 - 11.20$ 起得很早，早上吃了学校的小笼包，貌似更难吃了？ 然后在车上晃了一路，进去前和全 XJ 学生照了张合照，还被扔到 NOI 官网上去了（ 进场后开了文件夹，发现有一个 `number`，有一个 `sequence`，大样例很小，估计着像是什么结论题？ 有一个 `varience` 不知道是干嘛的，还有一个 `chess` 之后一直在看那个选手须知，貌似是直接贺的 CSP 然后解密，建文件夹。发现 A 是 sb 题，随便嘴巴了一下去看 B，然后有点蒙古。 于是直接去打那个 A，其间配了好一会儿 VS Code，直到 20min 左右才搞完。 然后开 B，看到 $n=30, m=100$ 这个阴间数据范围，想到大概率是什么高维 DP，因为 `meet in the middle` 肯定会开到 $n=40$。 然后写了一个巨大多 DP，空间 $\mathcal O(n^3m)$，时间 $\mathcal O(n^4m)$，然后一度以为自己假了，直到一发过了大样例 这时才 1h 左右，感觉不慌，吃了点东西，开 C。 感觉这个 C 看着十分 CF，推了推发现了那个重排差分的结论，记起来这是上次 ZCETHAN 不会的题（ 然后打了个样例二的方案，发现大致呈 V 字形排列，之后就不会了。 我把这个差分数列**从大到小**排了一遍，然后去想做法。 之后就一直在 C 上磕着，中途读了一下 D 的题意，觉得去打 D 的暴力还不如搞出 C 的正解，于是回去继续做 C。 发现数据范围十分不对劲，猜想复杂度是 $\mathcal O(na_n^2)$ 一类的东西，于是把我之前一直在想的各种诡谲贪心叉光了。 这时候 3h，大致意识到 C 可能又是个 DP，然后想了好长时间还是只会 $\mathcal O(n^2 a_n^2)$ 的暴力 DP。 写写写码码码，写到心态爆炸，写完一测发现连 $n=4$ 的样例一都过不去，直接注释掉了。 开 D，尝试打暴力，由于心态已经爆炸，打了一半就不打了。 然后发现还有 0.5h，去写 C 的随机化（只有 `shuffle`，没记起来退火怎么打），自以为能过 $n\le 15$ 的所有点。 最后检查了一下文件，去扫了一盘初级雷，时间就到了。 出场碰到猫猬兽，才得知 C 的 $\mathcal O(n2^n)$ 暴力有 48pts（（（ 然后 D 的好打的暴力有 32 pts（（（那这场不是猫猬兽要原地升天...... 出场问了一圈，碰到一个 mer 和我一模一样，都没打 D 的暴力，C 也做了 3h；pig 切了 ABC，我只能/bx cmll 和 dX 好像也都不会 C，但是他们都打了 D 的暴力，就我没打 听 pig 讲，正解是从小到大排然后 $\mathcal O(n^2 a_n)$ 的 DP，然后判掉差分为 $0$ 的情况就能过了，感觉我是小丑。 回去的路上在车上吃了些巨恶心的鸡肉，然后十分晕车。 ### $\textrm{Day}\ 2 - 11.21$ 听说代码发了，测了一下，大概前两题没挂？ C 的随机化只有大概 32pts有一个彩蛋是 D 我只打了读入还打挂了 之后要投入到 whk 中了。。。 ### $\textrm{Day}\ 4 - 11.23$ devin 测了一下全省代码，貌似 1= 线大概 190。 我在 XJ 数据上跑了 244，但是又排不进省前 100（ 不过 pig 上队线了/bx