NOIp 2025 总结

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

补 $jsy$ 的每日一题……

晚上开始打板子。

上午打板子。

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

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

洗了个澡，然后睡了。

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

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

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

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

好好思考贪心的正确性。

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

$T2$ 。

考虑这个按性价比去购买似乎挺优秀的，不合法的情况应该较少，直接求不合法情况。

考虑一定是先买了一个 $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$ 的重新测试，终于调过了。

此时只 $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)$ ，但是没时间打了。

看来我性质假了。

代码下发了，发现 $T1$ $95$ 分，没过 $WA$ 了，$T2$ $96$ 分，没过 $TLE$ 了，$T3$ $24$ 分。

$T1$ 没 $break$ 。

感觉寄飞了，$T1$ 好像可以卡到 $0$ 分，$T2$ 可能只有 $92$ 分。

出成绩了，$T1$ $100$ ，$T2$ $100$ ，$T3$ $16$ 。

好像 $T4$ $O(q\times n\times len\times\log n)$ 跑的挺快，有 $15$ 分，亏了。

据说去掉 $log$ 并不难，感觉我没有好好思考这题。

看来我们应该要相信 $CCF$ 的数据。