NOIP2025 游记

acb437 · 2025-12-06 18:29:35 · 生活·游记

NOIP2025 游记

Day1 11/29

今天从学校出发去考场。

解压密码 !noip@Nov29,2025:dream。T1 结论似乎很简单，所以直接写了。写完之后感觉细节可能还有一些东西需要证明，所以尝试证明 1h 无果，决定先写 T2，后面再调整 T1。此时是 0930。

T2 第一眼没有头绪，感觉 m=2 的性质比较具有启发性，于是花了半小时刻画出了充要条件。写出来之后又花了半小时推广出了普遍情况下的充要条件并写完了 O(n^3) 代码，根据大样例测试结果，预估可以得到 72pts。此时是 1030。考虑到这只是一道 T2，我判断将代码优化到 O(n^2) 需要的只是一些前后缀优化，于是向这一方向考虑，推导出了几个错误的优化方式，然而已经 1200，其它题目的部分分还没有写，于是暂时放弃。

花了半个小时写了 T3 的 O(n^n)，决定剩下的时间 All in T2。把公式列出来，化简一些部分，就是范德蒙德卷积 \sum_{k=0}^{m-j-2}\binom{j}{k}\binom{i-j}{m-j-k-2}=\binom{i}{m-j-2}。但此时我将它记成了另一个组合恒等式 \binom{n}{r}\binom{r}{k}=\binom{n}{k}\binom{n-k}{r-k}。当然，我并不记得这两条等式的具体内容，只记得大概形式。于是我按照组合意义，尝试将原式推导为另一个两个组合数相乘的形式，最后果然错了，我却发现不了组合意义在哪里出了问题。

1257 到了，我只好将之前注释掉的 O(n^3) 代码取消注释，过了一遍编译，连检查一遍大样例运行结果都没有做就离开了考场。

Day2 11/30

早上想看看 T1 贪心策略对不对，代码复现到一半发现自己在排序前记了一个下标，然后在排序后直接用了。但毕竟过了大样例，当时感觉不会挂很多。

Day 5 12/3

中午物理课刚一下课，就听说出成绩了，赶紧去机房查。T1 挂了 55pts，最后成绩是 45+72+8+0=125pts。

结语

比赛策略的问题是比较明显的。但我觉得最可惜的两点是 T1 犯的错误和 T2 没能推出来。尤其是 T2 的范德蒙德卷积是比较明显的，如果一开始就从推式子角度考虑，几乎可以肯定会扭转整个局面。但我对这条恒等式并不熟悉，加上对 T2 难度的误判，让我没有这么做。

赞美万机之神/破碎之神/Omnissiah/Mekhane/WAN。

记于 2025/12/6。