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

zrl123456 · 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}^n[10a_{i-1}+a_i\equiv0\pmod 4](i-1))+(\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
• 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 导致：

  1. 忘记根据是否有前导零（这题不用）和前面几位是否与 r 相同。
  2. 将 l,r 拆开（这题也不用）。
  3. 将 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

数据范围：

• 5\le n\le b\le 10^4,5|n
• 1\le q\le 10^4
• \forall i\in[1,q]\cap\mathbb Z,1\le u_i\le b,0\le t_i\le n

  ::::: 考虑如何建图。
  首先我们令 u_0=t_0=0 且 u_{q+1}=b,t_{q+1}=n，同时令 q\leftarrow q+1，对序列 \{u_q\} 和 \{t_q\} 进行差分，同时判掉一部分不合法。
  我们此时从源点向第 i 个约束条件连 t_i 流量，同时从约束条件分别向 5 个虚点连对 5 取模余一定值的数量，最后将这 5 个虚点分别向汇点连 \displaystyle\frac{n}{5} 的流量，跑最大流即可。 :::::warning[坑点] 由于 C++ 的除法向 0 取整，所以除之前要先加 5。
  ::::: 时间复杂度为 \Theta(n\sqrt n)，空间复杂度为 \Theta(q)。 :::::success[对时间复杂度的一点说明] oi-wiki 下对于单位流情况下的复杂度的解释
  考虑将大于 1 的边权拆成多个 1 的边权，就会发现只有 \Theta(n) 条边，故总时间复杂度为 \Theta(n\sqrt n)。
  :::::