noip2025 游记

· · 生活·游记

前一天 2h 一路坐大巴癫到杭州，晚上一直玩到 12:30。

第二天 8:10 进考场，看了 20min 的选手需知。

先开 T1，感觉是个贪心，10min 胡了个只有一种糖果会拿很多个的结论，那剩下的糖果呢？
按 x 排序然后两两拼起来去替换一个 x+y，样例 6 没过，特判了剩余的钱加最后一个 x 能换成 x + y 的情况，然后就 40min 稀里糊涂的过了大样例。

先看后面 3 题，感觉 T3，T4 不是很可做，先冲 T2 吧。

用 30min 想明白了 m=2 的做法，就是一个原最优代价是 2 的被两个 1 卡住了，又花了 30min 感觉会了。先枚举被卡住的 2 的编号，然后二分出那些点可能有影响，复杂度 O(n\log n)？我爆标了？等等，样例 2 怎么没过，把那几个没过的点拉出来，又调了 1h，发现可能两个 1 刚好凑成了 2 的那个点。只能再枚举其中一个 1，这样就要 O(n^2 \log n) 了，算了，先写再说。

一路调到 12:00，感觉要趋势了，打算赶紧把 T3 暴力写了，在 T3 读错了 2 次题目后写了 8 分暴力，又回来调 T2。把组合数调了又调，在 12:40 终于过了大样例。我复杂度不对，赶紧做常数优化，忽然发现可以双指针维护，变成 O(n^2)。此时还剩十几分钟，先用 3,4min 写了 T4 O(qn^3) 暴力，发现可以 st 表优化到 O(qn^2)，最后 15pts。

赛后出来碰到了 j23wuyifan，跟我说他差点过 T2，最终复杂度 O(n^2\log n)。交流做法后，发现我 T1 会被 x 很小，y 很大的数据卡死，而且以为人均 200+，直接炸了。后面才知道这次堪比 noi。

估分 ?+100+8+15，有点可惜。
赛后把 T2 题解写了，复刻了 T1 代码，怎么直接过洛谷数据了，也太水了吧。

初二，坐标 zj，出分了，100+100+8+0，至少 T2 过了，T1 也水过去了，挺开心的。