NOIp 2025 总结

· · 生活·游记

NOIp 2025 总结

Day -2

信心赛，甚至没有紫题，AK 了。

Day -1

补 jsy 的每日一题……

晚上开始打板子。

Day 0

上午打板子。

中午去了郑州，下午看了一下午手机。

晚上和老师、学长一起吃了火锅。

洗了个澡，然后睡了。

Day 1

去考场后，先下载了 lemon ，然后开始打缺省源。

配 lemon 时出现了一点小问题，发现直接解压的 MinGW 好像不太行，于是直接用了 DEV-C++ 的。

先把 lemon 的比赛建好，然后开题。

看 T1 ，贪心，不会又像去年的一样吧？

好好思考贪心的正确性。

发现不难，直接枚举一下计算就是对的，不到半个小时就过了。

考虑这个按性价比去购买似乎挺优秀的，不合法的情况应该较少，直接求不合法情况。 考虑一定是先买了一个 $1$ 元的，然后买了大于等于 $0$ 个 $2$ 元的，之后又遇见了一个 $2$ 元的，但是只有 $1$ 元，之后买了一个 $1$ 元或者后面没有 $1$ 元。 考虑之后遇见的 $2$ 元好像很重要，枚举它。 可以先想暴力，枚举之前那个 $1$ 元和之后那个 $1$ 元。 然后贡献可以用组合数 $O(n)$ 去求，现在有一个 $O(n^4)$ 的做法。 开打。 发现过不了第二个样例，第 $190$ 行（好像是，记不清了）错了。 此时距离比赛开始已经过去了 $1.5h$ 。 慌，先看后面的题。 $T3$ 逆天树高， $T4$ 感觉暴力没什么分。 接着回来调。 找到对应数据是什么，发现少考虑了后面没有 $2$ 的。 只剩下 $T$ 了，稳了！ 开始优化，先发现组合数是范德蒙德卷积，可以优化到 $O(1)$ 。~~其实赛时忘了公式了，又推了一遍。~~ 然后发现枚举后面的 $1$ 元很劣，应该可以直接二分一下，然后可以做到 $O(n^2 \log n) $，感觉过不去，先打。 中间因为边界原因调了好久，疯狂使用 $lemon$ 的重新测试，终于调过了。 ~~感谢 $lemon$ ，不然感觉真寄了。~~ 此时只 $T$ 了最后一个点。 发现由于先排了一下序，后面的限制是单调的，可以直接继承，不用二分，直接双指针。 然后把快速幂预处理一下就过了，此时是 $11:09$ 。 留给我的时间已经不多了。 想 $T3 $。 半个小时后，感觉有点思路，是不是对于一个点来说，他的儿子，要么贡献答案，要么增加这个点的 $mex$ 。 感觉有个 $O(n^3)$ 做法，$48$ 分，必须打。 然后发现过不去第三个点…… 这也没法调啊！ 先想 $T4$ 。 考虑有一个 $O(q\times n\times len\times\log n)$ 的暴力模拟，看一眼得分…… $5$ 分。 还要线段树，这谁打啊！ 还是调 $T3$ 吧。 对着 $DP$ 转移左思右想，发现没什么问题。 不会性质假了吧？ 还有不到一个小时，不能对拍了。 之后的时间不知道在干什么，反正啥也没干。 结束了，估计 $200+$ ，有可能只有 $200$ 分。 问 $Hthntd$ ，发现他 $T2$ 没过，直接退役了。 他说他 $T2$ 想偏了 $1h$ ，然后想到了，但没有调出来，$T3$ 打了个 $O(n^4)$ ，并且说可以优化到 $O(n^3)$ ，但是没时间打了。 看来我性质假了。 ### Day ？ 代码下发了，发现 $T1$ $95$ 分，没过 $WA$ 了，$T2$ $96$ 分，没过 $TLE$ 了，$T3$ $24$ 分。 $T1$ 没 $break$ 。 感觉寄飞了，$T1$ 好像可以卡到 $0$ 分，$T2$ 可能只有 $92$ 分。 ### Day ?? 出成绩了，$T1$ $100$ ，$T2$ $100$ ，$T3$ $16$ 。 好像 $T4$ $O(q\times n\times len\times\log n)$ 跑的挺快，有 $15$ 分，亏了。 据说去掉 $log$ 并不难，感觉我没有好好思考这题。 看来我们应该要相信 $CCF$ 的数据。