NOIP2022

Daidly · 2022-11-27 13:36:26 · 个人记录

赛前

NOIP 前十多天，基本上都被模拟赛覆盖，赛后题目也没补多少，就大概感受了一下比赛。

考前三天（11.23）接到通知要去酒店隔离以防意外，大概率是能考的。第一次入住了五星级酒店，居然有浴缸欸，但是好贵。

考前一天看看知识点，板子和 UB 问题，发现自己两天内两次非 void 函数没有加返回值，错误入典了。一次是最后一场模拟赛二分没写 return l，一次是赛前一天写了一下 CSP-S2021T3 回文 然后 bool 函数分讨后没写返回值。所以赶快学了一下有关 UB 的，在编译命令里面加了 -Wall -Werror。

考前一天没让试机。晚上还水了水群，水群时看到了：

更加坚定了我明天要写出来 T2 的决心。

没睡太好，最后一次看表是 23:48 第二天也就是考试当天 5:30 就醒了，不知道为什么，哪怕让自己什么都不想也睡不着。

赛时

早上 7:50 就入场了，在酒店的一间大型活动场地考试，四人对角一桌，有些冷冷的，也有些困。

策略是先切 T1，T2 冲正解或者大部分分，T3 T4 暴力稳住。

8:15 让动键盘，写了个快读和对拍，但是对拍好像没用上。8:30 才发解压码，感觉应该提前一点，而且 PDF 居然还有一层密码。

看 T1，题面有点长，把重点整理一下写到演草纸上，还是比较好想的。预处理 disr[i][j],disc[i][j] 表示格子 (i,j) 向右和向下延申格子个数，先枚举 y_0，然后枚举 x_2，用一手加和优化时间复杂度 O(Tnm)。中间还写成了乘积，发现第二个样例没过，手玩一下就调出来了。然后测第三个样例时绷不住了，看到 114 514 已经不想去打开 plant3.ans 了。

按照计划来说 T1 是要拍一下的，但是考虑到这题爆搜不太好写，写高次方复杂度也拍不出来啥，所以就没拍。

9:30 左右开 T2，发现又是与栈有关的一道构造题，看了一会没啥思路，然后注意到 k=2n-2 或 k=2n-1 一下就顿悟了，差不多加起来 30min 想出来了两种解法，其中 k=2n-1 的感觉很模糊，具体在处理第 2n-1 个种类时与下一个相邻之间的处理。

出去上了个厕所，还能偶遇同学，有点眼睛疼，洗了把脸，回去继续。

这时候已经稍微意识到了 T2 的实现难度，所以选择先去把 T3 T4 暴力写了。

10:30 左右看完 T3，注意到 n\leq 8 和 n\leq 16，是留给 2^n 的，想到了无向图缩点，但求出桥之后不太会建新图，所以写了断边搜索 check，时间复杂度 O(2^nnm)。然后注意到特殊性质是链，想了一下写了个 dp，记 f[i] 为前 i 个点，选第 i 个的情况方案数，则 f[i]=2^{i-1}+\sum\limits_{j=1}^{i-1}f[j]，前缀和优化转移，答案即为 \sum\limits_{i=1}^nf[i]\times2^{n-i}。这时候大概能感觉到正解是缩点后树上 dp，但是衡量了一下（内心独白：我 T2 都基本上想出来了，若是只拿个简单的 n=2k-2 只有 30，而按理来说 T3 更难，而如果去冲 T2，冲出来了前三题就是 100+100+45 直接赢麻，不如抓紧时间去冲 T2），所以克制住了没有继续写 T3！

然后去看 T4，先写了个 ST 表 O(qn^2)，但是发现没有这一部分的分，然后又想到了对于每一个数考虑贡献次数，想到了单调栈求出它左右边第一个大于它的数，确定区间，但是之后不会合并计算两个数组的贡献，是个乘法。就先放弃了，还想到了莫队感觉 10^5 可以上，但是没有想细节，急着去写 T2。

这时候是 11:00 左右，噩梦的开始，得分的结束。考虑到栈大小不会超过 2，我试着用一个 2\times n 的矩阵去模拟所有栈，过了不一会，我已经意识到我只能做到 O(Tnm)，呵呵，和 T1 一样的复杂度，此时还没有浪子回头。

写着写着发现不对劲，我不好处理相近两个相同种类在 k=2n-1 为最后一个元素的情况，我尝试把每一段相同的询问缩在一起，使得新数组相邻两项不同，然后把打标记延后，这使得我的代码变得很乱。我尝试保留一份之后去重构，就这样，我我的时间在消逝。

12 点了，时间已经能看到尽头了，此时我的头脑被第二题冲的火热，忘记了还有 T3 T4 两个题仍有一部分分等着我，我回忆起一位老师说的话：”考试最后 15min 你就可以喝茶了。“我在演草纸上写下 12:30 并圈了一下，以提醒我如果半点还没有冲出来，就选择放弃吧，检查一下其他的错误。

时间过得很快啊，现在想来 30min 想要继续完成这次的 T2 对我来说确实不大可能。最后 30min 不让出去了，发密码条，监考老师一直在催提交（不好评价）还点我名了，头有些疼，无助感充斥全身，可这又能怎样呢，只能把调不出来的程序交上去罢了。

赛后

原本还以为 T2 是那种人均题，因为我很快就想出来了，但是写不出来。出来看群，有人赢麻了，没先开 T2 冲出来 T3，然后看到都在说 T2 难，感觉我在策略上已经出了问题，T4 人均分 20 也没来得及写。

我不想以 1 开头......

评价一下题目：

• T1 签到题，很多人挂多测不清空和没乘 c,f。

• T2 构造题，人类智慧题，心理战，史上最难 T2。用时一坤时，斩获高贵的零分！

• T3 dp题，要是 swap(T2,T3) 估计就 200+ 了吧。

• T4 怎么感觉难度和 T2 差不多呢，也是因为 T2 挂分的。

评价一下比赛：

• 不挂分的 NOIP2022 不是真正的 NOIP2022。

• 挂分平均数估计在 50 左右了，比的是谁挂的少......

• 大部分挂分的原因来源于组题，所以组题人出来受罚！！！

• 抛开组题顺序不谈，难度其实和去年大体差不多。

评价一下策略：

• 不能再以题目的先后顺序下意识地被禁锢，这种思维定式会建立在两种情况上：实力不够强，经验不够多。以后要提升实力并且多些比赛经验，把每一场合适的比赛都当作是正赛来打。

自测后：

• 喵了个逼的，被这题干死了。

• 赛后 T2 寄了，连 k=2n-2 都 FST 了，感觉不好......

• 希望大家不要因为我考挂了就不和我做朋友（哭）

接下来要做的：

• 短时间内的代码实现能力，可以通过限时的 codeforces 以及 atcoder 比赛来训练。

• 更强的实力，学习更多的知识点，吃透学过的知识点。

• 更稳的心态，在多场大型考试中锻炼，时间的磨练以及心态的自我调整方法。

希望下一场考试取得令自己满意的成绩吧。

update：

• 5min 想出来了 T4 前缀和优化的 20 感觉自己弃了像是个 sb

被数据杀了

T3 判链写的 if(u+1==v)，45->35

T2 FST 但不知道为啥 test10 过了，0->5

CSP 没考，NOIP 才有蓝勾。