NOIP 2023 游记

EuphoricStar · 2023-11-18 17:44:33 · 个人记录

前一天打了点板子，特意看了一下连通性相关。

8:25 进场。右边是 ckj/se/se。

8:27 下发解压和 PDF 密码，顺便打了个缺省源。

8:30 开 T1。哦我会 O(n^2 \log m) 二分哈希，看上去很能过，8:45 写完。没拍。

开 T2。一眼顶针建出一些内向基环树或者内向树。哦那是不是做完了啊。9:25 写完 + 上拍。

开 T3。立刻转化题意，c_{i, j} = [a_i < b_j]，要求是否存在一条从 (1, 1) 到 (n, m) 的路径。哦暴力有 35 分，赶紧写。剩下的分好像不那么好搞了。先扔了。

9:50 开 T4。哦我会 O(n \log n)，哦有 56 分。开写。10:20 写完。哦我还会 O(m \log m)。是正解。开写。10:50 写完 + 上拍。

还有 2h 留给 T3。想了一些奇怪的分治，感觉细节很多，没写。退而求其次，先看特殊性质。哦我是不是可以设一个 f(n, m) 表示求 (1, 1) 是否能到达第 n 行或第 m 列。然后能缩尽量缩。OK 又拿到了 35 分！但是细节还是很多，要分别处理 2 个前缀 minmax 数组。不管了直接开写。12:00 过了特殊性质的大样例。

然后再想正解。哦是不是把最小值的行和最大值的列拎出来，正反跑一遍上面的做法就做完了啊？？？还真是。开写。12:25 写完 + 上拍。

剩下的时间在检查 + 启动虚拟机。

然后考完发现自己 T3 小丑了。

for (int i = 1; i <= n; ++i) {
    c[i] = a[i];
    d[i] = b[i];
}

其实复制 b 应该到 m 的。但是这玩意能过大样例，而且我拼的暴力和特殊性质都是这么写的。有点寄。不过没关系，反正不是最后一年考 noip。

要润去学 whk 了/ll。