NOIP2022 爆炸寄

· · 个人记录

NOIP 2022

同步更新于。由于前文涉及了一些私人 / 学校的非公开信息，故不予查看。

Day 1 / 2022.11.26

决定命运的一刻了，早上起的很早，和弘 \text{win} 一起去吃的早饭，来到教室，神些都给我加油，大概是不能辜负众望了啊（事实证明还是失败了）。

07:04

到达机房，做核酸，打卡洛谷。

宜：参加 \text{NOIP} ，祝你 \text{RP++} 。

例行格式，但也添加了一份信心。

07:11

依然在摆，想着逛逛洛谷能不能给点灵感，瞄了几眼平衡树 \operatorname{FHQ} 和高斯消元的板子，然后记了一些要点。

07:23

跑路。

07:41

到了楼底下，动了动钢琴，买了两包小袋纸和一包大袋纸（怕带不进），然后撕水的包装，万事俱备。

07:58

上楼。

08:02

进考场。

08:15

公布了 .zip 密码——biu#2019miss （后来察觉大概是禁三的梗），帮旁边人输密码，差点被逮。

偷偷开 .pdf 想看题，结果还有一层密码！那就瞪样例，发现似乎除了两道题之外输入量都比较小，考虑打不打 \text{Fast I/O} ，为了码风整齐，还是打算打。

08:23

罚坐。

08:31

公布了 .pdf 密码——solo@2022 ，打算偷偷看题，结果已经开考了（提前开了虚拟机），一边看题一边写 init ，结果发现那个机子慢得扣脚，就放弃看题，然后先打完了 init 。

08:38

看题，第一题看样子是个 \mathcal O(n^2) 的神仙暴力，\text{T2} 神仙构造题，\text{T3} 是个图论，幻视出了“不可以总司令”的感觉，结果是个计数，那就是图（或者树）的 \operatorname{dp} 了，\text{T4} 题目较长，先不看。

8:43
然后发现其实是好做的，迅速糊了一个 $\mathcal O(n^3)$ 跑不满的做法。 ##### 9:11 三个大样例都过了，第三个大样例的答案居然是 `114 514` ，$\text{CCF}$ 他真的，我哭死。 跑路。 ##### 9:12 想 $\text{T2}$ 。 ##### 9:16 码暴力。 ##### 9:38 码不出来，放弃 $\text{T2}$ ，转向 $\text{T3}$ 。 ##### 9:39 先去想了想树怎么做，结果发现还是不怎么会，然后开始码 $2^{n+m}$ 的状压。 ##### 9:54 码完，但是发现第二个样例死活不过，调。 ##### 10:19 调不出来，跑路，转 $\text{T4}$ 。发现 $\text{T4}$ 结果是个神仙数据结构，码暴力。 ##### 10:28 本来以为是个 $\mathcal O(n^2)$ 的，结果是 $\mathcal O(n^2q)$ ，$20pts\rightarrow 8pts$ ，想怎么优化，没想出来。 ##### 10:32 添了个记忆化，跑路，重开 $\text{T3}$ 。 ##### 11:11 口胡了一个链的公式，不太去顶，写了跑路。 ##### 11:41 打算冲一波 $n\leq 16$ 的分。 ##### 11:32 胡 $\text{T2}$ ，拿了个大概是 $\mathcal O(n^{2m})$ 的分。 ##### 11:43 外面开始放一些流行歌曲了，然后就听到《只因你太美》，还有很多比较熟悉的歌曲。 放平心态。 ##### 11:52 大概有了正解的思路，结果发现这个东西在平时仅限见过和口胡，没有做过（生成树计数和双连通分量），怎么办呢，只有摆了。 ##### 12:05 $\text{T1}$ 好像可以优化到 $\mathcal O(n^2)$ ，整了个 $C$ 的结论，过了。然后瞎猜了个 $F$ 的结论，也过了，但是用了 $\operatorname{BIT}$ 维护，时间复杂度 $\mathcal O(n^2\log n)$ 。 ##### 12:29 $\text{T1}$ 解决。 ##### 12:36 想了下 $\text{T2}$ 里 $n=2$ 的分，没啥头绪。 ##### 12:49 码了 $\text{T2}$ 的随机调配，不抱期望。 ##### 12:50 摆烂，疯狂检查 `freopen()` ，然后确定校对了，摆。 罚坐。 ##### 12:53 拿 `dev-c++` 乱搞，发现 $\text{T4}$ 编译错误，拿记事本改了。 ##### 13:01 还想检查，但是时间到了。 最终结果：$[60,100]+[0,35]+[0,25]+[8,20]=[68,180]

测分结果如下：

\text{Luogu:}100+0+10+12=122pts \text{InfOJ:}16+0+10+8=34pts \text{XJOI:}100+0+10+8=118pts

没什么好说的了。