CF628(EDU8) 题解 \/ 关于单位流量网络流时间复杂度的学习笔记

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-08-05 23:37:48

A. Tennis Tournament：

:::::info[题目基本信息] 考察：数学，模拟。
题目简介：
小 K 去参加了一场乒乓球比赛，有 $n$ 名选手，不断进行若干轮比赛，直至还剩 $1$ 人，下面是详细的比赛过程：
::::info[一次比赛的定义] 一次比赛有 $2$ 人，其中比赛结果不可能出现平局，$2$ 人中输的人淘汰。
:::: ::::info[一轮比赛的定义] 设有 $m$ 个人未被淘汰，令 $k$ 为最小的正整数使得 $2^k\le m$，$2^k$ 名选手进行 $2^{k-1}$ 次比赛，剩余选手直接晋级（不参加比赛）。
:::: 已知每位选手每次比赛需要 $b$ 瓶水，每次比赛的裁判需要 $1$ 瓶水，同时每位选手每场比赛需要 $p$ 块毛巾，问总共需要多少瓶水和多少块毛巾。
数据范围：

$1\le n,b,p\le 500$ ::::: :::::info[闲话] 纯纯阅读理解题，一不小心就翻译错了。
::::: 按上述模拟。
时间复杂度为 $\Theta(\log n)$，空间复杂度为 $\Theta(1)$。

B. New Skateboard：

:::::info[题目基本信息] 考察：字符串，数学。
题目简介：小 X 获得了一个只包含数字的字符串 $s$，他想计算其中有多少个非空子串形成的数能被 $4$ 整除，子串允许有前导 $0$。
数据范围：

$1\le |s|\le 3\times 10^5$ ::::: 根据小学知识得：一个数能被 $4$ 整除的充要条件是它的后两位拼成的数能被 $4$ 整除。
那么我们找出所有相邻两位拼成的数能被 $4$ 整除的位置，累加答案即可。设 $\{a_n\}$ 为字符串 $s$ 上每一位上的数字，则答案为： $$(\sum_{i=2}^n10a_{i-1}+a_i\equiv0\pmod 4)+(\sum_{i=1}^n[a_i\equiv0\pmod 4])$$ 时间复杂度为 $\Theta(n)$，空间复杂度为 $\Theta(n)$。
::::warning[坑点] 别忘了子串只有 $1$ 位的情况！
::::

C. Bear and String Distance：

:::::info[题目基本信息] 考察：贪心。
题目简介：
小 G 收到了一个长度为 $n$ 的仅由小写字母组成的字符串 $s$，定义两个字符的 $dist$ 值为两字符 ASCII 码值差，定义两个等长字符串的 $dist$ 值为两字符串每一对对应位置的 $dist$ 值之和，他想求任意一个字符串 $s'$ 满足它和 $s$ 的 $dist$ 值等于一个常数 $k$，若不存在请向他回复 $-1$。
数据范围：

$1\le n\le 10^5$
$0\le k\le 10^6$ ::::: 显然，若要使两字符串间 $dist$ 值最大，则对于字符串的每一位，要么改成 a，要么改成 z，看哪个和它 $dist$ 值最大，若求出来的值还小于 $k$ 则不可行，否则尽量使前面的 $dist$ 更大，构造方案即可。时间复杂度为 $\Theta(n)$，空间复杂度为 $\Theta(n)$。

D. Magic Numbers：

:::::info[题目基本信息] 考察：数位 dp。
题目简介：
小 L 收到了 $4$ 个数 $m,d,l,r$，其中 $l,r$ 位数相同，求满足下列条件的整数 $x$ 的个数对 $10^9+7$ 取模的结果：

$l\le x\le r$
$x$ 从最高位到最低位数的偶数位为 $d$，奇数位不为 $d$。
$m|x$

数据范围：

$1\le m\le 2000$
$0\le d\le 9$
$1\le l\le r\le 10^{2000}$ ::::: 数位 dp。
设 $f_{i,j,0/1,0/1}$ 为前 $i$ 位对 $m$ 取模的结果为 $j$ 且是否全都是前导 $0$ 和是否前面与 $r$ 相等。不断记忆化搜索即可。由于高精减不好 ~~（懒得）~~ 处理，所以最后要对 $l$ 判断是否符合条件。时间复杂度为 $\Theta(|r|m)$（$|r|$ 指 $r$ 的位数），空间复杂度为 $\Theta(|r|m)$。
::::warning[坑点] 一开始做这题因为太久没做数位 dp 导致：

忘记根据是否有前导零（这题不用）和前面几位是否与 $r$ 相同。
将 $l,r$ 拆开（这题也不用）。
将 $l,r$ 拆开后每次都进行清空 $dp$ 数组。
::::

E. Zbazi in Zeydabad：

:::::info[题目基本信息] 考察：树状数组。
题目简介：
小 A 拿到了一个 $n\times m$ 的由 z 和 . 组成的网格图 $s$，令其中为 z 的位置 $(i,j)$ 上 $a_{i,j}=1$，否则 $a_{i,j}=0$。
他想知道满足下列条件的有序正整数四元组 $(lx,ly,rx,ry)$ 的数量：

$1\le lx\le rx\le n,1\le ly\le ry\le m$
$rx-lx=ry-ly$
$\forall i\in[ly,ry]\cap\mathbb Z,a_{lx,i}=a_{rx,i}=1$
$\forall i\in[lx,rx],a_{i,lx+ry-i}=1$ 数据范围：
$1\le n,m\le 3000$ ::::: 想要固定该 Z 字形的一个点位置，但是固定那个呢？
若固定左上点或右下点，则 Z 字形的两条边还会动。
若固定左下点或右上点，则 Z 字形只有一条边会动，显然更优。

故我们固定右上点，想要快速统计贡献，所以我们维护以 $(i,j)$ 点为右端点的极长 z 序列长度 $a_{i,j}$ 以及以 $(i,j)$ 点为右上端点的极长 z 序列长度 $b_{i,j}$，则右下点的横坐标（这里的横坐标与平面直角坐标系的横坐标相反）$rx$ 就必须满足 $i\le rx\le i+\min(a_{i,j},b_{i,j})-1$。
但并非每一个都满足要求，还要满足 $j-a_{rx,j}+1\le j-(rx-i)$。
对上式根据参变分离法移项并合并同类项得 $rx-a_{rx,j}+1\le i$，这时就很显然了，对于每一列建立树状数组维护即可。
时间复杂度为 $\Theta(nm\log n)$，空间复杂度为 $\Theta(nm)$。
:::::warning[坑点] 本题卡空间，需要关闭 long long，仅对最后答案开 long long。
:::::

F. Bear and Fair Set：

:::::info[题目基本信息] 考察：最大流。
题目简介：
小 Z 收到了一些限制条件，他想知道是否存在一个集合 $S$ 满足下面这些条件：

$\forall x\in S,x\in[1,b]\cap\mathbb Z$
$|S|=n$
$\displaystyle\forall i\in\{0,1,2,3,4\},\sum_{x\in S}[x\equiv i\pmod 5]=\frac{n}{5}$
$\displaystyle\forall i\in[1,q],\sum_{x\in S}[x\in[1,u_i]]=t_i$