NOI2024游记

也该写游记了。（本文唯一一个句号）

pre

省选寄了，喜提高贵的大 D

希望有 Ag

Day 0

报道日

中午，午饭后大概一点从代码源赶过来，正式入住

和本校 oier 切蛋糕，进行一个习俗的传承

领取徽章的时候，发现我之前剩余的徽章忘带了，导致徽章数量锐减

不过我之前由于不善社交，从来没有换完过，就这样吧

和 zkx，wyf 分到了一个寝室

在床上躺了一会儿，就和 wyf 打乒乓去了

晚上，尝试随机抽取几名幸运 oier 交换徽章

回来寝室，发现寝室成雀庄了（

由于人员往来，我的徽章很快就换完了

达成成就：Day 0 换完徽章

Day 0.5

开幕式

首先和各种活动一样，各种领导讲话

然后睡了

还是 dzd 讲话有意思

下午是试机和笔试，难得一次性打对了 .bashrc

练习题是 NOIP 2023，先写了 T1，用 selfEval 测试发现抱零

然后发现没写 freopen

改了过后发现 90pts，原来是没特判 n=1

成功做到做过的橙题吃两发罚时

然后是笔试

笔试刚刚放开的时候，听到一群人笑，但是我登录的时候发现上不去了

然后通知延迟 15min

之后不算顺利的完成了笔试（结束编号为 $pid 的进程我一开始选的 delete $pid，哄堂大笑了）

查分，没挂，问了一下 SX 没有人挂分

后来知道笔试一开始因为主办方没有 localStorage.clear(); 导致系统默认显示去年同考号的答案

而且题目除了“今年是第几届 NOI”都和去年相同，这道题的正确选项也和去年相同

这下真下发 std 了

回到寝室，别人复习板子，我开摆

Day 1

比赛日

没有晚起，赢

和 WC 一样，有纸质题面，于是没有去看电子版题面

值得一提的是，今年 NOI 是 THUSC 赛制，在 selfEval 里提供了和真实测试数据范围一一对应的 pretest

上来当然是先看 T1

感觉是那种只要会多项式复杂度就会做的题，于是尝试去转化条件

但是 1h 过去了，没有任何进展

1.5h 过去了，还是没有任何进展

这个时候不得不看看暴力了

首先看到了占据半壁江山的 m=5，搞了一个 O(nm!) 的做法，喜提 60pts

然后继续想正解，突然灵光一现，想到了下面这个做法：

考虑每一个集合 S，满足 \forall i\in S,i\leq m,|S|\leq 3

• 考察下标 i 满足 S\subset a_i，要求 \displaystyle |\cup b_i|\geq |S|

如果所有限制都满足，则区间合法

然后写了一个 O(2^knq),k=3 的暴力验证了一下，发现是对的

值得一提的是，大小不超过 3 的集合可以使用 basic_string<int> 维护，好像比自己写类要快

第一次调用函数 std::set_intersection 和 第一次在比赛中使用 std::back_inserter 祭

这样就有 80pts 了

然后想到好像不值得为了 20pts 去写正解，就去看 T2 了

此时已经大概过了 2.5h 了

T2 的 15pts 是简单的，先拿到手

然后尝试去阅读那个分数表，看了半天也没看懂它在说什么

首先写了一个分治算法，好像有 20pts？

发现这样会导致 t 很大，于是进行了一个优化：

• 在 n < LIM 的时候，把二分改成四分

进行调参，这样就有 42pts 了

接着，把四分改成五分，就有 48pts 了

一共 64pts

然后尝试组合四分和五分，发现没有再高，就去看 T3 了

此时大概还剩 1h 40min

想了一会儿，发现想不到 O(poly(n)) 的算法，就去看特殊性质

A 是奇偶染色后分别去计算，B 是 2 sat 或者 bitset 传递闭包后去判断？

突然想起来好像 T1 的正解还没写，于是翻回 T1

发现 T1 答案可以双指针，于是写个双栈模拟队列实现不带删的尺取

写完后发现样例 2 挂了，调了半天

终于在还剩 30min 的时候调了出来：队列重构时入队顺序反了

多次测试，selfEval 上最后一个点最慢的时候跑 0.94s，不知道正式数据能不能过

然后赶紧 rush 了 T3 的 A 性质和 O(2^npoly(n)) 的暴力

然后发现我 B 性质假了：传递闭包是 O(\frac{n^3}{w}) 的，我之前按照 O(\frac{n^2}{w}) 想的，这样 B 性质只能过一档分了

此时还剩 10min，写了几行后放弃，觉得不如检查一下之前的代码

然后就盯着三个文件看直到比赛结束

估分：100+64+20=184

出来过后我听到的都是上了 200 的

吃完饭和本校讨论，发现成功成为本校垫底选手

T1 只要判断位置的集合“同构”即可，大家好像都是 1h 以内过的

T2 除了我都是 78

这下寄了

下午查分，大家都没挂

随了 24 个人，发现我是 rk17，按照比例来算妥妥的上位铜

此时想银只有靠 Day 2 翻盘的

但是我的 OI 经历中还没有翻盘成功的经历，这次，又能成功吗？

算了算了

反正是 D 类，打成什么样都无所谓

和 wyf 约着去打乒乓球，但是被教练强迫去听讲题

去了发现 T2 只需要一个 dp 求出决策点就可以很轻松的获得 90

交互题 dp 出最优策略这个套路我之前又不是没见过，怎么之前就没想到呢？

说什么都已经晚了，打球

回到寝室，别人复习板子，我开摆

Day 1.5

社会实践日

去了重庆三峡博物馆

很好的一次经历，不懂为什么很多人之前不愿意去

回到寝室，别人复习板子，我开摆

Day 2

比赛日

没有给自己设定什么目标，比如说必须翻盘什么的，因为根据以往的经验这样只会适得其反

打成什么样算什么样吧

先开 T1，什么抽象题目

肯定是找性质

发现定义2和5是没用的，只是为了样例解释

然后写了 O(nm\log n) 的算法（我对于 \forall i\leq n\forall j\leq m 求了 \gcd(i,j) 可能是 O(nm) 的），6s 跑过了，有 50pts

然后我尝试把所有完美正分数打表打出来，发现它们是由几条直线形成的

（也就是说，有一些一次函数的 pair (f,g) 使得 (f(x),g(x)),x\in N^+ 都是完美正分数）

于是，我尝试找出这些 pair

我找啊找啊找

找啊找啊找啊找

找啊找啊找啊找啊找

直到后来发现这个行为与 观察素数螺旋来尝试推导线性筛 一样愚蠢

遂放弃

然后灵光一闪，发现直接 dfs 可以做到 O(答案)

写了，发现有 85pts

然后尝试去写一些类似根号分治的正确性未知的做法，没有多获得一分

此时已经过去 3h，赶紧看 T2

感觉是一个长链剖分+线段树的题，感觉是可以想出正解的

于是想了 1h

发现不仅正解不会，任何一个特殊性质都不会

赶紧写了 O(n^2) 暴力开 T3

首先 A 性质是送，找到缩点以后入度为 0 的点，如果只有一个，那么这个点代表的点是 2，其他是 3

一开始以为 B 性质也是这样，但是没过样例

然后乱写了一个复杂度不低于 O(n^2) 的搜索过了 B 性质的第一档

只剩 8min 了，赶紧 rush 测试点 1

写完，样例过，selfEval 挂

最后 1min 多，发现二进制枚举的时候 i&(1<<(j-1)) 写成了 i&(1<<j)

改完，把三个题都放上了 selfEval，等到比赛结束后几秒才跑出结果，过了

估分：85+25+25=135

比赛出来，听到了讨论声音有比我分数低的，感觉应该是比 Day 1 打的好

下午查分，一分没挂，我校其他人也都是两天一分没挂

加上 Day 2，仍然是 SX 倒 3，我不好说

先是听说银牌线 400~410，然后听说金牌线 540，教练说银牌线 540-100=440

感觉应该是没用银了

没去听讲题，逃去打球

晚上是嘉年华，去嘉年华的路上看到了成绩公示，数了一下我前面有 266 个人（显然有几个误差），按照去年 D 类银以上 55 人来说是没有银了

失望

去嘉年华没带手机

在嘉年华，也不去想之前的事了，只想着玩耍

很难得，体会到了纯粹的欢乐

回到寝室，群里说银线 409

一开始我是存疑的，直到教练给我发了一个 409，我才真正相信

非常高兴，跑到食堂撸串，后又去操场上唱歌（主要是想唱但怕人听到）

今朝有酒今朝醉！

Day 2.5

上午是演讲和节目

值得一提的是，rzh(@rzh123)，zjx（@zhjxaoini）,wyf（@wYYSZLwSSY）演唱了《夜空中最亮的星》，这是 SX oier 第一次在 NOI 表演节目

银线出了的时候，我本来也是想上台的，但是由于他们排练的时候银线还没出，这个时候再加入显得太“见机行事”了，就没去

下午是闭幕式，D 类非金不予颁奖，只有一张废纸

晚上飞回了 TY

suf

这次 NOI 也算是这个赛季的完美的句号了吧

我这次虽然没有较大的失误，但是水平没有完全发挥出来

至于总结，一句话概括：平常心去考 NOI，在非极端情况下（比如 Day 1 这个我分数指望冲金）不要走极端，不要提前放弃，说不定就有好的结果呢

也是时候道别退役 er 了

我也要 std::this_thread::yield(); 了

Goodby，OI！后会有期！