Travel「NOI 2025 游记（VP）」

denominator · 2025-07-18 10:03:28 · 生活·游记

上一次：联合省选 2025

游记全集

这是一篇 VP 记，这是因为作者太菜根本去不了 NOI。

Day 1

Day 1 在机房的 NOI Linux 电脑上模拟，时间 11:00~16:00。

（你说的对，但是并不模拟，没有 pretests 和 selfeval）

开题看 T1，什么糖题啊？？？建分层图后不就 \mathcal O(m) 条边吗？？？

然后一度认为自己弄错了，边数 \mathcal O(m^2)，思忖了半天觉得还是当暴力写写，结果调第二个大样例发现确实是 \mathcal O(m) 条边。

在反复自我否定下在 1.5h 才切 T1。

在 T2 和 T3 中认为 T3 有更加有趣的性质可以玩玩（因为发现答案全是 2 的幂次），而 T2 这一抽象题面看都不敢看一眼。

认真读 T2 后，发现这 A 性质不是送的吗？写俩 dp 上去。

之后开始思考，发现可以将一段区间最多留下一个数，也就是以下三种情况：

1. 左边留下一个数；
2. 右边留下一个数；
3. 通过类区间 dp，将上下两种情况合并。

这好像是个 \mathcal O(n^3)！遂码码码，结果第一问全过了，第二问全寄了。不知道哪里数重了，可能是对于 1 与 2 中只有一个数的情况的讨论？

然后大力推 T3 性质，发现 A 性质做完这题基本做完了，但是手模样例发现可能不是。然后就考虑 B，甚至 AB，发现都很难碰，最后索性写最低分暴力跑路。

现在面临三个选择：

• 调 T2 第二问；
• 将 T2 的 3 优化到 \mathcal O(n^2)；
• 继续推 T3，

可惜我一个也没成功……最后只有一个丢脸的 100+32+8=140 滚粗。

看 T2 题解，自以为无限接近正解。

看看洛谷评分：绿紫黑（晚上再看 T2 升黑了）。

Day 2

Day 2 在家里模拟，但是没有 NOI Linux，时间 7:00~12:00。

仔细看了三题之后（其实 T3 没看），一口咬定 T2 是最水题，是 FMT 版题，遂回忆 FMT，推半天柿子，发现推出的柿子全是错的，例如最后一次算的是 P\neq Q。有点难绷，先回到 T1。

初始认为，前导 0 可以忽略不计，按照前两个数分为 11 型和 10 型。仔细研究样例解释发现，11 型时第一个 0 在 f 操作后恰好往右移一位，移到全为 1 时结束。

而对于 10 型，初始猜想是答案全为 1，不过观察它们经过一次 f 操作后还是 10 型，但答案是 0。之后很快就发现，如果 10 型中含有 101 或 110，肯定是能继续操作的，不然答案为 0。对于含有 101 的，发现经过一次操作后肯定结束，但是不会证明；而对于含 110 的，发现神似对于 11 型的分析！随即找到了对于 110 和 101 分析的 key observation！

不写暴力了，直接上线段树，但是维护 14 个信息是真的……不过还是很快过了大样例，还跑进 2s 之限。但时间已经过去 2.5h 了！太糖了！

然后硬想 T2 无果，想 T3 \mathcal O(nq\log n) 无果，直接逼到最后 1h，还是剩下两个选择：

• 写 T2 24pts 的 n\leq 10，但是没想明白，很可能错；
• 写 T3 10pts。

我果断选择了后者，一开始以为细节很少，测第二个大样例时才发现一堆细节……最后结束了还没调完。

不过始终以为 T2 很糖。

测一下！95+0+5=100。嗯？T1 怎么挂了？

有趣的是，pt 得了 80pts，已经料想到在 NOI 考场上看到这测试结果着急，结果只多得 5 分的样子了！

看来 T2 tj，才发现与正解相距甚远。

笔试看作 ~100，过了 Cu 线。

Day 4

在平板上看出 D2T1 代码的锅。