专栏文章

NOI2024 翻盘记

NNesraychan
生活·游记参与者 26已保存评论 25

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
25 条
当前快照
1 份
快照标识符
@mhza20hd
此快照首次捕获于
2025/11/15 03:55
3 个月前
此快照最后确认于
2025/11/29 04:47
3 个月前
查看原文
前排提示：这里的“翻盘”指的不是 Day1 寄了 Day2 翻盘（虽然也有一点？），而是 Day2 单场比赛的翻盘。

2024.7.12（UNR 笔试）

没看到与题库相比改了答案，喜提 9999，正赛可不能这么粗心！

2024.7.13（UNR Day1）

唐完了。
上来 A 结论假了，浪费了一个小时。
B 式子推错了，改对后以为单次复杂度是 O(V2ln⁡V)O(V^2\ln V) 的，想了好久怎么优化。
最后一个小时看 C，被榜诈骗了。以为是简单题，激进起来想正解，结果暴力分只拼了一点点。
喜提 100+100+14100+100+14，rk74。

2024.7.14（UNR Day2）

应该能稍微翻下盘吧？
A 看完题就会做了，成功抢到了一血。
B 写了一个 O(nlog⁡V)O(n\log V)，样例过了 8080 分。
C 先拼一点暴力，发现写了随机的分就可以过所有样例，预感又要有人被诈骗。
后来在 BC 之间反复横跳，但啥都没想出来。
100+40+40=180100+40+40=180，单场是 rk27。
两天合起来只排在 rk47，成功 Ag。达成成就：UNR 排名是去年的五倍有余。

2024.7.16

报道日，发现宿舍是按学校顺序排的，舍友是 sky 和两个双十的 D 类。
拿到了徽章，但决定在考完 Day2 之前还是先不进行什么社交活动。

2024.7.17（笔试日）

开幕式 dzd 依旧稳定爆典，贡献了选手们为数不多的笑料。
其他部分也就中规中矩，除了后面这个表彰仪式简直又臭又长/qd。
下午笔试，做了两题之后发现帮我选好答案了？？？致敬传奇出题人 Zayin。
于是延时了 15min15\text{min} 后重新开始，我没存答案，不过还是顺利 AK 了。
出来听说下发的是去年同准考证选手的答案，有人被坑了。
晚上睡得很好。

2024.7.18（Day1）

开题先看了一圈样例，发现 B 是个交互，大感不妙。
从 A 开始开，第一眼不会，想了一下发现构成双射的数之间可以随意选择匹配，这样就会多项式复杂度做法了。
想了一下可以哈希优化，加上双指针从以做到线性，在大约 15min15\text{min} 的时候通过所有大样例。
打开 selfeval 一测，发现给我爆 ce，看了一下代码感觉没问题，于是举手向监考求助。
他过来一顿指点，又让我交了好几发 ce，然后去问技术人员怎么回事。随后通知说 selfeval 锅了，正在修。
于是先开 B，一开始没看清楚数据范围，以为直接分治就做完了，写了一下发现算上第一个包只有 2626 分。
期间 selfeval 修好了，一测发现怎么 A 有 2020 个点？pretest 赛制？好时代要来了？
想 B 的优化，感觉可以随着层数的变化从二叉变成多叉，写了一个贪心状物拿了 5252，再加了一个剪枝获得了 6969。
先丢掉开 C，很快就观察出了结论，写了个 O(n2)O(n^2) 获得 5656 分。发现只要每次快速找到只剩 11 的路径就做完了，感觉自己能做出来，于是继续想 C。
又想了好一会，发现自己不会低于 O(n1.5)O(n^{1.5}) 的做法，只会一个 O(nn)O(n\sqrt n) 的 kdt，和 O(nnlog⁡n)O(n\sqrt{n\log n}) 的分块。
我并没有吸取 thupc 的教训，想着 kdt 怎么着都能过个 10510^5 吧，于是开始莽。写了将近两个小时发现比 O(n2)O(n^2) 可以多过 00 分！
感觉不能要了，先回去看 B，发现我其实可以把所有分叉的可能搜出来，状态数不会太多，获得了 t=9t=9 的 7878 分。
为什么我不能做 t=8t=8 呢？我的多叉不像正常人一样是平均分，而是直接把余数丢到了下一层，于是将所有状态搜出来都过不去 t=8t=8。
最后的时间想着写个 C 的分块，看看能不能冲过 10510^5，但写到一半感觉写不完了，转拼菊花的分，但不知道为什么到最后都没调出来。
最后是 100+78+56=234100+78+56=234，出来一问，发现 B 是简单题，也有一些人过 C。感觉寄飞了，要比大众分低个 3030 分。
福建 E 队一个 264264，一个 252252，而我们 A 队无人通过 B 题，感觉团体总分又烂掉了！
下午讲评，深刻地意识到了自己场上有多蠢。
小道消息说队线含 DE 是 240240，那我吃个 A 队的 55 分只低了一分，还有救。

2024.7.19

社会活动，三峡博物馆，我不评价。
晚上睡得不好。

2024.7.20（Day2）

进场发现 A 是神秘数论，B 是看起来很可做的 ds 优化 dp，C 没搞懂。
先看了 A 30min30\text{min}，发现自己除了知道可以辗转相除判无解以外一无所获。
我 D2T1 不过我打锤子呢？至少得过一个题吧？
于是先写了个 O(nm)O(nm) 的 5050 分，去看 B。
首先的想法是对 hih_i 按顺序 dp，通过启发式分裂来维护一些东西，然后用 ds 维护树形结构的一些和。
先写除了启发式分裂，剩下都用 ds 维护的版本，写了好久都过不去样例，在 2.5h2.5h 的时候，我忽然意识到，我的转移系数假完了！顿时冷汗直流。
先改了改暴力 dp，在 3h3h 多一点的时候终于拿到了 O(n2)O(n^2) 的 2525 分。
此时我有两种选择：
  1. 放弃这题的正解，选择拼看起来不少的部分分，但不一定够时间写其他两题的分了。
  2. 继续冲正解，但冲不出来的话分数就会烂掉。
上了个厕所冷静思考了一下，如果选择第一种，那么我必然达不到 Au 线，而我此时应该已经上了 Ag 线，低位 Ag 和高位 Ag 没有区别！
于是我毅然地采取了第二种决策。
首先仍是对 hih_i 按顺序 dp，有两种贡献方式，每个点有一些存活时间，在存在的时刻，他们的贡献是对到根路径的一个前缀。
先把转移方式改成上述的，并用倍增+树剖加速维护，调过样例的时间大约是 4h4h。
还剩最后一个算系数的部分，似乎还要用一个类启发式分裂的状物来做。我没写过启发式分裂，这个也不很板子，没把握在极短的时间内写对。
只剩 1h1h 了，我还只有 7575 分，有点红温，要倒闭了。
但很快，我就意识到系数可以在一开始预处理，这样可以倒过来维护，用并查集+线段树合并就可以做了。
开写！一遍就过了所有样例，在 4h10min4h10\text{min} 的时候终于在这题拿到了 100100 分。
回去看 A，观察到答案很小，于是直接记忆化搜索一下拿到了 7070 分。
进而我发现由于辗转相除过程的唯一性，所遍历到的状态必然不重不漏，不用记忆化就可以直接搜到 8585 分。
在 4.5h4.5h 开 C，发现暴力、性质 A、性质 B 的 O(n2)O(n^2) 都是简单的，飞速地拿了 2525 分。写完后还剩 5min5\text{min}，也写不了其他分了。
5+100+100+78+56+85+100+25=5495+100+100+78+56+85+100+25=549。
出来问了一圈大家的成绩，固然比这个成绩高的很多，但我知道自己真的翻盘了。
预估的金牌线一路走高，从一开始的 529529，到了 534、536534、536，最终定格在了 538538。现在的选手真是卷得离谱，也许未来有一天，金牌线会达到 600600 甚至更高，但我是看不到那个时候了。
福建今年进了四个集训队，分别是我,ljr,hjx 和 wzh。其实早该有四个了，但是前几年的选手总是在 noi 莫名的失常。

2024.7.21

闭幕式。
最后是并列 rk37\text{rk}37，苟到了金牌的第二批。福建时隔 44 年重回团体前八，热烈祝贺！！！
福建的四个集训队全在后 2020，不是很牛。不过也没关系，毕竟 noi 成绩也不带入之后的比赛是不是？
站在台上，看着胸口挂着的沉甸甸的金牌，我却没有产生什么高兴的情绪。也许是因为发挥与成绩不尽如人意？又或者是我认为自己一定可以拿到这块金牌？
接下来我需要考虑下自己的下一个目标是什么。是进入候选队？还是 cf 上 LGM？但无论如何，至少我有资格去思考自己未来该干什么了。

评论

共 25 条评论，欢迎与作者交流。

正在加载评论...