NOIP2025游记

· · 生活·游记

求你别炸分。

day -x

csp-s炸光了，凭借着T3 50 分擦着一等线过。不过终于可以初中生体验NOIP了。

day 0

从家开车一个半小时到大学城，路上听了一会丝之歌bgm，全是神曲啊。到了大学城城中村睡，晚上听着猫叫入眠。

day 0.5

先讲点趣事。晚上3点半醒来，4点又睡回去，然后做了一个一辈子的梦。梦见时间穿越回2023年，梦中感觉自己在做梦，于是掐了一下自己，结果发现是疼的，吓傻了。在那里想我又可以圆梦初二NOIP一等了，突然感觉到好像是2025年了，然后醒来了。

day 1

早上随便吃了一些，提前到了考场。发现水和巧克力都不让带？？？GD你也是够厉害的，幸好我提前想到在准考证上面写游记。

开考，速度打上define，打开T1。一眼发现T1是贪心，切了。结果WA了几个大样例，思考一下发现可以小小的反悔，同时考虑到一个民间数据和大样例都没有的优化，也打上了。T1过掉，耗时半小时，感觉有点不妙。

看T2。考虑正难则反，10 分钟后推出按性价比排序后假如某一段价钱是 12...21 这样子的，取了两个 1 可能不如取 2 ，此时不优。看到这里意识到T2不可做，去往后看。

发现离线+单调栈可以在T4拿 45 分，打打打，结果卡在输出上。__int128打过去，大样例都过。耗时 50 分钟左右，感觉赚了。

转头再磕T2，去考虑骗分，一个暴力可以得 20 分，发现 m=n-1 和 A 性质答案都是 2^n，加 8 分。看 m=n-2，发现当 n=1 特判输出 2，其他时候只有开始是 2222...12 时候不优，暴力哪个取 1 就可以了，加 4 分。推了一会 B 性质，无果。转移到 m=2 发现只有 122...2 或 122...1...2... 不优，n^2 枚举前两个 1 的位置，加 20 分。

测完T2我打了的大样例，看T3。下意识地感觉类似于重链剖分这样子贪心很优，每次从一个点向上跑看哪个重链最长，为其贡献。打完后，过了第1，2，4个大样例。意识到按最深的点找重儿子更优，于是按子树最深的点做第一关键字，子树大小做第二个关键字找重儿子。还是只过第1，2，4个大样例，但是第3个大样例多过一个，就这样子了。后面测了一些计算出来可能更靠谱的贪心法，但都没有更优。感觉 t \le 5 有点希望。

估分：100+52+?+45

希望别炸，200+有望了。

12/03 upd

出分了，没炸，100+52+36+45=233，可以为我多年奔波画上句号了吗？