BJOI2025 游记

· · 生活·游记

Day -\infin

选手 NOIP 只有 240 分。

Day 1

选手开始考试。

选手思考 T1。

选手发现如果想让 x 成为中位数，那么值域区间包含 x 的都应选 x 并放上限个。

选手发现可以进一步地对每个 x 求出必定小于其和大于其的数的个数的取值范围，然后让这两部分的个数尽量接近。

选手发现线段树可能跑不过去。

选手发现可以离散化后差分。

选手狂写 T1。

选手 T1 写挂。

选手发现自己未能正确使用 lower_bound。

选手通过 T1 大样例。

选手思考 T2。

选手认为为了回答询问，必须遍历 x 可达的所有点。

选手放弃 T2。

选手思考 T3。

选手头昏脑胀。

选手放弃 T3。

选手思考 T2。

选手终于意识到如果只有询问且忽略 a 的限制的话，其实只要在 DAG 上递推一遍就能求每个点的答案。

选手幡然醒悟但仅获得 0 分。

选手发现如果对 a 值域分块并预处理 DAG 可达性以快速查询散点答案，就能处理 a 的限制。

选手获得 4 分。

选手发现自己完全不会带修。

选手追忆起自己做过的 P5443。

选手想到对询问分块并每块暴力重构。

选手平衡时间复杂度。

选手得到了一个优美的 O(\dfrac{n^2}{\omega} + n^{\frac{5}{3}}) 做法！

选手前往洗手间冷静片刻。

选手狂写 T2。

选手通过样例 1。

选手通过样例 2。

选手高歌猛进。

选手样例 7 超时了亿点。

选手气炸。

选手写了 T3 的 8 分暴力。

选手开始对 T2 卡常。

选手的样例 7 快了 0.2 秒。

选手再度气炸。

选手卡常无果。

选手躺平摆烂。

选手估分 100 + x + 8 = x + 108。

选手遗憾离场。

Day 2

选手开始考试。

选手思考 T1。

选手发现按 t 排序后直接模拟即可。

选手发现需要使用线段树优化该过程。

选手欲在值域上开线段树，发现动态开点线段树开不下。

选手发现不用动态开点，只需要开每个箱子占一个下标的线段树即可。

选手狂写 T1。

选手通过样例 1。

选手通过样例 2。

选手高歌猛进。

选手样例 4 挂了。

选手狂调 T1。

选手发现如果在考虑某个箱子时其已经到达了目标位置，则自己的程序将出错。

选手写了特判。

选手通过 T1 大样例。

选手思考 T2。

选手会特殊性质 A。

选手会特殊性质 B。

选手不会特殊性质 C。

选手写特殊性质 A，耗时远超预期。

选手写特殊性质 B，耗时略超预期。

选手思考 T3。

选手认为暴搜是基本跑满 10^{10} 的。

选手躺平摆烂。

选手估分 100 + 24 + 0 = 124。

选手遗憾离场。

Day 2^+

选手想进 D 队……

Day 3

选手恶补文化课。

选手默写自己的 D1T2 代码，发现样例 7 在本地只跑了 5.5 秒，且本地的配置略逊于 CCF 评测机。

选手意识到或许是自己调编译选项的时候手滑了，导致没有开 -O2。

选手也许真的能进 D 队。