NOI 2026 游记

· · 生活·游记

Day -?

UNR。

Day 1 秒了 T1，T2 在想出来 O(n^4) 做法之后对着 200 的范围不敢写，然后想了一万年 O(n^3) 做法。T3 数组开小喜挂 15pts。

Day 2 秒了 T1，T2 容斥完就不会做了。T3 很快会了一个树分块，结果调到 4h 时发现假掉了，紧急修完就来不及卡常&写暴力了，发现最终得分等于拼三个暴力。

最后 rk~60。如此状态，如何 NOI？

Day -1

报到日。

根据去年的经验感觉并不会有人跟我换徽章，加上 HB 今年并没有志愿者，于是就懒得定徽章了。

感觉不应该在 NOI 前做难题了，于是在上飞机前挑了几道简单题，准备在飞机上想。结果落地的时候一道都不会做，感觉已经无敌了。

下午一直在寝室待着，把早上两道题的代码补了一下。

Day 0

开幕式&试机。

感觉开幕式真是拉完了。表演了一堆诡异的节目，dzd 讲话看上去也是按着稿子念的。

下午笔试没挂分，目前 100+5。不过试机题怎么是 WC 的，难道说 NOI 也要改成交互格式了吗？

晚上感觉比较紧张，听教练的建议在外面散步了很久。晚上稍微有点睡不着，最后一次看到钟大概是十二点。

Day 1

早上起来稍微有点困。

开场先把三个题都看了一遍，发现果然是三道交互格式。决定顺序开题。

想了 0.5h T1，感觉会了一个 O(nm^2K) 的 dp，并且感觉能优化一下做到大概 O(nmK)。于是直接开写，获得了 15pts 高分。准备优化的时候发现我的做法好像空间也是 O(m^2K) 的，并且要开 vector，那感觉已经倒闭了。

大概在 1h 时的时候 T1 还是没有任何进展，于是决定换题。

感觉 T2 每个点的决策只与其到目标点的距离有关，那枚举一下答案的范围，然后解方程应该就行了，能做到 O(n^2)。写了个暴力验证一下，发现还挺对。猜了一下可以二分答案，打表发现还挺对，然后就是一个邻域数点的问题了，写个点分树应该就能做。这个时候大概是 1h40min，怎么感觉 T2 比 T1 简单？

决定等会再实现 T2，回去重新看 T1。感觉不管怎么样都没办法压缩空间，因为必须要记录其中的两个端点。然而在上厕所的时候突然发现 k 这一维是可以滚动数组的，然后就基本会做这个题了。大概在 2h 时过了 pretest。

回来写 T2，在不到 3h 时过了 O(n\log^2 n) 的 75pts，3.5h 时卡到了 100pts。

看 T3，先把 Sub1 过了，加上 Sub2&3 获得了 17pts 的高分。然后试了一下前三次问 \{2,4,8,16,\cdots\},\{3,9,27,\cdots\},\{5,25,\cdots\}，好像是获得了四十分。感觉这些集合能区分的数还是太少了。试着做了一下 Sub2，发现质数集合就已经很不好区分了，只能用一个相邻数 \gcd 互不相同的集合来将其按大小关系划分。于是手搓了一个有十几个数的集合用于第一次询问，二三次询问就找一对 \gcd 不为 1 的数大概二分一下。发现直接过了 Sub2，交一下获得了 70+pts，感觉很牛。后面卡了一下常，最后做到了 83pts。

出考场的时候感觉这个分挺不错的，但是后来又听到很多对线要到 280/290 的传闻，感觉还是有点慌。

查分没挂，100+100+83=283。

Day 1.5

社会实践。

不是很懂为什么要五点半亮灯。不是很懂为什么不到一小时的车程开了两个半小时。不是很懂为什么只参观了半个小时就要回学校。不是很懂为什么返程又等了一个多小时的车。感觉回到寝室已经筋疲力尽了。

下午没看电影。吃完晚饭又散步了一会。今天入睡还算比较早。

Day 2

依旧三道交互，不过看上去好像没有真交互了。还是顺序开题。

T1 二分答案应该是比较明显的。然后感受一下，在转成 01 序列后，大概是要找到连续两三个划分成 1 的段，但是要对 k=2/3/5 特殊处理，然后还要考虑 k 的奇偶，还要对边上的段特殊考虑。花了 1h 才大概理清楚要分讨哪些类，在快到 2h 的时候过了 pretest。感觉大分讨题还是太超前了。

然后是 T2。简单转化一下变成了问点 x 被删除的时间。考虑记录当前编号 \le x 的个数 y，操作就相当于 y\to \max(y-1,0) 和 y\to y+1，若碰到了一个 \le x 的点最后一次出现则会执行第二种操作。写完暴力获得了 25pts。

发现上面这个东西需要同时对编号和区间右端点扫描线，然后也有单调性，所以直接莫队+分块维护一下就做到 O(n\sqrt n) 了。非常好写，过 pretest 大概是 3h。这个时候算了一下得分，发现已经有 588 了，感觉很激动。

花了一小会平复了一下心情来看 T3。感觉一个点祖先有和其颜色一样的点不太好做，于是先容斥成了一个点祖先没有与其颜色相同的点。结果写完代码才发现完全倒闭了，因为一种序列对应了多种涂色方案，然后就会出问题。然后就只能对着原本的条件硬做，最后搓出来了一个一百次方的 dp 套贪心，最后 10min 才调出来，获得 32pts。

出考场水群，发现有人说 T1 pretest 数据很水。想了一下，感觉我的 T1 好像也会有问题。于是煎熬地等到了查分，最后还好是没挂，100+100+32=232。

总分 100+5+100+100+83+100+100+32=620，rk 17。

Day 3

紧急逃离了 cyyz。