2026-10-20(#17)：乘三加一

Sean Ven —— 181 Seconds

我有不能输的理由。

补一下 CCPC 2026 长春，主要是不是我做的题和比较难的题。

A. 又一道纸笔问题

类似于网络流，将这一个点的流量直接转移到下一列上。

沃日这是啥。官方解法有点巧。就是通过连续段的长度来判断这是什么字符。

喜欢题目名称。

赛时没想到这个能做，但是我想了一会儿就会了，虽然不是我写的。赛后我觉得我写得很漂亮。

这种不好统计的形式一般是要枚举 LCA 的，设 $k_i$ 为某个模块选择的课程个数，那么贡献拆为：

$\sum_{i=1}^K (q_i-q_{fa_i})\binom {k_i} 2$

有效时间段数为 $10^4$ ，考虑网络流。不难想象 $K$ 的流量从根节点流入，但是这样发现每条边的费用是会随着流量的改变而改变的。

枚举中间两段的起点，大概要做一堆前缀和。不难。应该有更简单的做法。代码。

仍想起去年场上我是模拟 + 做 $k$ 轮字符串哈希加二分。多 $\log$ ，倒闭了。

就是说我们怎么检查两个字符串只相差 $k$ 个字符。全放在一起求两个后缀的 LCP，然后就可以找到失配的位置。

压成 ulong，这样后缀数组的大小只有 $\dfrac{n\times m} {64}$ ， $10^6$ 多一点。后面的时间复杂度是 $O(n^2 k)$ 。代码。

发现实际上只和水桶容量集合和漏水集合有关，合并的条件是 $a-bt<0$ 。代码。