于 2025.12.13 回归 whk 2 周。

noip 2025 挥之不去，在 whk 的教室里，还在屡次讨论着。

“要是我不会正解就好了”，“要是我没挂分就好了”，“要是我多测清空就好了”。

但是这都过去了。

在我的脑海中初步给 oier 在水平上定了 $4$ 类。

1. 任何实力没有，去 noip 纯属是玩的，奔着省三省二去的。不在我们的讨论范围内。

2. 有点实力，想拿到一等安稳退役的。

3. 有实力，但是不够，进不去省队。奔着 D 去的。

4. 很有实力，不在我们的讨论范围之内。

我的亲身经历是：noip 2025 T2 想到了初步解法，然后需要往后走下去，但是走一半走不动了。我很想证明自己，我觉得我能把 T2 做出来，然后后面题写了好写的暴力后就来写 T2 的 $O(n^3)$，然后这个都没调出来。

我自认为我是处在 2，3 之间的。所以我就想去打出成绩来。

但是我要给 2，3 一些建议：

• 对于 2：不要以为一等很好拿，只有你亲身经历过才知道。所以要怀着敬畏之心，不要掉以轻心，认认真真训练。考场上最好切掉 1 个题，后面题只要不是想的非常明白 & 代码你有绝对信心 1h 内能解决的你才去冲，否则一律暴力 + 部分分。

• 对于 3：好好想一想自己到底有没有这个实力，如果你发挥成屎了也能拿一等，那你可以去冲。否则一律回归到 2。不要幻想自己发挥好点。

我觉得这一年很戏剧性。我不知道别人到底是真强还是假强。

CSP-S 2025 和 noip 2025 都跟我开了玩笑。

无论是 S 的后三题数组全开小，以及 noip 2025 T3 的多测不清空。我之前从来没有犯过这种错误。

我是怎么犯错的呢？

S T2：大样例卡满了，但是他不报 RE。因为就多了一个，我数组是 1e4 + 5 然后 1 index，数据刚好也是 1e4 + 5，不 RE。

S T3：考试结束前想着多与处理一些 base 数组然后多水点分，导致直接 RE。最终测 CE 不 CE 的时候都给我警报了，我却以为没事。

S T4：大样例没有卡满的。

noip T3：大样例和小样例一样，然后小样例虽然多测，但是他第一组样例的图是第二组样例的一个子图，也就是第二组样例是在第一组样例的图的基础上延续的。所以没出现问题。

很戏剧性。

“还有人考场上会出现这样的低级问题？”当年说去的话，如今正中我的眉心。

真的，人教人永远不会，事教人一次就会。

真心忠告。

想了想，这些还是放在最后吧：

我还是想喷 noip 2025。经常有人说：打炸了就是菜。没拿到一等就是菜。

我是很讨厌的。因为这些都没发生在他们身上。

他们没资格去评判。

这套题 T1 过于简单，而且数据很水，大部分都能拿到 95+ 的分数。

T2 想到初步思路很简单，往下走下去以及写出来是很难的。那么对于我们这些接近 3 的来说，肯定是会去冲的。

然后那些 1，2 直接就不会，或者想到了初步思路后面直接走不动，那他们就直接打暴力 + 特殊性质了。

然后后面题的暴力都挺难打。

说的难听点：这次 noip 是那些低水平选手唯一能打过高水平选手的机会了。

反正还是任重而道远，认清自己。

link。

前言

首先就是这题 std 假了。

不能枚举其中一个走了几步然后把有对应的点全删掉。这样好多有解都被判掉了。

Solution

考虑你可以把 $b_i$ 对 $a_1$ 做差，然后 $O(n)$ 枚举一个走了几步。

此时你要 $O(n^2)$ 枚举所有差，然后作为第二个走了几步。

同时原先的 checker 是假的。这里你可以把他看作二分图，然后看是否完美匹配。

不上科技的话，用朴素增广路可以做到 $O(n^5)$。

上网络流的话可以做到 $O(n^4)$。

T1

简单题，先排序，然后扫一遍二分求贡献，然后前缀后缀取个 $\max$ 枚举中间点就好。100 分

T2

首先转化题意：$d + kx = s$。

其中 $d$ 为横向移动距离，$k$ 为上下移动距离。

然后题意说要让 $x$ 最小，于是一开始写了个按 $k$ 为第一关键字的最短路。

但是我的答案小了，又注意到是最短路，于是写了个按 $d$ 为第一关键字的最短路，然后大小样例都过了。

但是我当时就非常疑惑，就感觉不大对劲。（事实证明我的感觉是对的，的确假了）。

只得了 51 分。正解是直接二分答案，然后跑最短路。可能是我对题意理解错了吧。

T3

首先考虑 $x$ 的取值是 $[1, n]$ 的，然后就可以枚举 $x$，然后如果有 $m$ 的话，可以枚举长为 $m$ 的这个串的开头，然后算贡献。

一开始卡在如何快速算贡献上了，但是很快想到多重集排列，于是 $n^3$ 就拿到了。

接着考虑实际上它每次是跳 $x$ 的，这个复杂度总共是 $O(n \ln n)$ 的，于是套上 hash 就有了一个 $O(n^2 \ln n)$ 的做法。有 50 分。

但是我写出来答案大了，我就猜是算重了，然后又注意到对于同一个 $x$ 如果删完之后两个字符串一样，那他们的贡献只能被算一遍。

好吧，啥都想到了但就是写挂了。

正解就差一步，还是读题问题。

题面中说了，所有长为 $x$ 的子串得连续，所以就不存在 $m$ 把一个 $x$ 分搁开的情况。

所以枚举 $m$ 的位置也是 $\frac{n}{x}$ 的。调和级数，然后就对了。

T4

首先 $n^2$ 好做，直接 $n$ 遍 dfs 即可。

接着考虑了特殊性质 $B$，一个菊花。

首先根可以找其他 $n - 1$ 个点。

其次考虑枚举非根，那么根据这个点和根的大小关系，可以得知这个点作为 $\min$ 还是 $\max$。

然后贡献就好算了：

• 作为 $\min$，此时 $rt > i$，那么另一个 $\max > rt$，所以贡献为：$n - rt$。

• 作为 $\max$，此时 $rt < i$，那么另一个 $\min < rt$，所以贡献为：$rt - 1$。

然后写代码的时候我是都算了两遍，最后除 $2$ 即可。35 分。

正解是考虑在最小、最大生成树的 Kruskal 重构树上做。

这个还没学，等学会了在补。

总结

最终 100 + 100 + 50 + 35 $\to$ 100 + 51 + 0 + 35。

我有理由怀疑 mx 为了增加题目难度 / 防止被盒到原题而改的抽象题面。

但确实自己水平还是不够，读题不够仔细。

所以还是练练读题，以及在烦躁的时候静下心来读题。

然后再拓展学学一些进阶算法。

没报上名 /yun。

1

先看的括号树。一开始直接把 ( 看作 $1$，) 看作 $-1$，然后求 $1$ 到 $i$ 的路径上区间和为 $0$ 的区间个数。

但是发现这是不对的，因为还要保证任意时刻前缀和 $\ge$ 起点的前缀和。

所以重新考虑。这里就不太好。

然后对于链可以进行括号匹配来统计，直接求出 $f_i$ 表示以 $i$ 为结尾的数量，然后做前缀和即可求出。

然后考虑转移到树上，其实还是可以看作一条链，只不过把别的链上的贡献去除掉即可。

2

然后开的纪念品。一开始考虑了一个暴力，但是发现读错题了，有多种物品，所以重新考虑。

手玩样例然后注意到了持续持有一个物品多天等价于我在下一天卖了然后再买入。

所以直接 dp 就行。

3

然后看的加工零件。因为是和相邻的有关，所以答案和奇偶性有关。

然后发现我要提供原材料首先我的距离必须 $\leq L$。其次就是这个点到询问点的距离的奇偶性必须和 $L$ 相同，所以跑一遍 bfs 预处理 $1$ 到其他所有点奇数长度的最短路，偶数长度的最短路然后判断即可。

4

开的 E 家的饭。首先形式化题意：有 $n \times m$ 的网格，每行至多选 $1$ 个，每列至多选 $\lfloor \frac{m}{2} \rfloor$ 个，然后不能不选，求方案数。

由于至多选的个数为 $\lfloor \frac{m}{2} \rfloor$，所以只能有一种物品不合法。那就考虑容斥。

直接考虑了一个暴力 dp，设 $f_{i,j,k}$ 表示前 $i$ 种方式，一共选了 $j$ 个，不合法的物品选了 $k$ 个的方案。

转移 $O(n^3)$ 的，做 $m$ 次，有 $84$ pts。

赛后看的题解，就是注意到我们只关心 $j,k$ 的相对大小，所以直接把 $j,k$ 放到一维里，维护差值 dp。时间复杂度 $O(n^2m)$