[2024.11.18]NOIP2024模拟赛#23

赛时

T1 题面实在太奇怪，结合样例看了好久才看懂。

看懂以后发现应该就是简单神秘结论题。

简单写了一会就过了样例，发现没给大样例，就扔了。

T2 第一眼感觉还是结论题，但是如果发现每个点能保证只覆盖一次的话就能做到 \(\mathcal{O}(nm)\)。

然后开始写，写完不过样例，发现题目让先输入 \(m\)。（幸好样例没放两个 \(n=m\) 的）

写完以后过了小样例，发现还是没有大样例，于是自己造了一组，发现 T 了。

然后我发现我的做法根本保证不了覆盖次数，而且没有能优化的空间。

再次读题，发现题目上说的合法路径需要是最短的，也就是说我可以按照最短路的方法来跑。

但是只跑一次是不行的，因为题目上要求的是无限制条件下的最短，所以可以先预处理跑一次全局最短路，然后再跑一次，最后一一对照判断是否满足条件即可。

写完大概 10：00。

看了一眼 T3，像是一道模拟，但是发现逆序对相关的性质我根本不会。

于是先写了个枚举全排列的排序，复杂度 \(\mathcal{O}(n!+n\log n)\)，然后 \(n=10\) 的点跑了 \(2.6s\)。

去看看时限，以为是 \(2s\)，结果是 \(1/2s\)。

老师发了大样例，一看发现我 T1 假了，然后去改，发现少判断一种情况，改完就对了。

喝了点水，然后剩下的时间舌头一直在刺痛，所以不想看 T4 了。

赛后

T1T2 没挂，T3 预期之内蛋了。

T4 暴力分有 70pts，写了以后发现我可以到 rk4.

T1T2 好多人挂分，T3 正解是类似康拓展开+DP预处理的找排列。

T4 正解换根 DP，需要树剖。