MENU

NOI 2024 游记

人生中的第一个 NOI。

Day -1

比外校的其他同学提前两周到了重庆,在南开中学参加集训,有极为强大的讲师团队。模拟赛打的感觉还不算很差,不过除了补题之外基本也没做什么别的题了。

UNR 个人觉得打的也不错,能拿的分都拿的差不多了。

下午和外校的其他同学汇合进入重庆育才。WC 已经来过这里了所以校园倒也没什么新奇之处。值得一提的可能是这次育才在校外布置了很多宣传海报和旗帜,给路过的人一点小小的 NOI 震撼。

晚上跟着马思博四处换徽章,马思博还是有人脉的。意外捕捉到了 zak,成功交换徽章,赢。

Day 0

基本没复习笔试,在电脑里下了个 Despised 但是没怎么用过,可能就是 UNR 的笔试场稍微练了下手。考笔试之前的半个小时紧急进行了一波复习,感觉还是能拿下的。

笔试在试机进行半小时后开始。笔试开始后因为网有点卡所以迟迟进不去答题界面,但是此时已经有点喧哗了,进答题界面一看发现怎么答案都已经选好了,简单做了几题发现答案好像都是对的,这下下发 std 了,于是果断保存网页。工作人员紧急修复了这个问题但是题目完全没改,选项顺序都没变,保险起见还是自己做了一遍,然后和 std 比对一下发现没有差异,那就很稳。

赛后有说法是这个提前下发的答案是去年同考号选手的答案,有选手被坑了。去年的 HB-02 也很厉害。

Day 1

开考首先发现题目摘要里多了「pretest 数量」这一栏。pretest 和大样例并不等价,今年的大样例都没有给到极限数据,给的一般是中等大小的样例或者特殊性质。pretest 可以用 selfEval 测试,只能看评测结果,看不到测试点内容,但是 pretest 和正式数据的性质是一样的,也有说法说两组数据是用同样的 gen 生成的。看来 NOI 要变 IOI 赛制了,这是巨大的进步。

顺序开题。T1 想了一段时间,想到可以维护每个元素在哪些集合中出现过之后这个题就好做了,大概 1h 的时候理清楚了做法,但是我做法里有二分哈希以及二维数点,所以写起来有点答辩。大概 2h 的时候过了这个题。

T2 发现居然是交互。这个时候脑子有点不清醒。sub 1 是直接暴力,sub 2 可以将元素任意匹配之后将问题规模减半,这样是 $\log n$ 次请求,$n-1$ 次询问。场上想过分块,然后块内暴力块间做这种两两匹配的操作,但是这种操作在元素个数很多的时候是劣的,不知道为啥当时我就止步于此了。事实上正解是在元素个数多的时候两两匹配,元素个数较少的时候再用 dp 求最优的分块方式,用询问次数换请求次数。场上拿 26pts 之后脑子里啥都没有,不知道能咋做,认为这个题困难,然后只能去看下一题了。

T3 想了半天感觉只会 $O(n^3\operatorname{polylog}(n))$,因为不知道怎么找满足两点间路径上只有一条边方向未确定的点对,所以只好每次都暴力将所有边扫一遍判断是否符合条件。写了个 $O(n^3\log n)$ 的东西,结果发现其以非常快的速度过了 $n=2000$ 的点,以为是算法在随机数据下表现优秀。这玩意正式数据也跑过了 $n=2000$。讲完题之后会宿舍想了一想,发现事实上每条边只会被找恰好一次,所以复杂度就是 $O(n^2\log n)$ 的,那就很有道理了,感觉其他 $n^3$ 过 $2000$ 的选手也有可能是复杂度没分析清楚。本来还准备打菊花的部分分,先以为直接并查集可以维护,结果发现需要求 2-sat 的最小字典序解,这玩意我会做线性但是太难写,并且好像只有 4pts,遂放弃。最后这题拿了 56pts。

Day 1 总分是 100 + 26 + 56 = 182。显然是非常低。T2 感觉很白给,但是我基本没拿分。如果是 UNR 或者 CF,别人的高分还能提示我这个题是简单题,这样大概率我是能过这个题的,可能这就是 NOI 赛制和其他赛制很大的区别。

Day 1.5

社会活动去参观三峡博物馆。我看博物馆可能看不出什么名堂,我没啥文化的。

Day 2

T1 是个很怪的东西。可以用类似辗转相除的方法判定一个二元组是否合法,但是这样做没啥前途,分析性质和打表也都没看出什么有意义的东西。可能唯一观察到的事情就是合法的二元组数量很少,并且由于我们可以为每个二元组确定唯一的前趋,直接 dfs 就可以不重不漏的生成所有合法二元组。简单卡常可以让搜索次数做到 $ans / 2$,这样就可以拿到 90pts 了。有效代码只有 10 行左右。总共花了 1h,然后弃了,再做感觉没什么意义了。

T2 感觉有点困难。T3 是图论推性质题,感觉部分分是好写的,于是决定先写 T3。

A 性质很平凡,直接缩点就行。同时有 B 和 C 简单推一点性质即可做到线性,这样想 $O(n)$ 解决 B 要做的就是找任意一个一类点,我认为这个我是会做的,而且这玩意好像是有 20 多 pts,很想写这个部分分。狂暴敲了 150 lines 发现假了。NOI 场上的 vscode 没有 timeline 功能,没法回退到代码以前的版本。这个题的代码虽然不难写但是是由巨大多 dfs 拼起来的,所以写起来极为恶心,没有版本控制更是雪上加霜,改着改着代码可能就废了。好在有一些手动备份的版本。3h 后放弃了 B 性质,30pts 跑路,比大多数人可能就是多拿了 BC 那一档分。

然后 T2 只剩一个小时不到了。想了一会儿感觉是会 $O(n^2)$ 的。写着写着觉得不对劲,好像只会 $O(n^3)$ 啊。时间实在不够了,写点分也比爆零好,所以 rush 了一个 $O(n^3)$ 的东西,拿了 15pts。感觉部分分有很多能写的但是都没时间了。

Day 2 总分是 90 + 15 + 30 = 135。

晚上去嘉年华把所有项目都玩了,还是很有意思的。还和小粉兔换了徽章。

Day 3

总分是 100 + 182 + 135 + 5 = 422。民间有说法是 Ag 线 409,那还是比较好的。

颁奖时分数线确实是 409,压线拿了 Ag。

xxy 拿下 Au,不愧是湖北队长。

这次的 NOI 毫无疑问发挥的非常差。做 NOI 2023 的题的时候我觉得我上我也行,感觉真的是有拿 Au 的希望的,但是事实上如果是场外看今年的 D1T2,我肯定认为这是送的,事实上场上又只拿到了那样的分数。

可以发现两天的 T1 和 T3 可能打的都还行,问题出在 T2 上。这可能主要是对题目难度判断以及时间分配上的问题。从今年 NOI 的情况来看,如果目标是 Au,两天的 T2 恐怕都需要通过,或者至少拿到接近满分的分数,所以 T2 是需要优先拿出一些时间来解决的。对于 D1T2 那样放在 T2 的非传统题,更好的方式可能是告诉自己这题不会太难,并且如果知道自己的思路没有前途,就先去写 T3,或者上厕所,换个脑子再回来做,直到有靠谱的想法再拿出较多的时间冲击高分。

离金牌到底有多少距离,还是有点难说的。

总之今年 NOI 是一次珍贵的体验,OI 生涯可能在此刻需要告一段落了,高二不可能像高一那样拿太多时间出来训 OI。今年能拿 Ag 是幸运的,剩下两年 all in 文化课也能有不错的前途,虽然这样有点太无趣了;但事实是,对我来说拿 Au 是需要运气加持的,NOI Au 的容错在变低,还有随机区分的题会把人创死,太多时间学 OI 也不合理,更何况我的文化课底子并不好。究竟怎么规划,可能只能走一步看一步,能够再战 NOI 2025 自然是好的。

当然从另一个角度来说,经过一年的训练,现如今我对 OI 的热情恐怕早就不及当年了。虽然拿到题目还是能够专注到题目中去,但是并没有激情像以前那样维护博客,以及高频率的参加比赛。以这样的状态,可能从一开始我就没有想过能在今年就拿下 Au。两年前我就写过有关压力的东西,恐怕现在不是压力的问题,而是动力的问题。我的未来会何去何从,我确实也不知道了。

湖北新高一目前来看没什么强力选手,不过一年的时间足够让一个努力且有天赋的人脱胎换骨,还是很期待新高一新人的表现的,感觉老登们战斗力都不是很行。也期待远处 hsy 的表现。

Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment

2 Comments
  1. DengDuck DengDuck

    刘老师好厉害!!!明年继续加油啊!!!

    1. @DengDuck奇怪的称呼增加了