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 也水过去了，挺开心的。