2023杭电多校 赛题总结

前言

这篇笔记记录我在 2023 年“钉耙编程”中国大学生算法设计超级联赛（杭电多校）的 10 场比赛中遇到并认为值得记录的赛题题解以及我的思考和收获。

总览

• 【02-12】Coin
• 【03-02】King’s Ruins
• 【04-11】Circuit
• 【04-12】a-b Problem
• 【06-02】Pair Sum and Perfect Square
• 【08-06】Nested String
• 【08-09】Diagonal Fancy
• 【08-10】Rikka with Square Numbers
• 【09-02】Shortest path

笔记

【02-12】Coin

题意

有 $n(n\le3000)$ 个人在一起玩游戏。初始时每人拥有 $1$ 枚硬币，接着游戏进行 $m(m\le 3000)$ 回合。每回合会有两个人 A 和 B 被选中，他们可以有三种选择：

1. A 给 B 一枚硬币
2. B 给 A 一枚硬币
3. 什么也不做

游戏过程中，限定第 $i$ 个人最多拥有 $a_i$ 枚硬币。求在所有可能的情况中，指定的 $k(k\le n)$ 个人在游戏结束时最多共拥有多少枚硬币。

做法

• 通过按照时间阶段拆点，建立网络流模型：
  1. 源点向每个人连一条容量为 $1$ 的边
  2. 每回合都在选中的二人之间连容量为 $1$ 的边，并将二人的结点扩展出新结点。旧结点到新结点的容量为 $a_i$
  3. 最后将指定的 $k$ 个人的终态结点连向汇点，容量为 $a_i$
• 用 Dinic 算法求源点到汇点的最大流即可。

笔记

• 比较典型的拆点网络流建模。要点是将玩家每回合的状态拆开，然后将游戏回合中的硬币流动抽象为状态之间的流。当网络流中的结点有最大流量限制时，一般都是通过拆点把该限制转换为对边流量的限制。
• 关于最大流的时间复杂度：在流量极大时，Dinic 算法最坏情况下的时间复杂度为 $O(V^2E)$；而由于跑不满，实际情况中一般 3000 左右的点数和边数就可以使用最大流算法。然而，这题的最大流量较小，情况有所不同：由于每次增广最大流量都会提升，而增广一次的时间复杂度为 $O(E)$，总时间复杂度不会超过 $O(EF)$，其中 $F$ 为最大流量。

---

【03-02】King’s Ruins

题意

有 $n(n\le5\times10^4)$ 位骑士，分别给定每位骑士在 $5$ 个方面的能力值，以及选择每位骑士可以获得的价值。现在要按从左到右的顺序选择若干位骑士，要求每次选择的骑士在 $5$ 个方面的能力都不能小于上一次选择的骑士。求能够获得的最大价值。

做法

• 五维偏序问题，若使用 CDQ 分治复杂度为 $O(n\log^4)$ ，甚至劣于暴力的 $O(n^2)$。
• 考虑在 $O(n^2)$ 暴力 dp 的基础上应用分块技术。假设每块有 $k$ 个元素，对于每一块，块内元素暴力进行两两间转移需要 $O(k^2)$ ；块内元素与块后方 $O(n)$ 个元素间的转移可以等效为块的某个子集到块后方元素的转移，这需要用 bitset 在 $O(\frac{nk}{64})$ 预处理出每个块后元素需要转移的子集，并 $O(2^k)$ 预处理出每个子集的最大 dp 值。总共有 $O(\frac{n}{k})$ 个块，因此总时间复杂度为 $O(\frac{n}{k}(k^2+\frac{nk}{64}+2^k)) = O(nk+\frac{n^2}{64}+\frac{n\cdot 2^k}{k})$ 当 $k$ 取 $\log n$ 时，总时间复杂度为 $O(\frac{n^2}{\log n})$，恰好符合要求。

笔记

• 本题是一个很经典的偏序 dp 问题，但做法却是一个从没见过的神奇分块+bitset优化，记录之。
• 暴力预处理子集最大值需要 $O(2^k\cdot k)$ 时间；要想做到 $O(2^k)$ 可以对所有子集进行分治。
• 似乎有一种类似的算法叫“The Method of Four Russians”/“Four Russians”，思想是将区间每 $O(\log{n})$ 个元素分为一块，块内暴力计算，块间使用通常算法计算，从而优化通常算法的复杂度。该算法一般用来配合 ST 表优化 RMQ 问题。

---

【04-11】Circuit

题意

给定一张 $n(n\le 500)$ 个点的简单带权有向图，求最小环的长度和个数。

做法

• 最小环计数问题。为了不重不漏，可以仅在每个环上指向最大编号点的边处考虑该环。
• 用 Floyd 算法进行最短路计数，同时在枚举中间点 $k$ 时枚举指向 $k$ 的边 $(i,k)$，将以 $k$ 为最大编号点的最小环计入候选表，环的个数即为 $k$ 到 $i$ 的最短路条数。
• 最后在候选表中选择长度最小的环即可，总时间复杂度为 $O(n^3)$。

笔记

• 最小环是很经典的图论问题。通常考虑枚举所有边，再根据反向最短路得到包含该边的最小环。有向图或无向图都可以考虑 Floyd 和 Dijkstra：
  • 有向图 Floyd：枚举中间点 $k$ 的同时枚举边 $(i,k)$，看 $k$ 到 $i$ 的最短路。$O(n^3)$。
  • 无向图 Floyd：枚举中间点 $k$ 的同时枚举边 $(i,k)$ 和 $(k,j)$，看 $j$ 到 $i$ 的最短路。$O(n^3)$。
  • 有向图 Dijkstra：枚举所有边 $(i,j)$，求一次 $j$ 到 $i$ 的最短路。$O(m^2\log{m})$。
  • 无向图 Dijkstra：枚举所有边 $(i,j)$，屏蔽反向边求一次 $j$ 到 $i$ 的最短路。$O(m^2\log{m})$。

---

【04-12】a-b Problem

题意

有 $n(n\le10^5)$ 块石头，A 和 B 两人轮流进行操作，每次操作从剩余的石头中取一块，A 先手。给定 A 取第 $i$ 块石头的收益 $a_i$ 和 B 取第 $i$ 块石头的收益 $b_i$，求所有决策最优的情况下最终 A 的收益与 B 的收益的差值。

做法

• 问题可以等效转换为：初始时 $n$ 块石头都在 B 手中，轮到 A 时 A 可以从 B 手中抢走一块石头，而轮到 B 时 B 可以将一块石头藏起来不让 A 拿。若 A 抢走石头 $i$，二人的收益差距将会拉开 $a_i+b_i$。因此 A 和 B 的最优策略都是选择 $a_i+b_i$ 最大的石头。
• 根据上述结论进行排序模拟即可，时间复杂度为 $O(n\log{n})$。

笔记

• 结论很好猜，但是赛时并没有细想怎么证。题解给出的问题转换很巧妙，这种先假设一种极端情况再往另一种极端情况靠近的思想也很常用。

---

【06-02】Pair Sum and Perfect Square

题意

给定一个长度为 $n(n\le10^5)$ 的排列和 $q(q\le10^5)$ 个询问，每个询问的内容如下：

• 给定 $L$ 和 $R$，求有多少对 $i,j$ 满足 $L\le i<j\le R$ 且 $p_i+p_j$ 是一个完全平方数。

回答所有询问。

做法

• $O(n)$ 以内的完全平方数只有 $O(\sqrt{n})$ 个，所以整个排列中满足条件的元素对只有 $O(n\sqrt{n})$ 对。
• 预处理出所有满足条件的点对，并离线所有询问。考虑从右到左在每个后缀上用树状数组维护后缀的前缀的答案数，这样的时间复杂度为 $O((n\sqrt{n}+q)\log{n})$，有点难过。
• 将 $O(\log{n})$修改+$O(\log{n})$ 查询的树状数组换成 $O(1)$ 修改+$O(\sqrt{n})$ 查询的分块，总时间复杂度变为 $O(n\sqrt{n}+q\sqrt{n})$，符合时间要求。

笔记

• 查询满足 $L\le l<r\le R$ 的 $(l,r)$ 点对数，类似二维数点问题，非常经典。通常是将点对和询问按照左端点放在一起，从右往左考虑，不断加入左端点为 $i$ 的点对，使得条件 $L=i\le l$ 自动满足；然后查询前缀 $R$ 中的点对个数，使得 $r\le R$ 也满足。在点对数与询问数同数量级 $O(q)$ 时，通常用树状数组维护前缀，时间复杂度 $O(q\log{n})$，比较优秀；然而这题的点对数为 $O(q\sqrt{q})$ 级别，所以需要引入修改较快、查询较慢的数据结构。分块可以 $O(1)$ 修改、$O(\sqrt{n})$ 查询，正是一个完美的选择。

• 其实这题也是一道莫队二次离线模板题，将莫队转移的过程离线下来再通过可差分性预处理即可。

---

【08-06】Nested String

题意

给定字符串 $T_1,T_2,S(|T_1|,|T_2|,|S|\le 10^7)$，定义「T-嵌套串」为在 $T_1$ 任意位置插入 $T_2$ 得到的字符串。求 $S$ 中包含多少个位置不同或本身不同的T-嵌套串。

做法

• 数据范围为 $10^7$，只能考虑 $O(n)$ 算法。而字符串哈希的时空复杂度常数较大，难以通过。

• T-嵌套串的长度固定为 $|T_1|+|T_2|$，因此可以考虑枚举其在 $S$ 中的位置。对于每个位置 $S[l,r]$，判断它是否为T-嵌套串需要知道的是：

  1. $S[l,r]$ 与 $T_1$ 的最长公共前缀
  2. $S[l,r]$ 与 $T_1$ 的最长公共后缀
  3. $T_2$ 与 $S[l,r]$ 匹配的位置

  其中，1 和 2 等价于 $S$ 的所有后缀/前缀与 $T_1$ 的最长公共前缀/后缀，可以通过扩展 KMP 算法预处理得到；而 3 可以通过 KMP 算法轻松计算。

• 在预处理出上述信息后，对于每个位置 $S[l,r]$ 就可以算出 $T_2$ 插入后符合要求的位置范围。对该范围利用前缀和进行区间累加，最后再遍历 $T_2$ 在 $S$ 中的匹配位置即可统计出答案。

笔记

• 本题的要点在于将T-嵌套串分成三部分考虑，并将T-嵌套串前缀和后缀的匹配转换为 LCP 问题。处理模式串与文本串所有后缀的 LCP 是扩展 KMP 算法的典型应用。

---

【08-09】Diagonal Fancy

题意

给定一个 $n\times m(\sum n\times m\le 10^7)$ 的矩阵，求其中有多少个子正方形，满足该子正方形内每个从左上到右下的对角线内部的数字相同，且不同对角线之间数字互不相同。

做法

• 对于第一个条件，可以通过动态规划来维护：用 $dp(i,j)$ 表示以 $(i,j)$ 为右下角的满足第一个条件的最大正方形边长，有 $dp(i,j)=\min\lbrace dp(i-1,j),dp(i,j-1),dp(i-1,j-1)\rbrace +1$。
• 对于第二个条件，继续考虑上述转移：$dp(i-1,j)$ 保证了靠右上的 $2n-3$ 条对角线互不相同，$dp(i,j-1)$ 保证了靠左下的 $2n-3$ 条对角线互不相同，$dp(i-1,j-1)$ 保证了居中的 $2n-3$ 条对角线互不相同。因此只需要在转移时再检查一下靠右上的两条对角线和靠左下的两条对角线是否互不相同即可。若互不相同，则 $dp(i,j)=\min\lbrace dp(i-1,j),dp(i,j-1),dp(i-1,j-1)\rbrace +1$，否则 $dp(i,j)=\min\lbrace dp(i-1,j),dp(i,j-1),dp(i-1,j-1)\rbrace$。
• 总时间复杂度 $O(nm)$。

笔记

• 找符合条件子正方形常用的一种经典动态规划转移：$dp(i,j)=\min\lbrace dp(i-1,j),dp(i,j-1),dp(i-1,j-1)\rbrace +1$。

---

【08-10】Rikka with Square Numbers

题意

给定两个整数 $a,b(1\le a,b\le 10^9,a\neq b)$。每次操作可以让 $a$ 加或减一个完全平方数，求最少几次操作才能使 $a$ 变成 $b$。

做法

• 令 $d=|a-b|$，则相当于将 $b$ 表示为若干完全平方数的和或差。
• 若 $d$ 为完全平方数，则答案为 $1$。
• 否则分类讨论：

1. 若 $d$ 为奇数，则 $d=d\times 1=(\lceil\frac{d}{2}\rceil+\lfloor\frac{d}{2}\rfloor)(\lceil\frac{d}{2}\rceil-\lfloor\frac{d}{2}\rfloor)=\lceil\frac{d}{2}\rceil^2-\lfloor\frac{d}{2}\rfloor^2$，答案为 $2$
2. 若 $d$ 为 $4$ 的倍数，则 $d=\frac{d}{2}-(-\frac{d}{2})=(\frac{d}{4}+1)^2-(\frac{d}{4}-1)^2$，答案为 $2$
3. 若 $d$ 为 $4k+2$，首先至少可以花一步转换为奇数，即答案至多为 $3$，所以只需要判断 $d$ 能否表示为两平方数的和或差。由于 $p^2-q^2=(p+q)(p-q)$，$(p-q)$ 和 $(p+q)$ 的奇偶性一定相同，$p^2-q^2$ 不可能为 $4k+2$，即 $d$ 不可能表示为完全平方数的差。所以只需要枚举比 $d$ 小的所有完全平方数判断 $d$ 是否能表示为完全平方数的和即可。

• 总时间复杂度 $O(\sqrt{|a-b|})$。

笔记

• 与完全平方数相关的两个经典结论：

1. 奇数和 $4$ 的倍数一定能表示成两个完全平方数之差
2. 两个完全平方数之差一定是奇数或 $4$ 的倍数，即 $4k+2$ 不可能表示成两个完全平方数之差

---

【09-02】Shortest path

题意

有一张包含 $n(n\le10^{18})$ 个结点的图，对于每个结点 $i$ 按照如下方式建立有向边：

1. 若 $2i\le n$，则结点 $i$ 向结点 $2i$ 连边
2. 若 $3i\le n$，则结点 $i$ 向结点 $3i$ 连边
3. 若 $i+1\le n$，则结点 $i$ 向结点 $i+1$ 连边

求结点 1 到结点 $n$ 的最短距离。

做法

• 将问题逆向，相当于通过除以 $2$、除以 $3$、减 $1$ 三种操作将一个初始为 $n$ 的数变为 $1$。
• 先减两次再除以 $2$ 或先减三次再除以 $3$ 都是非最优的，因此每次除以 $2$ 前最多减 $1$ 次，每次除以 $3$ 前最多减 $2$ 次。
• 从 $n$ 出发记忆化搜索，每次除以 $2$/除以 $3$ 操作一定在下方最近的 $2$ 的倍数/$3$ 的倍数处进行。搜到的点都可以表示为 $\lfloor \frac{n}{2^a3^b}\rfloor$，总共有 $O(\log^2n)$ 个。

笔记

• 典中典套路。将减 $1$ 操作作为基本操作，填充在特殊操作（除以 $2$/除以 $3$）之间，搜索时直接跳过，不需要记录每次减 $1$ 操作的结果，这样才能保证较低的时间复杂度。
• 元素个数较少时可以用 unordered_map 优化复杂度。

---