NOIP2025 游记

· · 生活·游记

Day0：

早上在学校上课，晚上在家里复习了一下 Tarjan 和 fhq，有点紧张，但是 12 点应该就睡着了。

Day1：

7:20 起床，洗漱、吃完早餐后 8:00，去到长郡考试。

到里面跟着人群走，然后就走到错了走到了教学楼（（（，差一点就迟到了。

到了考场，打了打头文件就开始了。

先开 T1，感觉 T1 是一个和 S 组 T1 差不多的题目，发现选择超过 2 个数的的物品肯定只有一个，而且是 x_i+y_i 最小的，将 x_i 排序就行了，15min 写完。

看了 T2T3T4，T2 是计数，T4 是数据结构，T3 不知道是什么，于是开 T2。先写了一个暴力好查错，接着一直在想性质 B，中途一直以为自己会了，但是写完后又错了，思路极其不清晰，写着写着 1h30min 过去了，但是仍然没写出来。

有点慌了，开始想 T4，测试点 1\sim 3 就是纯暴力，考虑枚举区间长度 len，然后用单调队列求出每个 i 的答案，用 st 表就可以做到 O(n^2\log n+nq)。再用分块的技巧应该可以把 \log 去掉，这样可以通过测试点 4，稍微改一下代码就可以通过特殊性质 AB。看起来能拿 45pts，但是分块 rmq 没那么好写所以就只拿了 40pts。

此时还剩下 1h50min。

花了 25min 想 + 写 T3 状压，又想了 15min n\le 18,m=2 都不会，只能拿 16pts。

此时还剩下 1h10min。

检查了一下 T1T3T4 的文件，准备冲 T2。重新开始做，从简单的部分分入手：

A 性质，答案显然是 2^n。

$m=2n-1$，非全 $2$ 一定对，全 $2$ 也一定对，答案为 $2^n$。 $m=2n-2$，只有出现恰好一个 $1$ 的情况会有贡献，注意到这个 $1$ 为最小值，所以只有在 $a_1$ 为严格最小值且 $a_1<\frac {a_n}2$ 时才会有贡献，所以答案为 $2^n-1$ 或 $2^n$。 结合暴力一共有 $52pts$，只要能够做出特殊性质 B 就有 $72pts$，还有 20min，冲！ 枚举第一个 $1$ 的位置，再枚举 $1$ 的个数，对答案有贡献的方案，$2$ 的个数有一定范围，加上一个组合数就可以了，写完没过，还剩 10min。 想了想，发现不止对 $2$ 的个数有限制，对第 $t$（考试上设的变量，忘记是什么了）个 $2$ 的位置也有限制，再枚举 $2$ 的位置就行了，但是时间复杂度 $O(n^3)$，写写写，最后 3min 通过了。 检查了一下文件就交了。 预估：$100+64+16+40=220$。 --- 考完后水谷，发现 T1 没有判断没选完 $x$ 的情况，分数变成随机数，又发现 T2 忘记写 A 性质了，分数 -4。 所以预估分数变成了：$[0,100]+60+16+40=[116,216]$。 在 luogu、htoj、云斗上测了一下发现好像 T1 挂分不严重（？ 希望 CCF 数据水一点吧。 --- 哈哈哈，坠机了。 $95+40+16+40=191$。 T2 暴力写挂了，多挂了 15pts。 # 总结： ## 优点： 这次比赛没写出 T2，但是及时止损了，去打了 T3T4 暴力，后面几题的暴力分还是很多的。 做题不能做上头了，要给自己定一个规定，什么时候必须收手做其他题，一是后面题的暴力分可能还有很多，二是休息一下想另一道题后再想可能更有思路。 ## 缺点： 这次比赛 T1 写太快了，没有做细致的检查，应该多花点时间自己造数据 / 对拍的。后面题的分都是一点一点凑出来的，要是这道题挂了很多，那后面的努力基本就白费了，所以还是不要相信大样例，自己造数据。 我最后 5min 还在写 T2 的 B 性质，这是不应该的，这次只是运气好写出来了，要是万一没写出来，而且文件建错了，那就得不偿失了。