本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-01-08 16:53:09

这场 vp 起飞了，Div.1,Div.2 选手都算，在现场也是二十几名的位置。

A

模拟就行。

B

$dp_i,j$ 以第 $i$ 个结尾，模 $4$ 等于 $j$ 的子串总数。

C

每次贪心的尽可能选距离远的，只要不超过 $k$。

D

差分一下，设 $f(i)$ 表示 $[0,i]$ 有多少个能被 $m$ 整除的魔法数字。

那么答案就是 $f(b)-f(a-1)$。

设 $f_{i,j,0/1}$ 代表仅考虑前 $i$ 位，当前数字取模 $m$ 的结果是 $j$，并且当前数字是否已经确定小于限制。

转移是显然的。

E

可以枚举 z 字形的左下角，假设是 $(x,y)$。

首先，预处理出 $(x,y)$ 右边最多延申多长，记为 $d$。

显然，向上延申的长度不能超过 $d$。

假设向上延申 $k$ 的长度，即 z 字形右上角为 $(x-k,y+k)$，那么有两个必须满足的条件：

1. $(x-k,y+k)$ 必须向左能延申至少 $k$ 的长度。
2. $(x,y)$ 到 $(x-k,y+k)$ 的对角线上必须全部是 z。

值得一提的是，我 vp 的时候因为没注意条件 2 吃了 4 发罚时。

现在，升序枚举 $(x,y)$，考虑枚举的时候需要怎样操作。

枚举之前先 $O(nm)$ 预处理每个点向右，向左最长连续多少个 z，设 $p_i$ 代表 $i$ 点开始向左最多连续 $p_i$ 个 z，$q_i$ 代表 $i$ 点开始向右最多连续 $q_i$ 个 z。

对于每个 $(x,y)$，我们主要关心的是其所在的正对角线上有多少个点能作为 z 字形的右上角。

一个点 $i$ 想要满足条件，那么要求是这个点与 $(x,y)$ 的行的差 $d_i$ 需要小于等于 $p_i$。

考虑对于每个正对角线，都维护一个这样的集合，记录这条线上每个点的 $d_i-p_i$，只有这个集合内部的点才是有可能符合要求的。

随着 $(x,y)$ 升序枚举，$d_i-p_i$ 单调不增，所以每次枚举 $(x,y)$ 都会导致其所在对角线上的一些点被删除。

但是，对于单个 $(x,y)$ 还有个额外限制，就是符合要求的点与 $(x,y)$ 的行差 $d_i$ 必须小于等于 $(x,y)$ 向右的最长连续 z 长度 $q_{x,y}$，这个使用树状数组就可以维护，每次更新集合，也需要更新树状数组。

F

这题最难的点在于想到网络流。

Limak 给的关于值域的前缀元素个数，本质上给出了每个值域区间的元素个数。

而每个值域区间，能给模 $5$ 同余 $0,1,2,3,4$ 的数字数量贡献多少也是可以计算出来。

最后，它也给出了模 $5$ 同余 $0,1,2,3,4$ 的数字数量应该是多少个。

现在建模已经很显然了。

复杂度证明