NOI 2025 游记

· · 生活·游记

前言：食堂的饭很好吃，而且有芬达，雪碧，可乐三种饮料无限加。个人推荐往瓶中放入半杯菠萝片，然后加足量芬达至浸没所有菠萝片，静置5分钟后饮/食用更佳。

上海 D 类选手来挑战 NOI。

Day 1

开幕式和同学一起看题，同学一眼秒了两道 JOI，畏惧了。

开幕式的音乐很吵，没法专心思考，导致我一道题都没有口胡出来。

下午考笔试，考的时候忘记了 bit 和 Byte 的区别。有一道题问我 bit 的含义是二进制位还是字节，这道题纠结了半小时，最后想起一个叫 bitset 的东西，猜测应该是二进制位。

赛后我去问同学，同学一致和我说：“还在演！”就是不肯告诉我 bit 到底是什么含义。

笔试 100 分。

Day 2

扫视一遍，感觉 T1 很不可做，于是先做 T2，思考半小时无果。

回头思考 T1，发现非常困难，如果对于每个节点以及机器人的状态都建一个点的话，点的数量级是 O(nk) 的。（当然实际上每个点只需要对每一条链接它的边建新点就可以了，但我没想到）思考良久，写了一个常数巨大的抽象做法，过了。

T2 的操作是让一个数减去它的一个邻居，考虑减不好做，于是让 a_i\leftarrow (-1)^ia_i，这样操作变为让相邻两个点中绝对值大的加上绝对值小的那个，然后将绝对值小的设为 0。

此时问题的结构就非常清楚了，只需要把 [1, n] 切割位若干个互不相交的区间，每一个区间内的所有数都加起来放在某个位置 k 上。（当然，k 必须符合一定的条件）。 那么对于第一问，可以直接 DP，稍微优化一下做到 O(n^2)，取得 40 分。

作为一个在 NOI 前打的十多场模拟赛中没有场切任何一道题的选手，此时我得到的 140 分已经超过了任何一次模拟赛的分数。

当然第二问和第一问差不多，不过第二问要求不能把一个最终序列重复统计，那么只需要规定对于切割出来的任何区间 [l, r]，不存在 k\in [l, r] 使得 [l, k] 或者 [k, r] 的和为 0 并且能缩成一个数。

那么用 DP 维护这个东西，容易做到 O(n^2) 直接通过。

过了前两道题后，我对自己非常自信，于是尝试冲击 T3 的 A性质。从 11:00 一直做到 12:57 后发现我的做法假了，于是三分钟极限冲击暴力，狂砍 0 分。

Day 3

去了神秘科技馆，太好笑了，一路都在笑，笑得肚子疼。感觉不如隔壁的儿童乐园。然后又去了一个不知道什么馆。

下午看神秘电影，一直在做 P10440 [JOISC 2024] 环岛旅行 (Day4) 但是做了一整场电影都没做出来，电影结束后重新思考一下很快就会了。

（电影叫《人生大事》，主角有 5 个父母，其中三个是父亲，两个是母亲，有点抽象）

Day 4

先开 T1，写了个暴力找一下规律，发现只需要找到第一个 形如 110 的位置即可，写一个线段树维护一下，直接通过。（当然如果不存在 110 则需要特判一下是否存在 101）

思考 T2，先思考如果 a_i=1 怎么做，此时是一个纯计数题，发现能容斥。

考虑把容斥推广到 a_i\ne 1 的情况，推一通式子后，发现变成了卷积的形式，直接上 FWT，通过了所有 B 性质。

考虑如果 a_i=998244352 怎么办，此时会出现除数为 0 的情况。

正在这时，我回想起来以前读闲书时读到过 《高等数学 第七版上册（同济大学）》第一章第四节中介绍了无穷小和无穷大，于是只需要考虑在极限过程 \varepsilon\to 0^+ 下，将所有乘数/除数中的 0 替换为 \varepsilon。具体来说，对于每个数字，维护整数 k 表示它是 1 的 k 阶无穷小/无穷大。

然后直接通过 T2。

还有两个小时做 T3，显然有 O(nq\log n) 的暴力，半小时获得 35 分，最后一个半小时尝试优化无果，狂砍下 0 分。

总结：100(\text{笔试})+100+100+0+100+100+35=535。

upd:得了银牌。虽然没有 Au，但作为 D 类选手有 Ag 已经很满意的。