NOIP2022 游记

HoshizoraZ · 2022-11-27 15:52:29 · 个人记录

坐标：FJ。

早上 7 点起来，精神不是很好。不过没有下雨，运气不错。在来的路上本来想要在复习些什么的，但是感觉挺困的，就什么也没看。

到了附中门口，倒是一路就走进机房了，并没有要等待什么。键盘和校内差不多，但是电脑比较离谱，开个 C++ 要等待十来秒。

开题了，先扫一眼，T1 有取模、测试点不等分，T2 我趣，是构造，还是咩了个咩，T3,T4，完蛋了怎么三个取模。

回来看 T1，发现是个简单题，二十分钟写掉了。然后打开样例 3 的输出，114 514，这么臭的样例有什么造出来的必要吗（恼）

做到 T2，本来想着今年一定要去磕掉这题，结果画风不对，感觉上能做，却时不时又想出反例，所以口胡了一个 k=2n-2 的情况先跑了。

跑去看 T4，20 分暴力很显然，然后看见 Q=5，排列随机的点，回想到了一个性质，上了四个单调栈+奇怪的暴力，大概能拿 36 \sim 44。

往下看时间，已经过一个半小时了，要抓紧。

倒回去看 T3，一开始想错了，以为建军营的点之间一定要连边，然后敲了个 15 分 \mathcal{O}(2^mn) 状压，第二个样例死活过不去，卡了很久。

然后重新思考，发现一个环上的边不论怎么选，点都可以任意取，因为只有一条边可能会被割掉，所以永远连通。

本来思考到这我是能做出来的，但一是我没半年没练边双缩点了，tarjan都不会写，二是我脑抽一时半会想不出树形 dp，所以就寄了。

不过运气好的是由于发现了这个性质，状压复杂度其实是 \mathcal{O}(2^nn) 的，能拿 35 分，然后链的情况找一下规律就马上出来递推公式了，合计 45。

比赛大概还剩 100 分钟的时候才回来写 T2，先把 k=2n-2 的 15 分写掉，然后感觉 n=2 和 m \le 14 可做。