NOIp 2025 游记

zhoumurui · 2025-11-29 20:31:41 · 生活·游记

是不是该写游记了。

DAY 2 动笔。

奇迹的现人神保佑我考好点吧。

序

为什么大家的游记都写得那么出彩。破防了。

DAY -1

今年 JX NOIp 考场在南昌二中，不用坐火车了。

打板子。

DAY 0

最后一场模拟赛。

题目出得很信心，T1T2 都不难。

T3 是个“有多少种方案能使某种贪心正确”的计数，花了 3h 冲出了 T3 的 80pts。

回家，不打板子了，钢四启动！

诶防线漏风被跑马了。破防睡觉。

DAY 1

提早打车到考场。

先打缺省源，然后复制成 4 份。

下到 PDF，先把题目读一遍。

T1 简单题。

T2 看了一眼怎么是计数。不过应该还是可做的。

稍微想了一下没出结果，先看一眼 T3T4。

T3 特别奇怪，鉴定为 Ad-Hoc。既然放 T3 了那应该不是什么神秘贪心题。盯了个填的数必然小于 n 的结论，会了 8 分。然后会了 m=1，感觉 m=2 应该可做，看 T4。

袜 T4 是数据结构。一看区间询问不带修，马上口胡了 O(nq \sqrt n) 的回滚莫队，但是并没有多少分。

上个厕所。想了个基于 O(n^2) 预处理的做法，感觉可以拿 20 分。性质 A 和性质 B 感觉可以用类似的写法完成，这样是不是就 45 分了。

先去把 T1 写了。这个时候大概是 10 点钟。

然后定下了 T2->T4->T3 的策略，开始全力冲 T2。

手模了一下样例，感觉贪心不对的方案数比贪心对的方案数好统计啊。

随口蒙了个结论，贪心不对的时候，一定是还剩两费的时候买了一费的糖。感觉这个东西很对啊，试了一下找不到什么反例，就接着往下推了。

然后来考虑这个东西怎么计数能做到多项式。又去上了个厕所想到枚举那个本来应该买的两费糖和错买的一费糖。然后推了推有了一个 O(n^3) 的组合数式子，有 52 分。这个时候大概 11 点。

然后当然考虑优化了，两个方向，一个是优化组合数式子，一个是优化一下枚举策略。后者感觉走不通，考虑前者，捣鼓了一下式子发现形如一个 \sum C_x^iC_y^i 的式子。

恰好我上周 ABC 被范德蒙德卷积创了去看了一眼，感觉很像啊。检查一下枚举上限是不是等于 \min(x,y)，发现是的。于是变成了 O(n^2 \log n)，会了 92。

不知道剩下 8 分 n \le 5000,N \le 50000 是什么鬼，感觉 O(n^2) 不是很能过。但是重新想了一下，n^2 是不是 \le 3\times 10^7，这样感觉就很能过了啊。

想了一下可以把那只 \log 用双指针优化掉，然后果断写代码，调一调过的时候 11 点半。

回到 T4，思考了一下特殊性质 D，发现不会。于是开码。

码着码着发现做法的复杂度并不是几个小时前我想当然的 O(n^2 + nq)。实际上每个区间长度贡献给每个询问是 O(n) 的，复杂度飙升至 O(n^2 q)。

临时上了个分块变成 O(n^2 + n\sqrt nq)，感觉 45 分应该能保住吧。

写挂了。调。

往死里调最后 12:20 调过了。大样例一秒多。不管了赶紧把 T3 暴力打出来才是正经。

推了一下 m=2 猜了个结论，写了一手过了对应的大样例。

拼一个 O(n^{n+2}) 爆搜。懒得想了所以没写 O(n^{n+1})。应该不至于被卡常。小样例半秒，t = 5，应该不会被卡常。吧。应该吧。

还剩十五分钟赶紧检查一下四个题。

卧槽我 T1 缺了个特判赶紧补一下。

呼，差点就输掉了。