NOI2025 夏令营游记

· · 生活·游记

前言：这是蒟蒻第一次参加 NOI（虽然是以夏令营选手的身份），很多地方都不太明白，所以就当去旅游了吧。

Day -?

第一次参加省选，竟然进了 E 类，获得了体验 NOI 夏令营的资格（不过 SX 应该算是非常好进省队的那一批了，省选不到 200 分都能进）。

Day 0

上午去看开幕式，节目基本都挺有意思的。

开幕式结束以后回寝室速通了一下 NOIP2024 的后两题，为下午的试机做准备。看到一半就去吃饭了，食堂的饭还是很不错的，还有免费的水果和饮料。

下午是试机+笔试，要提前一小时排队检录，因为是第一次参加，以为检录的时候不让带手机、书包之类的东西，导致没有拿扇子或者伞，都快被三十多度的气温热炸了。

试机的时候尝试去打 NOIP2024 的 T4，中间还考了一下笔试，AK 了。但打的 T4 却连小样例都没过，这时已经能回学校了，就不管了（反正是试机），先回寝室了。

试机的收获在于我调 T4 时 har 过来看了一眼然后纠正了我 T4 保存位置的错误，成功避免 Day1 爆零。

回寝室打了一些模板，不过似乎没什么用。

晚上十点多就上床了，然而可能是因为太兴奋或者太紧张了有点睡不着，一想到明早需要六点多起床就强制让自己睡，然而越这样越睡不着，硬是熬到了两点多才睡，成功复刻了省选 Day2。

Day 1

早上 6:20 就起来了，洗漱完了就去吃饭、检录。进场后发现其实也没那么困，至少是不影响思考的。

然后看 $T2$。先尝试发现一些有用的性质，不过没什么进展，于是看特殊性质 $A$。这个性质明显是说选出若干长度为 $2$ 的段变为 $0$，于是可以直接 $DP$。这启发我继续往选出若干段进行操作并变为 $0$ 的方向思考，考前练过一些类似的 DP 题，于是想到分类讨论每一段的情况，本质不同的有三种：从区间的右端点不断向左操作，从区间的左端点不断向右操作，从区间的左、右端点分别向中间操作并在某一个位置合并起来。 前两种可以直接暴力，问题是最后一种情况怎么处理。发现可以先处理出所有的前两种情况，然后枚举一个中点把两种情况合并起来。这样是 $\operatorname{O}(n^3)$ 的，想到这里时去上了个厕所，回来以后打算先看一眼 T3。 看了一眼 T3，结果发现不知怎么下手，尝试推了一些性质也没什么用，还是只会搜索，于是回去看 T2。 这时已经 $10:30$ 左右了，就先实现 T2 的 $\operatorname{O}(n^3)$ 做法。写完后发现第二问 WA 了，是因为一些情况算重了，简单特判一下就好了。 写完后尝试优化复杂度，但没有太多思路。这时我的 T2 是 $60pts$。观察了一下两个特殊性质，发现特点都是可能进行转移的区间长度不会太长，于是对于 $n$ 较大的情况特判一下，减少处理第三种情况的区间数，就有了 $75pts$。然而可能是数据过水，直接这样能过掉额外三个点的第一问，于是喜提 $81pts$。 回去看 T3，尝试分析特殊性质，结果发现还是只会搜索，于是用二十分钟打了个搜索，获得 $8pts$。结束后已经 $12:35$ 了，剩下的时间都在尝试分析 T3 的性质。 下午查分没去，因为太热了，让别人帮着查了一下，没有挂分。在寝室躺着摆烂，结果不小心错过了讲题，就没有去。 ## Day 1.5 上午去了绍兴城市展览馆和科技馆参观，感觉科技馆还是有点意思的。 下午组织去演艺中心看电影，要求必须参加，就只能去了。放了一个叫《人生大事》的电影，很多人看到一半就走了，我倒是看完了，只是疑惑为什么要在 Day 2 的前一天放这种题材的电影。 晚上去领了密码条，剩下的时间都在摆烂。值得一提的是这次在十一点之前就睡着了。 ## Day 2 早上 $6$ 点多就起床了，进赛场后也挺精神的。 拿到题以后先看 T1，明显是性质题。尝试通过样例发现一些性质，反反复复想了很多性质，又 hack 掉一些不对的发现，在 $9:00$ 左右时感觉好像想到了正确的性质：找出一个极长的前缀使得其满足所有这个前缀中的相邻的 $0$ 之间的距离都 $\le 1$，然后找到这个前缀后面的第一个 $0$ 的位置 $id$，答案就是 $n-id+1$。同时如果在这个极长前缀中出现了形如 $101$ 的结构，那么答案就要跟 $1$ 取 $\max$，写出这个暴力代码并且调正确后是 $9:40$ 左右，直接暴力加上特殊性质能拿 $70pts$。 看了一下 T2 和 T3，发现 T3 可以通过暴力 DP 加二分拿到 $10pts$，T2 貌似可以通过容斥、枚举等技巧拿到一些分，这时应该刚过十点，尝试去优化 T1。发现 T1 只需要快速求出一个区间内最靠前的 $11,0,101$ 就行了，这个东西很明显是能通过线段树维护的。然而因为一开始的想法出了问题，导致我打完 $300$ 多行的线段树后发现完全是假的，浪费了一些时间。这时是 $11:00$ 左右，尝试去推 T2 的式子，然而基本上毫无进展，就赶紧打了一个最裸的暴力 DP，复杂度 $\opertorname{O}(8^n)$，期望能获得 $16pts$。 这时还有 1h，我有两种选择，一种是好好打暴力，能多拿 T3 的 $10pts$，且有希望在 T3 获得更多的分。还有一种选择是去写 T1 的正解，如果写出来就能多拿 $30pts$，但可能来不及看 T3 更多的分，而且未必能在一个小时内写完 T1。我选择了去写 T1，这次换了一种线段树的写法，至少保证了正确性，在 $12:30$ 的时候把代码写完了，然而 WA 了，调了一会，发现是 $pushup$ 时没有初始化信息。调过的时候刚好是 $12:55$，最后拿到了 $100+16+0=116pts$。 因为 T1 的常数有点大，于是下午亲自去查分了（为了防止需要复评的情况却不在场），幸好没挂分（最慢的一个点跑了 $1.97s$）。查完分后又去听了讲评，感觉没怎么看 T3 是很大的失误。 总分是 $100+189+116=405pts$。 晚上有一个篝火晚会，然而并没有篝火。听说 $Ag$ 线在 $410pts$，一开始不太信，后来所有选手的成绩表出来了，一看排名发现自己直接排到了 $300$ 名，应该是 $Cu$ 了。 ## Day 3 $6$ 点多的时候突然莫名其妙响起广播，说 $6:50$ 要到地下篮球场集合，但看了一眼秩序册发现今天上午并没有要出学校的活动，就继续睡了。后来也没消息了，应该是放错了。 上午有一个《我与 NOI》的活动，今年 SX 竟然报了两个节目，总体还是挺有意思的。 下午是闭幕式和颁奖，$Ag$ 线还真是 $410pts$，那我这个分应该算是铜首了，虽然夏令营选手只有成绩证明（安慰自己初一有这个成绩已经不错了）。 闭幕式结束后还没吃晚饭，就提前离校了。总的来说，这是我第一次参加 NOI，有很大的收获，主要还是见了见世面，见识了一次大型正式比赛（至少旅游的目的达到了）。