NOIP 2025游记

NOIP 2025 游记

Day -inf

Day -2

Day -1

Day 1

开考

• 8:33 分准时开考。
• 解压缩，唉怎么没有类似 CSP 的四字词语？
• 8:35 看 T1。
• 当时就觉得 $x_i + y_i$ 最小的那个会被一直选，当时只觉得会选到不能再选，然后尝试开写？
• 8:40 写完，当然没过样例。
• 然后看了看特殊性质，好像没啥启发。
• 大概 9:00 看了看后面的，发现全是不可做题（但是真没想到会是那么难）。
• 写了个暴力，发现也不好写，但是还写挂了几次。
• 9:30 左右上了个厕所。
• 写暴力，随便造了点数据，输出最优方案之后发现没啥规律！
• 大概 10:00 发现好像自己又干了个逆天的事，因为我的爆搜每次只记录最后一次的答案，可能会有覆盖。
• 随手排了个序，发现和之前的猜测一样：只有 $x_i + y_i$ 最小值一直选，剩下的都是只选 $x_j$。
• 然后那为啥我之前的不对？
• 我把一个 $n = 100$ 的数据跑了个 $O(2^n \times V)$ 的暴力。
• 等待了 $7$ 秒，发现跑出来了！
• 我仔细一看，哦，原来不一定每次都要选！
• 那我枚举一下选的次数，然后按照 $x$ 排序，计算剩下的钱能买几个，这样二分一下不就行了！
• 唉，这好像是 $O(V \log n)$ 级别的，好像 $m = 10^{18}$ 过不了。
• 没关系，先写了再说。
• 大概在 11:00 左右写了出来。一测样例，全过！
• 考虑优化。我们发现，瓶颈在于枚举，如果我们假定前缀和然后反推次数再计算不就行了！那我岂不是会了。
• 开写，11:15 写完。因为害怕还用了 i128。
• 测样例，全过！大概没啥问题，开 T2。
• 花了 $20$ 分钟理解题意。
• 然后写了一个暴力里面还套了个暴力的暴力，然后想了想性质 A，感觉答案就是 $2^n$。
• 此时大概 12:00。上厕所。
• 开 T3、T4。
• T4 看着像是一个传统一点的，感觉在 ZR 见过类似的。推了半天，发现还是只会 $O(n ^ 3)$，懒得写，干了点迷惑行为，要是能上迷惑行为大赏就行。
• 回去看 T3，这是啥？
• 想了想，感觉每个数字的 $a_u$ 不会超过 $m + 1$，再大没意义，然后写了个暴力套树的遍历，大概能过前两个点？
• 然后就开摆了。
• 估分 $100 + 20 + 4 + 0 = 124$。

收卷

回家

总结