NOIP 2022 游记
Ninelife_Cat
·
·
个人记录
前言
按照惯例考前两周应该去机房集训的，但今年的机房风气已远不如去年了，于是仍旧以文化课为主。
毕竟自己不是圣人，难免想颓。
Day 0 NOIP 前一天
今年住的居然是八百一晚的杭州西溪雷迪森大酒店。
学校啥时候变得这么有钱了。
公费旅游 plus，起飞。
笑死了，酒店整个十二层几乎都是我们的人。
刚理完东西，去串了个门，一看 xhf 连外卖都已经点上了。
之后便是喜闻乐见的银趴环节。
七八个人挤一个屋子里吃烧烤小龙虾肯德基，有打 CSGO 的，有玩 LOL 手游的，还有看罕见大片《君の名は》的。
吃完之后又去休比房里蹭电脑玩原神，打到十二点半回房睡觉。
除了复习 NOIP 啥都干了属于是。
Day 1
酒店的叫醒铃声太轻了，早上差点睡过头。
自助早餐我觉得还行，烤饺和小甜点很好吃，就是培根和烤肠有些老。
但同学一致认为一般，不值八百一晚的价格。
可能由于去晚了没啥好东西吃了。
其他没啥好写的，直接快进到开考。
今年的文件夹解压密码八点二十就放出来了，刚想夸 CCF 今年给大伙提前看题，duang，打开 pdf 又要个密码。
引荐人吧。
密码是 biu#2019miss 和 solo@2022，一年更比一年抽象。
看了下题，T1 T3 T4 好像都是计数，T2 构造，都不是我擅长的，一眼寄。
于是开 T1，想到了个 O(n^2m) 的 72pts 暴力写法。
预处理一行连续的 0 的个数，然后枚举合法的两行，接着枚举列，用前缀和判是否合法，并更新答案。
做到 F 的时候突然发现先枚举列是否合法能大大减小枚举次数，这样复杂度就变成了跑不满的 O(n^2m)，如果 01 矩阵不是特意构造的话甚至可以降为 O(nm) 级别。
花了半个多小时，然后看 T2。
手玩 $n=2$ 半小时没玩出结果，便弃了，先打后两题暴力。
T3 想到了找桥缩点之后在建出的新树上搞搞，但算答案那部分没什么思路，最终还是决定写 $O(2^n)$ 的爆搜。
刚打算写，问题来了，发现自己不会找无向图的桥，于是瞎写了个复杂度极其糟糕的 shaber 玩意。
省流：写成了一坨答辩，$120$ 行 $3.2$ kb，复杂度大概 $O(2^nn^2 \log n)$ 附加巨大常数，全局和局部变量重名一堆。
枚举每条边删去之后是否会造成图不连通，得到所有的桥，再把桥删掉跑 bfs 得到若干个连通块。
爆搜枚举点的时候又发现需要维护经过的树边个数，于是又要一个 dfs 预处理父亲节点和一个 map 维护边。。。
写的很乱，基本上是想到什么写什么，根本无法解释。
T4 更是没有思路，草草打了个 $8pts$ 的 $O(n^2Q)$ 模拟就跑路了。
此时还剩下一个半小时，回来冲 T2 正解。
结果直到考试结束我还是没玩出 $n=2$，只好写 $k=2n-2$ 遗憾离场。
这剧本怎么和去年这么像呢，都是 T1 秒了，T2 不会，T3 T4 一丢丢暴力分，然后二等退役。
***
# 彩蛋
考试快结束的时候开了把扫雷获得了 $74$ 秒过中级的成绩，然后就忘记把挂在椅背上的外套拿回来了。。。落在杭师大机房了。。。
找花花问了下能不能让杭师大的人帮忙寄回来，结果不出意外地寄了。
这下只能明年的 NOIP 去拿了。
***
# Updated
冥间数据 $80+0+45+8=133$。
T2 手玩炸了，痛失 $15pts$。
希望 CCF 数据能比冥间数据再假一点。
***
# Updated*2
T1 多测没清干净小图灵上 boom 成 $23pts$。
为了省点时间没用 ```memset```，手动清空，结果边界处理萎了，破大防。
```cpp
while(T--)
{
cin>>n>>m>>c>>f,ans1=ans2=0;
for(ri int i=1;i<=n;++i)
for(ri int j=1;j<=m;++j)
a[i][j]=s[i][j]=x[i][j]=y[i][j]=0;//这里后缀和数组用到了n+1和m+1位置的信息，但是没清空到
...
}
```
***
# Updated*3
官方数据 $10+0+15+8=33$。
寄。