NOIP 游记

· · 生活·游记

NOIP 2024 游记 & AFO 记

突然发现自己马上 AFO 了。最后一场 OI 比赛游记，总要认真写一写，纪念一下我的 OI 生涯吧。

这次的游记的绝大部分是实时完成的，因此稍微有些长。不想看赛前集训的读者可以直接跳转到“比赛日”部分。

赛前集训

2024.11.18

停课集训第一天。

来到新机房，各种环境不熟悉，花了好长时间适应。

上午模拟赛成功切不掉蓝题。看来离一等差距不小啊。

复习 KMP,Trie，第一天就过去了。

2024.11.19

听课集训第二天。

今天是我场上切不掉简单 DP 的第二天。同机房一半人都 A 了。

攻克列队。花了 2h 才想通“实际删除的位置”是什么东西。我还是太菜了。

2024.11.20

今天校内模拟赛做的是我提供的题目！然后有题数据过水被错解跑过了 QwQ~

同学们全都把贪心题当 DP，图论题当 DP，然后真正的 DP 题没人做。

练字符串，练 DP。写题解。平凡的一天。

2024.11.21

模拟赛出了道高精度。与高精度斗智斗勇 ing。

这么魔怔的高精度题，怎么能不写魔怔一些呢？

for(int i=1;i<=n;i++)
    for(int a=mx[0];a>=0;a--)
        for(int b=mx[1];b>=0;b--)
            for(int c=mx[2];c>=0;c--)
                for(int d=mx[3];d>=0;d--)
                    for(int e=Maxp-1;e>1;e--)
                        if(dx[e][0]+a<=mx[0]&&dx[e][1]+b<=mx[1]&&dx[e][2]+c<=mx[2]&&dx[e][3]+d<=mx[3]) dp[dx[e][0]+a][dx[e][1]+b][dx[e][2]+c][dx[e][3]+d]+=dp[a][b][c][d];

模拟赛还出了道线段树合并。但如果我菜到连线段树合并都不会呢？

如何使用树上启发式合并与树状数组水掉线段树合并题？

2024.11.22

做蚯蚓以为 O(m \log m) 能过。我还是太天真了。

晚上学 Tarjan。怎么会有猫猫现在才学 Tarjan 呢？

2024.11.23

无意间刷到了邦邦的大合唱站队。一发最优解。

2024.11.24

梦熊周赛两个绿题场切不掉，40 + 32 + 4 + 0 = 76 遗憾离场。

吃完中饭回来把 T3 O(n) 做法写掉了。评价是 T3 < T1,T2。

晚上音游瘾犯了，开了一场 CF 虚拟赛，打的是 Codeforces Round 614 (Div. 2)。

结果呢？A 题用 lower_bound() 没判 end()，数组越界调了 50min。

回寝室 5min 想出了 E 题正解。要是 A 题一遍过就能场切 E 题了。但愿 NOIP 考场上不要重蹈覆辙。

2024.11.25

把 CF1292C 补了，顺便切了 CF1292D。要是 NOIP 场上也能切紫题就好了。

2024.11.26

模拟赛考了一道构造 + LCA 神题。

看了眼 CF1292E 。想了半天。您猜这么着？

My First Codeforces *3500 ACCEPT!!!

写了篇题解纪念这题。可惜洛谷现在 Codeforces 的 RemoteJudge 暂时不能用，不然我在洛谷就有黑题 AC 记录了。

2024.11.27

早上模拟赛打了 20pts。T1 死磕 3.5h，写完对拍之后终于发现推的性质假了。

晚上打机房同学 Misserina 出的信心赛，到处挂分，遗憾离场。

2024.11.28

什么是信心赛？

上午开了一把 NOIP 2023。

T1 是个签到题。我以为直接暴力比较过不了，于是写了个计数排序。

T2 是个虚点并查集，刚好碰到优势区（？）。调了约 1h A 了。

后面 2 题就不太好做了。T3 看懂题面后想了很久，只想出一个在特殊性质下能跑 O(n)，在非特殊性质下只能跑 O(n^2) 的做法。无论如何，能拿一点分算一点吧。

提交后只拿了 60pts，n=2000 两个点没过。不过无伤大雅。

此时已经只剩 20min 了。看了眼 T4，发现 32pts DP 特别好写，打完跑路。

总分 100 + 100 + 60 + 36 = 296，高于我近两场梦熊 NOIP 模拟赛的成绩总和 ( 214 + 76 = 290 < 296)。

现在谁才是信心赛？

2024.11.29

打各种板子。

打 SPFA。然后写着写着就成了 Dijkstra。

随手切了 催化剂。

打了一堆 Tarjan 多倍经验题。

打了一堆贪心。

把 Speaker 补了。或许是我不擅长 LCA，感觉这题异常难写。

最后还是打了线段树板子。

Monotonic Queue 题解审核通过。

最后一天了。祝我好运。

比赛日 2024.11.30

赛前

人（猫？）生中第一回参加 NOIP，也是最后一回。

赛前和同学一起打 Bounded Quietude，拿手机打的，爆了。

看起来考场内所有人都志在必得。这将是一场恶战。

我的考号是 ZJ-0147。今年浙江有 738 名考生，前 20\% 恰好等于 738 \times 0.2 = 147.6。

打了 4 年 OI 了，总得混个一等吧。

出师不利

进考场，解压，开考。读题。

T1 看起来像是个简单题。感觉稍微贪心一下就行。

T2 一眼没思路。

T3 一眼没思路。

T4 一眼没思路。

感觉已经没有 1= 了。

无论如何，先开始做 T1 吧。

举步维艰

稍微手玩了一下 T1，想出一个贪心。写代码。

写完了代码，测样例一。发现没过。输出中间过程，与预期完全不同。

发现是用 cin 读入的 bitset，应从右向左读。发现还是不对。

发现贪心策略有误。尝试调试，发现无法修正。

此时已经过去了 1h，而我场上只有 40pts。而这只是 T1。

NOIP，就这样结束了吗……

绝望的重新看了一遍后面的题。感觉 T2 似乎可做。T3 像树形 DP。T4 可以先把 LCA 写出来再说。

但我连 T1 都 A 不掉，我真的能做出其它题目吗？

突然想起 CSP-S2022 的经历，T1 怎么也做不出，而 T2 才是真正的签到题。教练说过：“不要对着一道题死磕太久，不妨先看一看其它的题目。”

又想了一会 T1，未果。带着失落，不甘，绝望，我看向了 T2。

此时已经过去了 1h30min。

拨云见日

T1 挂掉使得我没有想正解的信心。我先看到了 n \le 10^5 的那一档部分分。

很快发现 d 除了判断无解以外没有任何作用。初步写出转移方程。意识到这个式子可以压缩，用快速幂优化。

等等，这是……正解？

看了一眼后面的大样例，大致能验证自己的猜想。开始写程序。

测试样例。发现少量样例未通过。意识到自己写的式子存在一定问题。

写出新式子，发现换了一批样例未通过。发现这次没过的全是 v > 2 的情况。发现式子中一处忘记乘以 (v-1)。稍作修改，测试大样例，通过。

此时距离考试开始已经过去了 2h50min。

进退两难

做完 T2，又回去看 T1。想出一种修正原先贪心策略的方式，但很快被推翻。再次陷入沉思。

有的时候就是有这样的陷阱：感觉下一刻就会有奇迹出现，感觉下一刻自己就能想出正解。可是我的能力不允许这样的奇迹出现。

想放弃又不甘心，想坚持又做不出。这 T1 终于在我面前成了一块鸡肋。

只剩最后 1h 了。我还只有 140pts。难道这场比赛就将在这份迷茫中结束吗？

考场上你做不出正解，但这并不影响你 1=，因为你会打暴力。

不行，我不能投降。我将在这最后的 1h 中，写好我 OI 生涯的结尾，对 2019 年的我，做一个交代。

背水一战

终于放下了 T1 的死磕正解的心，开始拿部分分。

先从 T1 开始。n \le 10 这一档直接暴击搜索判断合法性即可。很快过了这档部分分，并通过了样例 1 以及样例 2 的前 6 个测试点。得分 +20pts。

再看 T4。在时间紧张的情况下，正当我考虑怎么处理区间 LCA 的时候，我突然意识到 \operatorname{lca}(u,u)=u，也就是说，它是个可重复贡献问题，可以用 ST 表维护！稍微调了一定时间，过了大样例。得分 +32pts。

此时离比赛结束仅剩 24min。

回去看 T3。看了部分分的分布，发现：

特殊性质 A：对于任意的 i(1 \leq i \leq n - 1)，都有 u_i = i, v_i = i + 1。

打开对应大样例，打开输出文件，发现全是 1。得分 +4pts。

剩下的点中，k=1 的部分分高达 24pts。时间紧张下，我简单推了一下，感觉树形 DP 可做。时间来不及了。

逃离 NOIP 的 24 分钟！我孤注一掷，将最后的时间留给了代码环节。

“离比赛结束仅剩 15 分钟。请考生再次检查文件路径，并填写源程序字节数表格。”

比赛结束前 10 分钟，要放下手头的一切事情，检查提交的程序。

还没有写完 T3。真的要止步于此了吗……

程序是死的，可是我们 OIer 是灵活的啊！

成败在此一举了。我做出了最后的，也是最冒险的决定——把 T3 写完。

终于写完了 T3。测试样例 1 通过。测试样例 3，发现没有一个数是正确的，全都差的很远。心态大崩。

const int mod=998244353;

哦，原来是模数写错了。那没事了。

改掉模数，再测样例 3，通过，跑得有些慢。没时间写快读了，希望不要 TLE。预期得分 +24pts。

此时离比赛结束仅剩 5min。再次确认了所有题大样例都能跑，填完源程序字节数表格，比赛结束。

赛后

感觉最后 1h 发挥的还可以吧。1h 打暴力出 80pts 也算是拼劲全力了。

唯一的遗憾是没场切 T1。这下成洛谷最菜 7 勾了。

打了一下午 Phigros，2939920pts 卡线没过金 46。于是又打了一晚上 CYTUS II。

逛洛谷。好像大家都会做 T1？

T4 强行预处理任意区间的 LCA 好像也能 32pts。还好我 ST 表打的熟，不然可能直接挂在这里了。

群友 T4 人均 32pts，但绝大多数人没打 T3 的链。

洛谷题目难度出了。哦，蓝绿紫紫啊，那没事了。

CSP-S2022 也是蓝绿紫紫，一等线 210pts。220pts 还有机会拿一等。

想了一会 T4 的链怎么做，未果。我也就这点水平了。

2024 年的 11 月在这场比赛中结束。

赛后

2024.12.1

一觉醒来已经是 12 月了。

回归文化课。唉我两周不在你们上到哪里去了？

跟同机房 OIer 交流。发现我 T1 的贪心策略是正确的，代码实现稍微改一个小错误就行了。可惜我在考场上一直用一种不存在的情况 Hack 了我的代码。

NOIP 唯一遗憾。

2024.12.2

对 CF1292 写的几道题的题解都过审了。

居然还听得懂文化课。集训两周再回到文化课跟过了一个世纪一样。

同机房 2 名同学因读错题导致 T2 没打。默哀。

晚上机房没开。走到机房门前，看着关着的机房，才意识到我（或许）已经不是一名 OIer 了。

2024.12.6

出分日。65 + 100 + 24 + 32 = 221pts，高于预期 (220pts)。

T1 错贪多过了一个点。符合我对 CCF 数据的想象。

T3 少过了一个点。难道链那一档分没拿到？

小图灵初评排位恰好 147（符合考号）！

做出 T1 的人好多。云斗榜上一大片 100 中留下我一个光秃秃的 65（其实还有一个 80 陪着我）。

2024.12.7

好像 T3 死因是二维 vector 存图挂了。详见此贴。

原来是没把数据读完啊，那没事了。

还好 CCF T1 送了我 5pts，不然真的要遗憾离场了。

简单的花 10min 修改了一下 T1 考场代码，AC 了。不知道该哭还是该笑。

同机房的除了 @ShenTianYi_ 大佬以外没有一等。

2024.12.17

信息课上摸鱼，发现 NOIP 分数线出了。

一等分数线 216pts，高 5 分压线过段！

同机房同学基本都卡在各自的期望获奖线上方。从某种意义上的大团圆结局？

@ShenTianYi_ 230 出头。明年一起去省选陪跑。

NOIP ，以及我的 OI 生涯，在这一刻结束。

后记

这回跟初三不一样了。这回是真的结束了。

记得 2019 年，连什么是“信息”都不知道的我误打误撞的加入了学校的信奥队。那年几乎什么都没学（学完一年才学到循环结构），但奠定了我后续对 OI 的热情。

真正起步是在 2020 年。结识了一批好朋友，在一个机房里一起训练，闲暇时间一直聊着 OI。

2023 年，初中的最后一场 CSP，集体爆冷，竟没有出一个（提高组）一等。面对学业压力，在最后一顿聚餐以后，大家都再也没有进入过（初中）学校的机房。

后来呢？高中（或者严格的说，预科？）一年级，我在 OI 上投入的时间与精力比初中还多。曾经的队友纷纷变为灰名，我的身边换了另外一群同学。

然后就到了如今。在 AFO 之际，我又回想起自己 OI 生涯中那些可能微不足道的“大事记”：

五年半时间转眼就过去了，其间有着我数不尽关于 OI 的回忆。时间虽长，但我过得异常充实。

我的 OI 生涯以一场 NOIP 结束。或许成绩一般，但对我而言，有那么一个爱好，曾经为之疯狂，为之痴迷，为之拼尽全力的奋斗过，就值得让我珍藏这段回忆，这段 Heroic Ages。

可能还可以参加省选，反正重在参与。之后，我可能会继续参加大学生竞赛。

这是一段故事的结束，更是一段新的故事的开端。

Burn to ashes into the sun

Till the end of the day you'll find out from your heart

Seeking the whole rest of brand new world

-- The Whole Rest, by Kiv\Lambda & Rua

鸣谢

小学 & 初中（这两个时间段几乎是同一批人）

全能神犇 @_StarBird_（不用代码框会导致下划线显示为斜体）

StarBird yydStarBird!

小K @Alphy

喵喵最可爱了，你说对吧，喵喵？

桂花包 @baoxuanming

“毕导”@UPwill

@spaceside

什么也阻止不了我刷水题！！！

@yushangchen

真実はいつも一つ

@paulChen

自缘本是OIer 投学二中白马湖

@junxis

Get busy living, or get busy dying.

初中教练 gzw

高中（预科一年级）

高中教练 @xaero7

@fang20081114

卡常大师 天蓝向日葵 @ShenTianYi_

我永远喜欢杭高钱江。

CSP-S2023 AKer @ShwStone

水出天际就叫水哥

@DNWdpl

东风夜放花千树 更吹落 星如雨 宝马雕车香满路 凤箫声动 玉壶光转 一夜鱼龙舞

甚至 e @EVENe

nao~ tan~

日记里没写就是忘了

宵宫梦男 @Naganorhara_Yoimiya

烟花易逝，人情长存

冰雪女王 @Misserina

杭高名媛米塞莉娜，EST？，aespa，seventeen，冰雪奇缘

@F000000

我才是na~ nong~

@klnoier

你说的对，但倘若我掏出奥地利算法、匈牙利算法、甚至e大力算法，我就是不可战胜的

@PtMiner

@iamchl

“我们喜欢 shw, zfy, zhx, C! H! L!”

珂学家 @Chtholly__Nota

总有一天你会静下心来像个局外人一样 看着自己的demo笑着摇头

rp++ Chtholly bless me

@zent

编程的尽头是摸鱼

@joy612

@wudi12345

我永远喜欢STY

@leafstyle

猫猫

可爱而单纯的猫猫 @lizihan250

这只猫很懒，什么也没留下

立在黑暗中凝视前方的猫猫 @che960

Can you hear me?

And You

……

而我们的故事，才刚刚开始……