NOI2026游记

· · 生活·游记

BOSS 关卡 NOI2026 已开启,D 类选手前来挑战。

笔试获得了 100pts。

Day1

很久没体验过紧张是什么感觉了。

意识到现在正在亲手书写自己的结局,开始紧张了。

还好比赛时间充足,调整调整心态,问题不大。

比赛开始了,怎么密码条还没发,延时了 5min。

比赛还没开始,但是却拿到纸质题面了,发现 T3 是交互,而我是交互高手,优势在我。

比赛开始了,不好 T1 怎么是计数题,不好的回忆开始涌入我的脑海:

联合省选2026:不会 day1T1,最后 day1 总分 27,直接崩溃了。

若干场模拟赛:被各种各样的计数题创飞,放在哪个位置都没 AC 过。

快停下来,现在可不是追忆的时候。

开始理性分析现状:现在我在考 NOI,不是神秘模拟赛,这道题肯定不会那么困难,而且我已经训练了一段时间,实力应该有所提升。

直接开始硬做,大约 25min 时会做了,边写边调最终在 60min 时自测取得了 100pts,心态有所恢复。

想做交互题了,于是开始看 T3,我会询问所有可能的数得出答案,可以获得不超过 20pts。

诶,这个把数混入其中然后升序排序我是不是在哪里见过,好像在 [APIO 2026 中国赛区] 蛋糕 里出现过,那这个题应该是蛋糕的续作,我应该猜对了吧!

30min 过去了,我却没有任何新的思路,甚至连方向都没有,这个 T3 何意味???

还是去做 T2 吧,让我猜一猜最优解的形态,猜对了,我会 O(n^2+q),获得 45pts。

我再观察一下,这个答案函数是不是可以三分,那我需要维护邻域信息,不好我的 DS 能力太低不会维护,先拼个 B 性质继续做 T3 吧,至此 100+50+0=150pts。

由于质数的数量很多,我意识到我需要利用数之间的相对位置,二分显然是不够的,当我打算分成更多区间时我发现这对询问的集合有很奇怪的要求,而且也会把候选答案集合分得很奇怪。

我先尝试花了 5min 手动构造了第一次询问,然后花了 10min 写了个答案集合大小检验器。

结果远超我的预期,我只用了 7 个数就把最大的可能答案集合大小从 3000 变成了小于 500 的一个数,而且仅有的 7 个可能答案集合大小超过 50 的集合的值域都是一个长度不超过 600 的区间。

我又望了望 T3 的 S \le 35,和这道题奇怪的评分标准,以及显示屏上 100min 的剩余时间。

我决定手动构造这 7 个大集合的第二次询问。

为了让询问集合的相邻两数的 \gcd 互不相同,我采用的方法是:打开计算器,不断地将两三个整数相乘并记录,然后运行检验器,选择表现较好的集合放入代码中。

30min 过去了,在使用计算器把几百个整数相乘后,我构造完了所有的第二次询问。

第三次询问我就询问所有可能的答案吧,先交一发。

我在自测中取得了 73pts。

现在我只用了三次询问,于是我在第三次询问前插入了一次二分。

我在自测中取得了 94pts。

现在我有 100+50+94=244 分。

我意识到 T3 大概率是随机区分题了,内心感到一阵狂喜。

这意味着,有不少数量的中高水平选手将会因为被 T3 区分打出比我低几十分的分数,我已经很难拿到 Cu 了,甚至可以冲击 Au。而且,这个分数已经超过了我打过的任何一场 NOI 模拟赛。

我完全放松下来了,最后的时间里,我调了调 T3 的参数,并在自测上取得了 98pts。

最终得分:100+50+97=247

什么?你说最后分数的计算方式是先下取整再相加?

查分过程中,我向同校选手展示了我手动构造出的由六七十个整数组成的几个集合,他们大为震惊。

Day2

鉴于 Day1 的表现如果 Day2 再有两道 D1T3 那我可能有 Au 了。

开始看题。不好,怎么三道都是传统题,预定 Ag 了。

先看 T1,简单看了看题意就翻到了数据范围一栏,然后我看到的:k=2,3,5,\le10,\equiv0\pmod 2,>5

现在我在考 NOI,不是神秘模拟赛,那肯定每个点都有一个做法,直接猜测存在一种做法能过 k>5 并会在 k=2,3,5 时假掉,然后这个做法需要对 k 是否为偶数分讨,然后存在一种暴力能过 k \le 10,拼上去应该就做完了。

思考过程较为顺利,90min 时自测 100pts。

剩下的 210min 好像都在鱼鱼。

T2 只会送的 20pts,而且我的 DS 能力极低,思考了各种特殊性质都不是很会。

T3 一开始想拿 n \le 16,后面发现自己什么都不会只能爆搜拿到 n \le 8。我决定尝试拿点非平凡的部分分,写了链的 4pts,然后隐约觉得自己想到了一个多项式解法,但是又觉得 D2T3 这个位置的题我不可能想清楚,于是放弃了。

最后居然没调出来爆搜,样例 #2 一直 WA,算了 8pts 又不会改变我的牌子颜色,不管了。

最终得分:100+20+4=124

什么?明明只有 n-1 个点有父亲结点但是题目给出的数组长度为 n

后记

NOI 居然有随机区分题了,这还是 NOI 吗。

有没有治愈系谷友陪我聊天,实在不行致郁系的也可以,如果我长时间没有回复可能是因为没有想到一个好的表达。

milthm 第二章更新了,喜欢看刀子(指剧情)是不是等于喜欢zc呢