NOIP 2025游记
NOIP 2025 游记
Day -inf
在 CSP-S 中获得了
Day -2
很不幸，感染了支原体+乙流，发烧高达
Day -1
吃了点药，大概好了，但是很不幸当天没赶上和一中一起去秦皇岛，只能第二天早上去。
Day 1
早上五点半起床，已经不发烧了，但是还是有点虚弱，头有点晕。\ 吃了点面包就和爸妈上车去了秦皇岛。
半路上还在高速上看了日出，高速日出还是很美的！
一路开到了燕山大学。在门口见到了这两位 @idle_onlooker 和 @pszyh。
进了考场，考场怎么在三层？
然后在门口排队，等待安检。进去发现自己坐在最边上，挺开心，因为坐在边上一般发挥好。
开考
- 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 。
收卷
第一个收的就是我的，开心！出来看见了教练，简单交流了一下，然后和妈妈去食堂吃饭。
回家
燕大的面好吃！ 回家路上听说两位高二学长@idle_onlooker 和 @pszyh要 AFO 了，也挺感慨的，他们是我送走的第二批 AFO 的学长，祝他们大学还能来 ACM。
总结
今年 NOIP 是我第一次以正式的非正式选手（初中生）参加的。希望以后还能来。