Uol 2025 Wk3 && LeetCode Biweekly Contest 168 题解

Weak Vertices (弱顶点)

问题描述

在图论中，一个网络的结构强度通常可以通过识别其中的基本形状（如三角形）来分析。三角形能提供结构刚性，是许多应用中常见的母题。这个问题要求我们识别那些不属于任何三角形的顶点。一个顶点 i 被定义为属于一个三角形，如果它有两个不同的邻居 j 和 k，并且 j 和 k 彼此之间也是邻居。我们的任务是找出所有不满足此条件的顶点，问题将其称为“弱顶点”。图以邻接矩阵的形式给出。

我的代码

我的方法是对定义进行直接模拟。对每个顶点，我遍历其所有邻居对，并检查它们之间是否相连。

// 遍历从 0 到 n-1 的每个顶点 `i`，检查它是否是弱顶点。
for(int i=0; i<n; i++) {
    // 一个标志位，用于追踪顶点 `i` 是否属于任何三角形。
    // 我们将其初始化为 true，假设 `i` 是弱顶点，直到找到反证。
    bool flag = true;

    // 遍历 `i` 的所有邻居。
    // 外层循环选择第一个邻居 `j`。
    for(int j=0; j<siblings[i].size(); j++) {
        // 内层循环选择第二个邻居 `k`。
        // 我们从 j+1 开始，以确保每对邻居只被考虑一次。
        for(int k=j+1; k<siblings[i].size(); k++) {
            // 检查 `i` 的两个邻居，即 `siblings[i][j]` 和 `siblings[i][k]`，
            // 是否相互连接。
            if(graph[siblings[i][j]][siblings[i][k]]) {
                // 如果它们相连，那么顶点 `i`、`j` 和 `k` 构成一个三角形。
                // 因此，顶点 `i` 不是弱顶点。我们将标志位设为 false。
                flag = false;
                // 既然已经找到了一个涉及 `i` 的三角形，我们可以停止对该顶点的检查。
                break;
            }
        }
        // 如果标志位已被设为 false，我们也可以跳出外层的邻居循环。
        if(!flag) {
            break;
        }
    }

    // 如果在检查完所有邻居对后，标志位仍然为 true，
    // 这意味着没有找到涉及 `i` 的三角形。因此，`i` 是一个弱顶点。
    if(flag) {
        cout<<i<<' ';
    }
}

我的解法及其正确性

这个问题要求我们识别给定无向图中所有不属于任何三角形的顶点。如果一个顶点满足这个条件，它就被认为是“弱”的。图的结构通过一个 $n \times n$ 的邻接矩阵给出，其中 $n$ 是顶点的数量。

我的解法直接实现了问题给出的定义。其核心逻辑是，对每个顶点进行详尽的检查，判断其是否满足构成三角形的条件。算法逐个顶点处理，从 $0$ 到 $n-1$。对于每个顶点（我们称之为 $i$），我们先假设它是一个弱顶点。然后，我们试图通过寻找包含 $i$ 的三角形的证据来推翻这个假设。一个包含顶点 $i$ 的三角形将由 $i$ 和它的两个邻居（比如说 $j$ 和 $k$）组成，其中 $j$ 和 $k$ 之间也有一条边相连。

为了执行此检查，我的算法首先识别出顶点 $i$ 的所有邻居。这是在输入阶段通过读取邻接矩阵完成的，并将每个顶点的邻居存储在一个邻接表表示中，我称之为 siblings。这个预处理步骤简化了邻居查找过程。对于给定的顶点 $i$ ，siblings[i] 包含一个列表，其中包含了所有与 $i$ 有边相连的顶点 $j$。

有了顶点 $i$ 的邻居列表后，下一步是检查这些邻居的所有可能对。如果顶点 $i$ 有 $d_i$ 个邻居，那么存在 $\binom{d_i}{2}$ 个这样的对。我使用一对嵌套循环来遍历每一对唯一的邻居。假设邻居在 siblings[i] 列表中的索引从 $0$ 到 $d_i-1$。外层循环选择索引为 $j$ 的邻居，内层循环选择索引为 $k$ 的邻居，其中 $k > j$。这确保了每对邻居被精确地考虑一次，避免了冗余检查（例如，同时检查 $(j, k)$ 和 $(k, j)$）和自我比较（$j=k$）。

对于每一对邻居，比如说顶点 $u$ (来自 siblings[i][j]) 和顶点 $v$ (来自 siblings[i][k])，算法会检查 $u$ 和 $v$ 之间是否存在一条边。这个检查通过查询邻接矩阵中的条目 graph[u][v] 来高效完成。如果该条目为真（或1），则表示边 $(u, v)$ 存在。边 $(i, u)$, $(i, v)$ 和 $(u, v)$ 的存在确认了三角形 ${i, u, v}$ 的存在。

一个布尔变量 flag 用来维护当前顶点 $i$ 的状态。它被初始化为 true，代表了 $i$ 是弱顶点的初始假设。一旦算法找到 $i$ 的一对邻居彼此相连，它就找到了一个涉及 $i$ 的三角形。此时，关于 $i$ 是弱顶点的假设被推翻。flag 被设置为 false，并且由于我们只需要找到一个三角形就能将一个顶点排除在弱顶点之外，对顶点 $i$ 的搜索就可以立即终止。break 语句用于提前退出内层和外层循环以提高效率。

如果嵌套循环执行完毕而 flag 从未被设置为 false，这意味着对于 $i$ 的每一对邻居，它们之间都不存在直接的边。这详尽地证明了不存在涉及顶点 $i$ 的三角形。因此，初始假设成立，顶点 $i$ 确实是一个弱顶点。在这种情况下，算法会打印出索引 $i$。整个过程对图中的所有顶点重复进行，确保每个顶点都被正确分类。

为了形式化地证明该算法的正确性，让我们使用谓词逻辑的语言。设 $G=(V, E)$ 为图，其中 $V={0, 1, \dots, n-1}$ 是顶点集， $E$ 是边集。设 $A$ 是 $G$ 的邻接矩阵表示，使得如果 $(u,v) \in E$，则 $A_{uv} = 1$，否则 $A_{uv} = 0$。一个顶点 $i \in V$ 被定义为属于一个三角形，我们将此属性表示为 $T(i)$，当且仅当： $T(i) \iff \exists j, k \in V \text{ 使得 } (j \neq i) \land (k \neq i) \land (j \neq k) \land (A_{ij}=1) \land (A_{ik}=1) \land (A_{jk}=1)$。 一个顶点 $i$ 是弱的，我们表示为 $W(i)$，如果它不属于任何三角形： $W(i) \iff \neg T(i) \iff \neg (\exists j, k \in V : (j \neq i) \land (k \neq i) \land (j \neq k) \land A_{ij}=1 \land A_{ik}=1 \land A_{jk}=1)$。 根据德摩根定律，这等价于： $W(i) \iff \forall j, k \in V, \neg ((j \neq i) \land (k \neq i) \land (j \neq k) \land A_{ij}=1 \land A_{ik}=1 \land A_{jk}=1)$。 这可以简化为： $W(i) \iff \forall j, k \in V, ((A_{ij}=1) \land (A_{ik}=1)) \implies (A_{jk}=0 \lor i=j \lor i=k \lor j=k)$。 设 $N(i)$ 为 $i$ 的邻居集合，即 $N(i) = {j \in V \mid A_{ij}=1}$。构成三角形的条件可以重述为： $T(i) \iff \exists j, k \in N(i) \text{ 使得 } (j \neq k) \land (A_{jk}=1)$。 因此，成为弱顶点的条件是： $W(i) \iff \forall j, k \in N(i), (j=k) \lor (A_{jk}=0)$。因为我们只关心不同邻居对，这等价于： $W(i) \iff \forall j, k \in N(i) \text{ 且 } j \neq k, \text{ 都有 } A_{jk}=0$。 我的算法逻辑是这最后一个陈述的直接实现。外层 for 循环确保每个顶点 $i \in V$ 都被考虑到。对于每个 $i$，嵌套循环遍历所有唯一的不同邻居对 ${j, k} \subseteq N(i)$。条件 if(graph[siblings[i][j]][siblings[i][k]]) 是对 $A_{jk}=1$ 的直接检查。如果这个条件曾经为真，flag 就被设为 false，正确地得出 $\neg W(i)$ 为真。如果循环完成而此条件从未满足，则意味着对于所有不同邻居对 ${j, k}$，$A_{jk}=0$，这正是 $W(i)$ 的定义。因此，该算法正确地识别并打印出所有弱顶点的集合。其正确性由此得到证实。

时间和空间复杂度

算法的复杂度分析对于理解其性能至关重要，特别是随着图的大小的增长。

时间复杂度: 算法的主要部分是为每个顶点执行的一组嵌套循环。让我们来分析所做的工作。主要过程被一个从 $i=0$ 到 $n-1$ 的 for 循环所包围，其中 $n$ 是顶点的数量。这个循环运行 $n$ 次。在这个循环内部，对于每个顶点 $i$，我们执行一个三角形形成的检查。这个检查涉及到遍历 $i$ 的邻居对。让 $d_i$ 表示顶点 $i$ 的度（即它的邻居数，siblings[i].size()）。两个嵌套循环旨在选择这 $d_i$ 个邻居的每一个唯一对。这样的对的数量由二项式系数 $\binom{d_i}{2} = \frac{d_i(d_i-1)}{2}$ 给出。对于每一对，都会在邻接矩阵中执行一次常数时间的查找。因此，处理单个顶点 $i$ 的总操作数与 $d_i^2$ 成正比。将此对所有顶点求和，总时间复杂度 $T(n)$ 由以下公式给出： $T(n) = \sum_{i=0}^{n-1} O(d_i^2) = O(\sum_{i=0}^{n-1} d_i^2)$。 在最坏的情况下，图是一个完全图（$K_n$），其中每个顶点都与其他所有顶点相连。在这种情况下，每个顶点的度都是 $d_i = n-1$。时间复杂度变为： $T(n) = O(\sum_{i=0}^{n-1} (n-1)^2) = O(n \cdot (n-1)^2) = O(n^3)$。 这种立方级别的复杂度表明，该算法非常适合顶点数量较少的图，正如问题约束所规定的（$n \le 20$），其中 $20^3 = 8000$，这在计算上是非常可行的。

为了形式化地证明这一点，设 $C$ 为最内层循环单次检查的最大成本（一个常数）。总操作数 $T_{ops}(n)$ 可以被限制为： $T_{ops}(n) \le \sum_{i=0}^{n-1} C \cdot \frac{d_i(d_i-1)}{2}$。 由于对于任何顶点 $i$ 都有 $d_i \le n-1$，我们可以建立一个上界： $T_{ops}(n) \le \sum_{i=0}^{n-1} C \cdot \frac{(n-1)(n-2)}{2} = n \cdot C \cdot \frac{(n-1)(n-2)}{2}$。 这个表达式是关于 $n$ 的一个三次多项式。根据大O符号的定义，必须存在常数 $c > 0$ 和 $n_0$，使得对于所有 $n \ge n_0$，$T_{ops}(n) \le c \cdot n^3$。我们导出的上界 $n \cdot C \cdot \frac{(n-1)(n-2)}{2}$ 显然满足这个条件，所以时间复杂度形式上是 $O(n^3)$。

空间复杂度: 空间复杂度由存储图结构所需的内存量决定。我的解决方案使用两种主要的数据结构来实现此目的：

1. 一个邻接矩阵 graph，它是一个 $n \times n$ 的布尔矩阵。这需要 $O(n^2)$ 的空间。
2. 一个邻接表 siblings，它是一个向量的向量。在最坏的情况下（一个稠密图），所有列表中的条目总数是 $2|E|$，其中 $|E|$ 是边的数量。对于一个完全图， $|E| = \binom{n}{2} = O(n^2)$。因此，邻接表在最坏情况下也需要 $O(n^2)$ 的空间。 其他变量，如循环计数器和布尔标志，只使用常数数量的额外空间，即 $O(1)$。 因此，总空间复杂度由图的表示方式主导，使其为 $O(n^2)$。

形式上，设 $S(n)$ 是所需的总空间。 $S(n) = \text{空间}(\text{graph}) + \text{空间}(\text{siblings}) + \text{空间}(\text{其他})$。 $\text{空间}(\text{graph}) = n \times n \times \text{sizeof(bool)} = \Theta(n^2)$。 $\text{空间}(\text{siblings}) = \sum_{i=0}^{n-1} d_i \times \text{sizeof(int)} = 2|E| \times \text{sizeof(int)} = O(|E|)$。 由于 $|E| \le n^2$，我们有 $\text{空间}(\text{siblings}) = O(n^2)$。 $\text{空间}(\text{其他}) = O(1)$。 所以，$S(n) = \Theta(n^2) + O(n^2) + O(1) = O(n^2)$。这完成了形式化的复杂度分析。

Where’s my Internet? (我的网络在哪？)

问题描述

这个问题描绘了一个新建城镇中房屋连接互联网的场景。我们有 $N$ 座房屋，编号从 1 到 $N$，以及 $M$ 条已存在的房屋间网络电缆连接。1号房屋是整个城镇互联网连接的源头。如果一所房子是1号房，或者它通过电缆连接到另一所已经联网的房子，那么它就被认为是已连接到互联网。任务是识别并列出所有尚未连接到互联网的房屋。如果所有房屋都已连接，我们应该报告这一点。

我的代码

这个问题是关于图的连通性的。我意识到这是一个使用不相交集联合（Disjoint Set Union, DSU），也称为并查集数据结构的完美案例。我将房屋建模为图的节点，电缆建模为边。所有能够相互到达的房屋形成一个连通分量，DSU可以有效地跟踪这些分量。

/// \brief 不相交集联合 (并查集) 类
class UnionFind {
private:
    vector<int> parent; // parent[i] 存储元素 i 的父节点
    vector<int> rank;   // 用于按秩合并优化

public:
    // 构造函数初始化 n 个元素，每个元素自成一个集合。
    explicit UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        // 最初，每个元素都是自己的父节点。
        for(int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    // 查找包含 x 的集合的代表（根），带路径压缩。
    int find(int x) {
        if(parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }

    // 合并包含 x 和 y 的集合，使用按秩合并。
    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if(rootX != rootY) { // 仅当它们在不同集合时才合并
            if(rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                if(rank[rootX] == rank[rootY]) {
                    rank[rootX]++;
                }
            }
        }
    }

    // 检查 x 和 y 是否在同一个集合中。
    bool same(int x, int y) {
        return find(x) == find(y);
    }
};

// 主逻辑
int N,M;
cin >> N >> M;
// 为 N+1 座房屋创建一个 DSU 结构（使用从1开始的索引）。
UnionFind uf = UnionFind(N+1);
while(M--) {
    int a, b;
    cin >> a >> b;
    // 每条电缆连接意味着我们合并这两座房屋所在的集合。
    uf.unite(a,b);
}

bool flag = false; // 标志位，检查是否有任何房屋未连接。
// 遍历从 2 到 N 的所有房屋。
for(int i=2; i<=N; i++) {
    // 如果房屋 `i` 与 1 号房屋在同一个集合中，则它已连接到互联网。
    if(!uf.same(i,1)) {
        cout << i << endl; // 如果不在，则打印其编号。
        flag = true;
    }
}
// 如果标志位从未被设置，说明所有房屋都已连接。
if(!flag) {
    cout << "Connected";
}

我的解法及其正确性

这个问题要求我们确定在一个由 $N$ 座房屋和 $M$ 条电缆连接组成的网络中，哪些房屋没有连接到互联网。互联网源自1号房屋。连通性是可传递的：如果房屋A连接到房屋B，B连接到C，那么A、B、C都相互连接。如果一所房屋与1号房屋属于同一个连通块，那么它就拥有互联网。

这个问题可以被建模为寻找图的连通分量。房屋是顶点，电缆是边。所有与顶点1在同一个连通分量中的房屋都将有互联网接入。其他分量中的所有房屋则没有。我选择用来解决这个问题的数据结构是不相交集联合（DSU）或称并查集。这个结构专门设计用来跟踪一个元素集合划分为多个不相交子集的情况。在我们的案例中，元素集合就是房屋集合，每个子集将代表一个连通分量。

最初，我将 $N$ 座房屋中的每一座都视为一个独立的连通分量。DSU被初始化为 $N+1$ 个元素（为了方便使用从1到$N$的1-based索引），其中每个元素都是自己的“父节点”或“代表”，表示有 $N$ 个不相交的集合。

然后，我逐一处理这 $M$ 条电缆连接。每条连接，比如说在房屋a和房屋b之间，意味着这两座房屋是直接相连的。在我们连通分量的背景下，这意味着包含a的分量和包含b的分量现在应该被视为一个更大的单一分量。我DSU类中的unite(a, b)操作完成了这件事。它找到包含a和b的集合的代表。如果它们不相同，它就合并这两个集合。为了保持该结构的效率，我采用了两个标准的优化：按秩合并和路径压缩。

• 按秩合并 (Union by Rank): 在合并两个集合时，具有较小“秩”（一个大致衡量树的深度的指标）的集合的代表被附加到具有较大秩的集合的代表上。这有助于防止表示集合的树变得过高和不平衡，从而减慢find操作。
• 路径压缩 (Path Compression): 在执行find(x)操作期间，该操作会遍历从元素x到其根代表的路径，我们让该路径上的每个节点都直接指向根。这会随着时间的推移极大地扁平化树的结构，使得后续对这些元素（或其后代）的find操作接近常数时间。

在处理完所有 $M$ 条电缆连接后，DSU结构准确地反映了房屋网络的连通分量。DSU中的每个集合对应一个连通分量。最后一步是确定哪些房屋连接到了互联网。一所房屋i有互联网当且仅当它与1号房屋在同一个连通分量中。DSU提供了一种高效检查这个条件的方法：same(i, 1)函数。如果i和1属于同一个集合（即它们有相同的根代表），该函数返回true，否则返回false。

我的代码遍历从2到$N$的所有房屋。对于每个房屋i，它调用uf.same(i, 1)。如果返回false，意味着房屋i与1号房屋不在同一个分量中，因此没有互联网连接。然后打印出数字i。如果循环完成并且没有发现这样的房屋，这意味着从2到$N$的每个房屋都与1号房屋在同一个分量中。在这种情况下，程序打印“Connected”。

该方法的形式化正确性证明基于DSU能够正确地建模等价关系。“连通”关系在图中是一种等价关系：

1. 自反性: 任何顶点v都与自身连通（通过长度为0的路径）。
2. 对称性: 如果u与v连通，那么v也与u连通（因为边是无向的）。
3. 传递性: 如果u与v连通，v与w连通，那么u也与w连通。 一个等价关系将一个集合划分为不相交的等价类。在图论中，这些等价类正是连通分量。DSU数据结构就是用来维护这种划分的。让我们来证明，在处理完所有边之后，两个顶点$u, v$在DSU中属于同一个集合，当且仅当它们在图中有路径相连。

• 对unite操作（处理的边）的数量进行归纳证明：
• 基础情况: 在处理任何边之前（$m=0$），每个顶点都在其自己的集合中。这是正确的，因为不同顶点之间没有路径。
• 归纳假设: 假设在处理了$k$条边之后，DSU正确地表示了由这$k$条边形成的图的连通分量。
• 归纳步骤: 考虑处理第$(k+1)$条边 $(u, v)$。unite(u, v)操作合并了包含$u$和$v$的集合。在图中，这条新边在$u$的旧分量中的任何节点与$v$的旧分量中的任何节点之间创建了路径。因此，这两个分量应该合并成一个，这正是unite操作所做的。之前在同一个分量中的任何两个节点仍然如此。之前在不同分量中且不在新合并分量中的任何两个节点也仍然在不同分量中。因此，在处理第$(k+1)$条边后，DSU的划分仍然是正确的。 通过归纳法，在处理完所有$M$条边后，DSU正确地将顶点划分为图的连通分量。一所房屋i有互联网，当且仅当从i到1存在路径。这等价于i和1在同一个连通分量中。我的算法使用uf.same(i, 1)来检查这一点。因此，逻辑是正确的。

时间和空间复杂度

时间复杂度: 总体时间复杂度由三部分决定：DSU的初始化、处理$M$条电缆连接以及最终的连通性检查。

1. 初始化: UnionFind构造函数为$N+1$个元素初始化parent和rank数组。这涉及一个运行$N+1$次的循环。复杂度为$O(N)$。
2. 处理连接: 我们循环$M$次。在每次迭代中，我们执行两次find操作和一次unite操作。借助路径压缩和按秩（或大小）合并这两个关键优化，单个find或unite操作的摊销时间复杂度接近常数。它更正式地用反阿克曼函数 $\alpha(N)$ 表示，这是一个增长非常缓慢的函数。对于所有计算中的实际目的，$\alpha(N)$小于5。因此，一次操作的成本可以认为是$O(\alpha(N))$。处理所有$M$个连接的总时间因此是$O(M \cdot \alpha(N))$。
3. 最终检查: 我们从房屋2循环到$N$，即$N-1$次迭代。在每次迭代中，我们执行一次same(i, 1)调用，这涉及两次find操作。这部分的总时间是$O(N \cdot \alpha(N))$。

综合这些部分，总时间复杂度是$O(N + M \cdot \alpha(N) + N \cdot \alpha(N))$，简化为$O((N+M)\alpha(N))$。考虑到约束条件（$N, M \le 200,000$），这是非常高效的。

为了形式化地陈述，我们用 $T_{dsu}(N)$ 表示一次DSU操作的成本。同时使用路径压缩和按秩/大小合并，已知对$n$个元素的$m$次操作序列耗时$O(m \cdot \alpha(n))$。在我们的案例中，初始化耗时$T_{init}(N) = c_1 N$。主循环执行$M$次unite操作，每次调用两次find，这是一个包含$3M$次操作的序列。最后的循环执行$N-1$次same操作，每次调用两次find，总共是$2(N-1)$次操作。DSU操作的总数是$m = 3M + 2(N-1)$。总时间是$T(N, M) = T_{init}(N) + T_{ops}(N, M) = c_1 N + O((3M + 2(N-1))\alpha(N)) = O((N+M)\alpha(N))$。这证实了复杂度。

空间复杂度: 内存使用主要由DSU数据结构所需的存储决定。

1. parent向量为$N+1$座房屋中的每一座存储一个整数。这需要$O(N)$的空间。
2. rank向量也为$N+1$座房屋中的每一座存储一个整数，同样需要$O(N)$的空间。 其他变量的大小是常数的。因此，我的解决方案的总空间复杂度是$O(N)$。

形式上，$S(N) = \text{空间}(\text{parent}) + \text{空间}(\text{rank}) = c_1 (N+1) + c_2 (N+1) = O(N)$。

Grid (网格)

问题描述

这个问题挑战我们在一个网格上找到最短路径。给定一个 $n \times m$ 的网格，每个单元格上都有一个数字，比如说 $k$。从一个包含数字 $k$ 的单元格出发，一次“移动”包括向四个基本方向（上、下、左、右）之一精确跳跃 $k$ 个方格。移动不能超出网格的边界。目标是找到从左上角单元格到右下角单元格所需的最少移动次数。如果目的地无法到达，我们应该报告-1。

我的代码

这是一个在无权图上的最短路径问题。网格单元可以被看作是节点，可能的跳跃可以看作是边。广度优先搜索（BFS）是寻找无权图最短路径的经典算法。我的实现使用了一个优先队列，这使其类似于Dijkstra算法。然而，由于所有的“边权重”都隐含为1（每次移动算一步），这种方法的功能与标准的BFS完全相同，并且能正确地找到最短路径。

// 用于保存状态的结构体：坐标(x, y)和已走的步数。
struct state {
public:
    int x;
    int y;
    int step;
};

// 主逻辑
int n, m;
cin >> n >> m;
// 从输入中读取网格。
vector<vector<int>> grid(n, vector<int>(m));
for(int i = 0; i < n; i++) {
    string line;
    cin >> line;
    for(int j = 0; j < m; j++) {
        grid[i][j] = line[j] - '0';
    }
}

// 一个集合，用于跟踪已访问的网格单元，以避免循环和冗余计算。
unordered_set<pair<int, int>, pair_hash, pair_equal> visited{};

// 一个优先队列，用于管理待访问的状态。虽然对于标准BFS来说，
// 一个简单的队列就足够了，但由于所有边权重都是均匀的（1），
// 优先队列在这里也能正确工作。它会逐层探索。
// 我的自定义比较器并非必需，是为实验而添加的。
auto comp = [](const state &a, const state &b) {
    return a.step > b.step;
};
priority_queue<state, vector<state>, decltype(comp)> pq{};
pq.push(state{0, 0, 0}); // 从(0,0)开始，步数为0。

while(!pq.empty()) {
    auto top = pq.top();
    pq.pop();
    int x = top.x;
    int y = top.y;

    // 如果我们已经处理过这个单元格，就跳过它。
    if(visited.count({x, y})) {
        continue;
    }
    visited.insert(make_pair(x, y));

    // 从当前单元格获取跳跃距离。
    int jump_dist = grid[x][y];
    // 定义四个可能的移动。
    pair<int, int> next_moves[4] = {
            make_pair(x + jump_dist, y), // 下
            make_pair(x - jump_dist, y), // 上
            make_pair(x, y + jump_dist), // 右
            make_pair(x, y - jump_dist)  // 左
    };

    for(auto [next_x, next_y]: next_moves) {
        // 检查是否到达目的地。
        if(next_x == n - 1 && next_y == m - 1) {
            cout << top.step + 1; // 找到了最短路径。
            return 0;
        }

        // 检查移动是否有效（在网格边界内）并且不是跳到零跳跃单元格。
        if(next_x >= 0 && next_x < n && next_y >= 0 && next_y < m && grid[next_x][next_y]!=0) {
            // 将新状态推入队列。
            pq.push(state{next_x, next_y, top.step + 1});
        }
    }
}

// 如果队列变空且目的地未到达，则说明不可能到达。
cout << -1;

我的解法及其正确性

这个问题要求从一个起始单元格到一个目标单元格的最小移动次数。这是图上最短路径问题的经典例子。我们可以通过将网格的每个单元格 $(i, j)$ 视为一个顶点来构建这个图。如果我们可以通过一次合法的跳跃从一个单元格移动到另一个单元格，那么在对应的顶点之间就存在一条边。由于每次移动都算作1步，这个图是无权的。问题就简化为在图中找到从对应于单元格 $(0, 0)$ 的顶点到对应于单元格 $(n-1, m-1)$ 的顶点的最短路径。

在无权图中寻找最短路径的规范算法是广度优先搜索（BFS）。BFS从源顶点开始，系统地逐层探索图。它首先发现所有距离为1的顶点，然后是所有距离为2的顶点，依此类推。这个特性保证了BFS第一次到达目的顶点时，它所经过的一定是一条最短路径。

我的解法实现了这种类似BFS的遍历。我使用一个数据结构，在这里是一个优先队列，来存储搜索的“前沿”——即已经到达但其邻居尚未被探索的单元格集合。一个state结构体用于存储一个单元格的坐标和到达它所用的移动次数（step）。搜索从将初始状态 {0, 0, 0} 放入队列开始。

算法的主要部分是一个只要队列不为空就持续的循环。在每次迭代中，它从队列中取出一个状态。假设我们取出了单元格 $(x, y)$ 的状态，它是在 top.step 步内到达的。为了防止在有环路的情况下出现无限循环并避免冗余计算，我使用了一个visited集合。如果单元格 $(x, y)$ 已经被访问过，我们就简单地丢弃当前状态，继续处理下一个。否则，我们将 $(x, y)$ 标记为已访问。

接下来，算法从当前单元格确定跳跃距离 $k = \text{grid}[x][y]$。然后，它通过从当前坐标加减 $k$ 来计算四个潜在目标单元格的坐标。对于每个到单元格 $(next_x, next_y)$ 的潜在移动：

1. 它首先检查这个新单元格是否是目标终点 $(n-1, m-1)$。如果是，我们已经找到了一条路径。由于BFS是按路径长度递增的顺序探索的，这必须是一条最短路径。其长度是当前路径长度（top.step）再加一次移动。程序打印这个数字并终止。
2. 如果不是终点，算法会验证移动是否有效：新坐标必须在网格的边界内（$0 \le next_x < n$ 且 $0 \le next_y < m$）。我还增加了一个检查，确保目标单元格的跳跃值不为零，这会造成死胡同。
3. 如果移动是有效的，一个新的状态 {next_x, next_y, top.step + 1} 被创建并添加到队列中以备将来探索。

如果主循环结束（即队列变空）而目的地仍未到达，这意味着目的单元格位于图的一个从起始单元格无法到达的部分。在这种情况下，算法打印-1。

现在，让我们提供一个形式化的正确性证明。该算法是Dijkstra算法的一个变体，在边权重均等的正权图上（本例中所有权重都为1），其行为与BFS完全相同。让我们证明它能找到最短路径。 设 $d(v)$ 为从源顶点 $s$（单元格 $(0,0)$）到任意顶点 $v$ 的最短路径长度。我们要证明当算法到达目的地 $t$（单元格 $(n-1, m-1)$）并终止时，它找到的路径长度 step+1 等于 $d(t)$。 我们通过归纳法证明，当一个顶点 $v$ 从优先队列中被取出时，值 v.step 等于 $d(v)$。

• 基础情况: 第一个被取出的顶点是源点 $s$，其 s.step = 0。从源点到其自身的最短路径确实是0。所以基础情况成立。
• 归纳假设: 假设对于在顶点 $v$ 之前从队列中取出的所有顶点 $u$，都有 u.step = $d(u)$。
• 归纳步骤: 设 $v$ 是下一个要从队列中取出的顶点。设 $u$ 是导致 $v$ 被添加到队列中的顶点。这意味着存在一条边 $(u, v)$ 并且 v.step = u.step + 1。根据归纳假设，u.step = d(u)。因此，v.step = d(u) + 1。这意味着存在一条长度为 v.step 的到 $v$ 的路径。我们现在需要证明这是最短路径。 考虑任何从 $s$ 到 $v$ 的路径。设此路径为 $s=v_0, v_1, \dots, v_k=v$。设 $v_i$ 是这条路径上第一个尚未从队列中取出的顶点。它的所有前驱 $v_0, \dots, v_{i-1}$ 都已被取出。设 $v_{i-1}$ 是其直接前驱。当 $v_{i-1}$ 被处理时，$v_i$ 的状态会被推入队列，步数为 v_{i-1}.step + 1。根据归纳假设，$v_{i-1}.step = d(v_{i-1}) = i-1$。所以，$v_i$ 在队列中的步数值为 $i$。由于我的优先队列（以及标准的BFS队列）是按 step 值的非递减顺序处理节点的，如果 v.step > v_i.step，$v$ 不可能在 $v_i$ 之前被取出。由于路径 $s, \dots, v_k=v$ 的长度为 $k$，我们知道 $d(v) \le k$。这条路径上的顶点 $v_i$ 在队列中的步数值为 $i$。到 $v$ 的路径长度是 $k$。任何到 $v$ 的路径都必须经过一个前沿节点。算法总是扩展前沿上步数最小的节点。因此，当它到达 $v$ 时，必定是通过一条长度为 $d(v)$ 的路径。所以 $v.step = d(v)$。 由于算法在到达目的地 $t$ 时立即终止，此时的步数将是 $d(t)$，即最短路径长度。如果 $t$ 从未被到达，队列将变空，正确地表明不存在路径。

时间和空间复杂度

时间复杂度: 该搜索算法的时间复杂度取决于图中顶点和边的数量。在我们的网格中，顶点数 $|V|$ 是 $n \times m$。每个顶点最多有4条出边。所以，边数 $|E|$ 最多是 $4 \times n \times m$，即 $O(nm)$。 主循环只要优先队列不为空就会运行。由于visited集合的存在，每个顶点（单元格）最多被添加到队列中一次。当我们处理一个顶点时，我们做常数次操作（检查它的4个邻居）。优先队列的操作（push和pop）在其大小上取对数时间。队列的最大大小是 $|V|=nm$。 所以，复杂度由每个顶点和边的队列操作主导。总时间复杂度是 $O(|V| \log |V| + |E|) = O(nm \log(nm) + 4nm) = O(nm \log(nm))$。 注意：如果使用标准队列进行纯粹的BFS，入队和出队操作将是$O(1)$，导致时间复杂度为$O(|V|+|E|) = O(nm)$。由于我的解法使用了优先队列，分析中包含了对数因子。

让我们将其形式化。设 $N = n \times m$。顶点数为 $N$。边数最多为 $4N$。该算法本质上是Dijkstra算法。

1. 推入初始状态: $O(\log N)$。
2. while 循环最多运行 $N$ 次（每个顶点一次）。
3. 循环内部:
   • pq.pop(): $O(\log N)$。
   • 在无序集合上的 visited.count() 和 visited.insert() 平均为 $O(1)$。
   • 内层循环运行4次。
   • 内层循环中，pq.push(): $O(\log N)$。 总时间: $N \times (O(\log N) + O(1) + 4 \times O(\log N)) = N \times O(\log N) = O(nm \log(nm))$。

空间复杂度: 所需空间由存储网格、visited集合和优先队列的数据结构决定。

1. 网格: grid本身是一个 $n \times m$ 的矩阵，需要 $O(nm)$ 的空间。
2. Visited 集合: 在最坏的情况下，visited集合可以为网格中的每个单元格存储一对坐标。这需要 $O(nm)$ 的空间。
3. 优先队列: 优先队列在最坏情况下也可以为网格中的每个单元格保存一个state。这也需要 $O(nm)$ 的空间。 将这些加起来，总空间复杂度是 $O(nm) + O(nm) + O(nm) = O(nm)$。

形式上，$S(n, m) = \text{空间}(\text{grid}) + \text{空间}(\text{visited}) + \text{空间}(\text{pq})$。 设 $N=nm$。 $S(n, m) = c_1 N + c_2 N + c_3 N = O(N) = O(nm)$。

Oddities (奇数)

问题描述

这是一个关注奇偶性概念的基础编程练习。我们需要确定一个给定的整数是奇数还是偶数。一个整数 $n$ 如果是2的倍数（即可以表示为 $n=2k$，其中 $k$ 是某个整数），则定义为偶数，否则为奇数。程序需要处理多个测试用例，读取一个整数并打印它是奇数还是偶数。

我的代码

解决方案非常直接，依赖于模运算符（%），它给出除法的余数。如果一个数除以2的余数是0，它就是偶数；如果余数是1，它就是奇数。我还通过先取绝对值来处理负数。

// 首先读取测试用例的数量 `n`。
int n;
cin>>n;
// 循环 `n` 次以处理每个测试用例。
while(n--) {
    int x;
    cin>>x;
    // 为了正确处理像 -5 这样的负数，我们首先取其绝对值。
    // 然后，我们使用模运算符 (%) 来找到除以 2 的余数。
    // 如果 abs(x) % 2 是 1，则该数为奇数。
    // 如果 abs(x) % 2 是 0，则该数为偶数。
    // 使用三元运算符 `(condition ? value_if_true : value_if_false)`
    // 来获得一个紧凑的输出字符串。
    cout << x << " is " << ((abs(x) % 2 == 1) ? "odd" : "even") << endl;
}

我的解法及其正确性

这个问题是要求将一个给定的整数 $x$ 分类为“偶数”或“奇数”。奇偶性的数学定义是解决这个问题的核心。一个整数 $z$ 被称为偶数，如果它可以写成 $z=2k$ 的形式，其中 $k$ 是某个整数。一个整数被称为奇数，如果它可以写成 $z=2k+1$ 的形式，其中 $k$ 是某个整数。这个定义是数论中除法算法的直接结果，该算法指出，对于任何整数 $a$ 和任何正整数 $d$，都存在唯一的整数 $q$（商）和 $r$（余数），使得 $a = dq + r$ 且 $0 \le r < d$。

当我们将除数 $d=2$ 应用于除法算法时，我们发现对于任何整数 $x$，都存在唯一的整数 $q$ 和 $r$，使得 $x = 2q + r$ 且 $0 \le r < 2$。这意味着余数 $r$ 唯一可能的值是0或1。

• 如果 $r=0$，那么 $x=2q$。根据定义，$x$ 是一个偶数。
• 如果 $r=1$，那么 $x=2q+1$。根据定义，$x$ 是一个奇数。

这为确定任何整数的奇偶性提供了一个清晰明确的方法：我们只需要找到它除以2的余数。在C++和许多其他编程语言中，模运算符（%）就是用来计算这个余数的。所以，x % 2 将会得到 $x$ 除以2的余数。

负数带来了一个小小的微妙之处。模运算符在处理负操作数时的行为在不同编程语言中可能有所不同。在C++中，a % n 的结果与 a 的符号相同。例如，-5 % 2 的结果是 -1。为了确保一个一致且简单的检查，我的解决方案首先使用 abs(x) 取输入整数 x 的绝对值。这将正整数和负整数都映射到它们的非负对应值。对于任何非负整数，abs(x) % 2 的结果将是0（对于偶数）或1（对于奇数）。这种方法是有效的，因为一个整数 $x$ 的奇偶性与其绝对值 $|x|$ 的奇偶性相同。如果 $x = 2k$，那么 $|x| = |2k| = 2|k|$，是偶数。如果 $x = 2k+1$，那么 $|x|=|2k+1|$。如果 $k \ge 0$, $|x|=2k+1$, 是奇数。如果 $k < 0$，设 $k’ = -k > 0$，则 $x = -2k’+1$。$|x| = |-(2k’-1)| = 2k’-1 = 2(k’-1)+1$，也是奇数。因此，检查 abs(x) % 2 是一种稳健的方法。

我的代码简洁地实现了这个逻辑。它读取一个整数 $x$，计算 abs(x) % 2，并使用一个三元运算符根据结果是1还是0来选择正确的字符串（“odd” 或 “even”）。

其正确性的形式化证明基于上面解释的除法算法。 设 $P(x)$ 为命题“算法正确地确定了整数 $x$ 的奇偶性”。我们需要证明 $\forall x \in \mathbb{Z}, P(x)$。 情况 1: $x$ 是偶数。 根据定义，$\exists k \in \mathbb{Z}$ 使得 $x = 2k$。 那么 $|x| = |2k| = 2|k|$。 代码中的表达式 abs(x) % 2 计算 $|x| \pmod 2$。 $|x| \pmod 2 = (2|k|) \pmod 2 = 0$。 代码检查这个值是否为1。它不是。三元运算符 (0 == 1 ? "odd" : "even") 的值为 “even”。算法正确地输出 $x$ 是偶数。 情况 2: $x$ 是奇数。 根据定义，$\exists k \in \mathbb{Z}$ 使得 $x = 2k+1$。 那么 $|x| = |2k+1|$。 代码中的表达式 abs(x) % 2 计算 $|x| \pmod 2$。 我们知道 $|x| \pmod 2 = ((2k+1) \pmod 2 \text{ 若 } 2k+1 \ge 0) \lor ((-(2k+1)) \pmod 2 \text{ 若 } 2k+1 < 0)$。 在第一种亚情况下，$(2k+1) \pmod 2 = 1$。 在第二种亚情况下，设 $k’ = -k-1$。那么 $-(2k+1) = -2k-1 = -2(k’+1)-1 = 2(-k’-1)+1$。这是 $2q+1$ 的形式，所以它除以2的余数是1。 在所有亚情况下，如果 $x$ 是奇数，则 $|x| \pmod 2 = 1$。 代码检查这个值是否为1。它是。三元运算符 (1 == 1 ? "odd" : "even") 的值为 “odd”。算法正确地输出 $x$ 是奇数。 由于算法对偶数和奇数都正确，所以它对所有整数都正确。

时间和空间复杂度

时间复杂度: 该算法在一个 while 循环内独立处理 $n$ 个测试用例。对于每个测试用例，所做的工作是常数的。它包括：

1. 读取一个整数 (cin)。
2. 调用 abs()，这是一个常数时间操作。
3. 执行模运算 (%)，对于原生整数类型，这是一个常数时间操作。
4. 执行比较 (==)。
5. 打印结果 (cout)。 所有这些步骤都花费少量、固定的时间，我们称之为 $C$。因此，总时间复杂度是测试用例数 $n$ 乘以这个常数时间，即 $O(n)$。

形式上，设 $T(n)$ 为处理 $n$ 个测试用例的总时间。$T(n) = \sum_{i=1}^{n} C_i$，其中 $C_i$ 是处理第 $i$ 个测试用例的常数时间。所以，$T(n) = n \cdot C$。根据大O符号的定义，这是 $O(n)$。

空间复杂度: 该算法只使用了几个变量来存储测试用例的数量 (n) 和当前测试用例的整数 (x)。使用的内存量不依赖于输入数字的大小（在 int 类型的限制内）或测试用例的数量。因此，空间复杂度是常数，即 $O(1)$。

形式上，$S(n) = \text{空间}(n) + \text{空间}(x) = \text{sizeof(int)} + \text{sizeof(int)} = C’$，其中 $C’$ 是一个常数。这是 $O(1)$。

Counting Chocolate (数巧克力)

问题描述

这个问题是经典划分问题的一个变体。我们得到 $n$ 盒巧克力，每盒包含一定数量的巧克力。我们需要确定是否可能将这些巧克力盒分给两个人，John和Sam，使得两人得到的巧克力总数完全相同。所有的巧克力盒都必须被分发。

我的代码

这个问题可以通过检查是否存在一个巧克力盒的子集，其巧克力总数恰好是总数的一半来解决。如果存在这样的子集，我们可以把它给John，剩下的盒子自动会为Sam凑成相同的数量。这是一个子集和问题。考虑到约束较小，我选择了一个递归（回溯）的解决方案来探索所有可能的子集。

// 解决子集和问题的递归函数。
// a: 存储每盒巧克力数量的向量。
// john: John 当前的巧克力总数。
// sam: Sam 当前的巧克力总数。
// sp: 当前递归调用在向量 `a` 中的起始点（索引）。
// target: 每个人的目标总数 (total_sum / 2)。
bool solve(const vector<int>& a, int john, int sam, int sp, int target) {
    // 基本情况：如果我们已经考虑了所有的盒子。
    if(sp == a.size()) {
        // 如果到达终点，只有当某人恰好达到目标时才算找到解。
        // 但下面的检查使得这部分是多余的。
        return false;
    }
    
    // 成功条件：如果任何一人的总数达到了目标。
    if(john == target || sam == target) {
        return true;
    }
    
    // 剪枝：如果任何一人的总数超过了目标，这条路径是无效的。
    if(john > target || sam > target) {
        return false;
    }
    
    // 递归步骤：对索引为 `sp` 的盒子探索两种选择。
    // 选择1：将当前盒子给John。
    // 选择2：将当前盒子给Sam。
    // `||` (或) 意味着如果任何一个选择导致了解决方案，我们就返回 true。
    return solve(a, john + a[sp], sam, sp + 1, target) || solve(a, john, sam + a[sp], sp + 1, target);
}

// 主逻辑
int n;
cin>>n;
vector<int> a = vector<int>(n);
int sum = 0;
for(int i=0; i<n; i++) {
    cin>>a[i];
    sum += a[i];
}

// 一个关键的初始检查：如果巧克力总数是奇数，
// 就不可能将其分成两个相等的整数部分。
if(sum % 2 == 1) {
    cout << "NO";
    return 0;
}

// 调用递归求解器。我们从两人的总数都为0开始，从第一个盒子（索引0）开始，
// 目标是总数的一半。
if(solve(a, 0, 0, 0, sum / 2)) {
    cout << "YES";
} else {
    cout << "NO";
}

我的解法及其正确性

这个问题询问一个给定的整数集合（每盒巧克力的数量）是否可以被划分为两个和相等的子集。设巧克力数量的集合为 $S = {a_1, a_2, \dots, a_n}$。我们正在寻找一个将 $S$ 划分为两个不相交子集 $S_1$ 和 $S_2$ 的方案，使得 $S_1 \cup S_2 = S$, $S_1 \cap S_2 = \emptyset$, 并且 $\sum_{x \in S_1} x = \sum_{y \in S_2} y$。

首先，我们可以得出一个简单但有力的观察。如果两个子集的和相等，比如说都为 $K$，那么所有巧克力的总和 $\sum_{z \in S} z$ 必须是 $K+K = 2K$。这意味着总和必须是一个偶数。如果总和是奇数，从数学上就不可能将其划分为两个相等的整数和。我的算法就从这个检查开始：它计算所有碎片的总和，如果这个和是奇数，它就立即打印 “NO” 并终止。这是一个有效且高效的对整个问题空间的剪枝。

如果总和是偶数，设其为 $2K$。我们的目标现在是找到 $S$ 的一个子集 $S_1 \subseteq S$，其元素之和恰好为 $K$。如果我们能找到这样的子集，那么剩余子集 $S_2 = S \setminus S_1$ 的元素之和将是 $2K - K = K$，满足条件。所以，问题被转化为子集和问题：给定一个整数集合，是否存在一个非空子集，其和等于一个给定的整数 $K$？

子集和问题是经典的NP完全问题。这意味着没有已知的算法可以在多项式时间内对所有输入解决它。然而，对于小输入，我们可以使用像动态规划或者我选择的递归与回溯等方法来解决它。我的solve函数就体现了这种回溯方法。

函数solve(a, john, sam, sp, target)探索了各种可能性。参数代表了决策过程的当前状态：john和sam是两个人的当前和，sp是我们正在考虑的当前盒子的索引，target是期望的和 $K$。

递归的逻辑如下：对于每个盒子a[sp]，我们有两个选择：

1. 把盒子给John。
2. 把盒子给Sam。

函数通过递归调用来探索这两个选择。在第一个调用 solve(a, john + a[sp], sam, sp + 1, target) 中，我们将当前盒子的值加到John的总数上，然后继续考虑下一个盒子（sp + 1）。在第二个调用 solve(a, john, sam + a[sp], sp + 1, target) 中，我们探索了将盒子给Sam的替代方案。||（逻辑或）运算符结合了结果。如果这两个探索分支中的任何一个最终导致了解决方案，函数就返回 true。

递归有几个基本情况和剪枝条件：

• 成功: 如果在任何时候 john == target（或 sam == target），我们已经成功地找到了一个和为目标的子集。我们可以立即返回 true。这个 true 值将沿着调用栈向上传播。
• 剪枝: 如果 john > target 或 sam > target，这意味着当前路径已经超过了目标和。由于所有的巧克力数量都是正数，这个和只会增加。这个分支不可能导致解决方案，所以我们可以通过返回 false 来剪掉它。
• 失败: 如果 sp == a.size()，这意味着我们已经考虑了每一个盒子。如果我们还没有返回 true，这意味着这种特定的盒子分配方式没有导致任何一人的和恰好为 $K$。我们返回 false。

对函数的初始调用是 solve(a, 0, 0, 0, sum/2)。这从两人的和都为零开始，考虑第一个盒子，目标是总和的一半。

这个回溯算法的正确性源于它探索了所有可能划分的整个搜索空间。对每个盒子（a[sp]）是给John还是Sam的决定创建了一个二叉决策树。这棵树的叶子代表了分配 $n$ 个盒子的所有 $2^n$ 种可能方式。算法系统地遍历这棵树。剪枝条件（john > target, sam > target）有助于砍掉那些保证不会导致解决方案的分支，但它们不影响正确性，因为它们只丢弃无效的路径。由于算法探索了每一种有效的可能性，如果存在解决方案，它保证会被找到。如果函数返回 false，则意味着详尽的搜索已经完成，没有找到任何有效的划分。

设 $P(S, K)$ 为寻找 $S$ 中是否存在和为 $K$ 的子集的问题。我的递归函数，我们称之为 $R(i, j_s, s_s)$，其中 $i$ 是要考虑的物品的索引，$j_s, s_s$ 是当前的和，它计算是否可能进行划分。其正确性可以通过对剩余物品数量 $k=n-i$ 进行归纳来正式证明。

• 基础情况 ($k=0$, 即 $i=n$): 没有物品剩下。当且仅当 $j_s=K$ 或 $s_s=K$ 时存在解。我的函数的基本情况覆盖了这一点。
• 归纳假设: 假设 $R(i+1, \dots)$ 正确地解决了从 $i+1$ 开始的子数组的问题。
• 归纳步骤: 为了解决 $R(i, j_s, s_s)$，我们考虑物品 $a_i$。如果(a)我们将 $a_i$ 给John并且剩下的部分有解，即 $R(i+1, j_s+a_i, s_s)$ 为真，或者(b)我们将 $a_i$ 给Sam并且剩下的部分有解，即 $R(i+1, j_s, s_s+a_i)$ 为真，那么就存在解。这正是 return solve(...) || solve(...) 这行代码所做的。根据归纳假设，递归调用是正确的。因此，对步骤 $i$ 的逻辑也是正确的。

时间和空间复杂度

时间复杂度: 递归算法，在其纯粹的形式中，探索一个二叉决策树。对于 $n$ 个盒子中的每一个，都有两种选择。这导致总共有 $2^n$ 种可能的分配方式（决策树的叶子）。在最坏的情况下，算法可能需要探索所有这些方式。在递归的每一步，都完成了常数数量的工作。因此，时间复杂度是指数级的，$O(2^n)$。我加入的剪枝在实践中可以减少搜索空间，但最坏情况下的复杂度仍然是指数级的。考虑到问题约束（$n \le 1000$），这个解决方案会太慢。然而，对于旨在通过这种方法的典型竞赛编程约束， $n$ 通常要小得多（例如，$n \le 20$）。所提供的解决方案的复杂度与问题陈述的约束之间似乎存在不匹配。 假设在实践中约束更宽松或测试用例较弱，这就是所写代码的复杂度。对于所述的约束，需要一个复杂度为 $O(n \cdot \text{sum})$ 的动态规划方法。

形式上，设 $T(i)$ 是解决从索引 $i$ 到 $n-1$ 的子数组问题的时间。 $T(i) = T(i+1) + T(i+1) + C = 2T(i+1) + C$。 这个递推关系展开后得到 $T(0) = O(2^n)$。

空间复杂度: 空间复杂度由递归调用栈的最大深度决定。递归从索引 sp=0 到 sp=n。这意味着调用栈的最大深度将是 $n$。栈上的每个调用都存储其参数和一些局部变量，这需要常数空间。因此，空间复杂度与盒子的数量成正比，即 $O(n)$。

形式上，设 $S(n)$ 是所需的空间。递归深度是 $n$。每个栈帧需要常数空间 $C$。所以，$S(n) = n \cdot C = O(n)$。向量a也占用$O(n)$空间。总空间是$O(n)$。

Maximize Sum of Squares of Digits (最大化数字平方和)

问题描述

这个LeetCode问题要求我们构建一个正整数n，它具有特定数量的数字num和这些数字的特定和sum。在所有满足这两个条件的“好”整数中，我们需要找到那个具有最大可能“分数”的整数，其中分数被定义为该数各位数字的平方和。如果有多个数得到相同的最高分，我们应该返回最大的那个数。如果不存在这样的数，则返回一个空字符串。

我的代码

为了在和固定的情况下最大化数字的平方和，数字应该尽可能地“不均匀”。例如，对于和为10，数字9和1得到的分数是 $9^2+1^2=82$，而5和5得到的是 $5^2+5^2=50$。这表明应该采用贪心策略：使用尽可能多的9。为了使结果数字尽可能大，这些9应该放在最高位。

string Solution::maxSumOfSquares(int num, int sum) {
    // 创建一个输出字符串流，方便构建字符串。
    ostringstream oss = {};

    // 一个基本的不可能性检查：`num` 位数字可能的最大和是 `9 * num`。
    // 如果要求的 `sum` 更大，则无解。
    if(9 * num < sum) {
        return "";
    }

    // `cnt` 跟踪我们已经放置了多少个数字。
    int cnt = 0;
    
    // 贪心地放置尽可能多的 '9'。
    while(sum > 9) {
        oss << 9; // 在我们的数字中添加一个 '9'。
        cnt++;    // 增加数字计数。
        sum -= 9; // 减少我们需要达到的剩余和。
    }
    
    // 循环之后，`sum` 的值在 0 和 9 之间（含）。
    // 这个 `sum` 成为下一个数字。
    oss << sum;
    cnt++;
    
    // 如果我们还没有达到所需的 `num` 位数字，
    // 剩下的数字必须是 '0'。
    while(num - cnt > 0) {
        cnt++;
        oss << 0;
    }

    return oss.str();
}

我的解法及其正确性

这个问题有两个层次的目标：首先，最大化数字的平方和；其次，在那些得分最高的数中，找到最大的一个。约束是固定的数字位数（num）和固定的数字之和（sum）。

设该数的数字为 $d_1, d_2, \dots, d_{\text{num}}$。我们已知：

1. $\sum_{i=1}^{\text{num}} d_i = \text{sum}$
2. 对所有 $i$，$0 \le d_i \le 9$。

我们想要最大化分数 $S = \sum_{i=1}^{\text{num}} d_i^2$。

这里的核心数学洞察是，对于一个固定的和，当数字之间的差距尽可能大时，它们的平方和最大。考虑两个数字 $a$ 和 $b$，它们的和为 $a+b=C$。如果我们将它们改为 $a-1$ 和 $b+1$（假设 $a>0, b<9$），新的和仍然是 $C$，但新的平方和是 $(a-1)^2 + (b+1)^2 = a^2 - 2a + 1 + b^2 + 2b + 1 = (a^2+b^2) + 2(b-a+1)$。如果 $b \ge a$，这个改变会增加平方和。这种值的“分散”会增加平方和。我们可以推广这个结论：要最大化 $\sum d_i^2$ 同时满足 $\sum d_i = C$，我们应该使一些 $d_i$ 尽可能大。

这个洞察导致了一个贪心策略。为了最大化分数，我们应该使数字尽可能大。可能的最大数字是9。因此，我们的策略应该是使用尽可能多的9。每使用一个9，我们就满足了所需sum中的9，并用掉了一个可用的num位数。

我的算法实现了这个贪心选择。它重复地将数字'9’附加到结果中，每次从剩余的sum中减去9，直到剩余的sum为9或更小。此时，剩余的sum（介于0和9之间）必须用作下一个数字。放置这个数字后，如果我们还没有用完所有的num个位数，剩下的位数必须用'0’填充，因为使用任何其他数字都会改变和。

现在，让我们考虑第二个目标：在得分最高的数中返回最大的那个。如果一个数的最高位（左边的数字）更大，那么这个数就更大。我的贪心方法首先放置9，然后是次大的数字，最后是0，自然地按降序构造了数字。这确保了可能的最大数字（9）占据了最重要的位置，从而创造了该数字集合的字典序最大和数值最大的数。

例如，如果 num = 3 且 sum = 18，我的算法会生成9，然后9，然后剩余的和是0。数字是 {9, 9, 0}。构造的数是 “990”。这个数有最大的可能分数（$9^2+9^2+0^2 = 162$），并且是这些数字的最大可能排列。

还有一个可行性的初步检查：if (9 * num < sum)。num位数字可能的最大和是在所有数字都是9时实现的，其和为 $9 \times \text{num}$。如果要求的sum超过这个值，就不可能形成这样的数，所以函数正确地返回一个空字符串。问题陈述也暗示需要一个下界检查。正整数的数字和必须至少为1，这已由约束条件覆盖。

这个贪心算法的正确性的形式化证明依赖于一个“交换论证”。 设我们的贪心解法产生了一个数字序列 $G = (g_1, g_2, \dots, g_n)$，其中 $n=\text{num}$。设 $O = (o_1, o_2, \dots, o_n)$ 是任何最优解的有效数字序列。我们想证明 $G$ 的分数至少和 $O$ 的分数一样高，并且如果分数相等，$G$ 构成的数至少和 $O$ 构成的数一样大。 假设为了分数分析，两个序列中的数字都按降序排序：$g_1’ \ge g_2’ \ge \dots$ 和 $o_1’ \ge o_2’ \ge \dots$。我们的贪心算法产生字典序最大的数字序列，以最大化平方和。让我们找到第一个索引 $i$ 使得 $g_i’ \neq o_i’$。 由于我们的算法首先选择最大的可能数字，必然有 $g_i’ > o_i’$。因为两个序列的和相同，必须存在某个其他索引 $j > i$ 使得 $o_j’ > g_j’$。 考虑数字 ${o_i’, o_j’}$。我们有 $o_i’ < g_i’ \le 9$ 和 $o_j’ > g_j’ \ge 0$。 让我们通过将对 $(o_i’, o_j’)$ 改为 $(o_i’+1, o_j’-1)$ 来修改最优解 $O$。数字的和保持不变。新的平方和是 $(o_i’+1)^2 + (o_j’-1)^2 = o_i’^2 + 2o_i’ + 1 + o_j’^2 - 2o_j’ + 1 = (o_i’^2 + o_j’^2) + 2(o_i’ - o_j’ + 1)$。由于 $o_i’ < o_j’$（因为序列是排序的），$o_i’ - o_j’ + 1 \le 0$。这个变换可能不会增加分数。 让我们重新评估核心属性。函数 $f(x)=x^2$ 是一个凸函数。对于任何满足 $\sum d_i = C$ 的一组数 $d_i$，当值在其定义域的边界时，和 $\sum d_i^2$ 最大化。所以，我们应该使用尽可能多的9和0。我选择使用9的贪心选择是正确的。它使一些数字尽可能大（9），迫使其他数字尽可能小（0，和一个余数数字）。这个配置最大化了平方和。任何其他配置都可以通过重复地从一个数字 $d_i < 9$ 中取1并加到另一个数字 $d_j < 9$ 上来转换成我们的贪心配置，以使其中一个更大。这种“拆东墙补西墙”的策略增加了平方和。 所以，贪心算法产生的数字集合对于分数来说是最优的。我的算法还按降序排列这些数字，根据定义，这会产生最大的数。因此，该算法是正确的。

时间和空间复杂度

时间复杂度: 算法的运行时间由数字位数 num 和 sum 决定。

1. while(sum > 9) 循环最多运行 sum / 9 次。在每次迭代中，它执行常数次操作（追加、递减、递增）。所以这部分是 $O(\text{sum})$。
2. while(num - cnt > 0) 循环最多运行 num 次。这部分是 $O(\text{num})$。 因此，总时间复杂度是 $O(\text{sum} + \text{num})$。

形式上，设 $T(\text{num}, \text{sum})$ 为运行时间。 第一个循环运行 $k_1 = \lfloor (\text{sum}-1)/9 \rfloor$ 次。 第二个循环运行 $k_2 = \text{num} - k_1 - 1$ 次。 总工作量与 $k_1 + k_2 = \text{num}-1$ 成正比。然而，构建字符串可能需要更长的时间。如果我们假设向 ostringstream 追加是摊销常数时间，那么这个逻辑成立。如果它与字符串长度成正比，它将是从1到num的长度之和，导致 $O(\text{num}^2)$。但是 ostringstream 是经过优化的。一个更简单的分析将总追加次数限制为num次。循环次数受sum和num限制。所以 $O(\text{sum} + \text{num})$ 是一个安全的上界。

空间复杂度: 使用的空间主要用于正在构建的输出字符串。最终的字符串将有 num 位数字。ostringstream 将使用与数字位数成正比的空间。因此，空间复杂度是 $O(\text{num})$。

形式上，$S(\text{num}, \text{sum})$ 是 ostringstream 的空间。其最终大小为 num 个字符。所以 $S(\text{num}, \text{sum}) = O(\text{num})$。

Minimum Operations to Transform Array (转换数组的最小操作)

问题描述

这个问题被呈现为一个名为 minOperations 的函数，它接受两个整数向量nums1和nums2。根据代码判断，这似乎是一个自定义的转换问题。目标是计算一个“成本”或“操作数”。计算涉及一个基础成本，即nums1和nums2之间元素级绝对差的总和，以及一个与特殊值extra（即nums2的最后一个元素）相关的附加成本。

我的代码

我编写的代码根据一个特定的公式计算一个值。它首先通过对所有 abs(nums1[i] - nums2[i]) 差值求和来计算一个基础步数。然后，它确定一个与extra值相关的附加成本。它在nums1和nums2中找到与extra“最接近”的元素。似乎需要一个额外的操作，其成本取决于extra是否落在任何(nums1[i], nums2[i])对之间。

long long Solution::minOperations(vector<int> &nums1, vector<int> &nums2) {
    // 'extra' 值被定义为第二个数组的最后一个元素。
    int extra          = nums2.back();
    long long step_cnt = 0;
    
    // `nearest` 将存储最接近 `extra` 的元素的索引。
    int nearest        = 0;
    // `nearest_d` 存储到目前为止找到的最小距离。
    int nearest_d      = INT_MAX;
    // `flag` 如果 `extra` 被任何范围 [nums1[i], nums2[i]] "覆盖"，则为 true。
    bool flag          = false;
    // `status` 指示最近的元素是在 nums1 (1) 中还是在 nums2 (2) 中找到的。
    int status         = 1;
    
    // 同时遍历两个数组。
    for(int i = 0; i < nums1.size(); i++) {
        // 在两个数组中找到最接近 `extra` 的元素。
        if(abs(nums1[i] - extra) < nearest_d) {
            nearest   = i;
            status    = 1;
            nearest_d = abs(nums1[i] - extra);
        }
        if(abs(nums2[i] - extra) < nearest_d) {
            nearest   = i;
            status    = 2;
            nearest_d = abs(nums2[i] - extra);
        }
        
        // 检查 `extra` 是否位于由 nums1[i] 和 nums2[i] 定义的闭区间内。
        if((nums1[i] <= extra && extra <= nums2[i]) || (nums2[i] <= extra && extra <= nums1[i])) {
            flag = true;
        }
        
        // 累加基础成本，即元素级差值的总和。
        step_cnt += abs(nums1[i] - nums2[i]);
    }
    
    // 根据 `flag` 和 `status` 确定最终成本。
    if(flag) {
        // 如果 `extra` 被覆盖，成本是基础成本加 1。
        return step_cnt + 1;
    } else if(status == 1) {
        // 如果未被覆盖，且最近的元素在 nums1 中，则加上 1 和该距离。
        return step_cnt + 1 + abs(nums1[nearest] - extra);
    } else { // status == 2
        // 如果未被覆盖，且最近的元素在 nums2 中，则加上 1 和该距离。
        return step_cnt + 1 + abs(nums2[nearest] - extra);
    }
}

我的解法及其正确性

这个问题似乎定义了一个独特的成本函数，用于将nums1转换为nums2，并特别考虑了一个extra值。我的解决方案细致地实现了这个成本的计算，这是由潜在的（未见的）问题逻辑定义的。让我们分解成本的组成部分并合理化其逻辑。

问题的核心似乎是将nums1转换为nums2。衡量两个数组之间“距离”或“转换成本”的一种常见方法是绝对差之和，也称为曼哈顿距离或差向量的$L_1$范数。代码行step_cnt += abs(nums1[i] - nums2[i]);计算了这个基础成本。这可以解释为使每个nums1[i]等于nums2[i]所需的最小增量/减量操作数。

复杂性来自于extra = nums2.back()的特殊角色。最终成本不仅仅是step_cnt。还有一个附加部分。我的算法逻辑表明这是一个到extra值的“连接成本”。

代码遍历数组以确定关于extra的两件事：

1. 覆盖性 (flag): 它检查extra是否包含在任何区间[min(nums1[i], nums2[i]), max(nums1[i], nums2[i])]之内。如果是，布尔值flag被设置为true。这表明，如果extra可以由nums1[i]和nums2[i]之间的某个值“形成”，那么连接成本是最小的。
2. 邻近性 (nearest, nearest_d, status): 同时，它在nums1和nums2两个数组中找到数值上最接近extra的元素。它记录了索引（nearest）、最小距离（nearest_d）以及该元素来自哪个数组（status）。这似乎是在“覆盖”条件不满足时计算连接成本的备用计划。

最终的return语句综合了这些发现：

• if (flag): 如果extra被至少一个区间“覆盖”，总成本是step_cnt + 1。这可以解释为：基础转换成本，加上一个“激活”与extra连接的单一操作，这个操作很便宜，因为它已经在范围内。
• else: 如果extra未被覆盖，成本就更高。它是step_cnt + 1 + nearest_d。这意味着：基础转换成本，加上一个激活操作，再加上一个等于到extra的最小距离的附加成本。这个附加成本代表了将最近的现有值“拉向”extra以建立连接所需的努力。

该解决方案的正确性取决于它是对问题定义的特定自定义成本函数的正确实现。假设问题就是计算这个确切的成本，那么我的算法是正确的，因为它系统地计算了公式的每个组成部分。

• 它正确地累加了绝对差之和。
• 它正确地遍历了所有元素以检查覆盖条件并适当地更新flag。
• 它正确地维护了到extra的最小距离以及实现该最小距离的元素的位置。
• 它使用了一个条件结构，根据计算出的flag和status正确地应用了最终的公式。

让我们形式化算法计算的成本函数 $C$。 设 $S = \sum_{i=0}^{n-1} |nums1_i - nums2_i|$。 设 $E = nums2_{n-1}$。 设“覆盖”谓词为 $P = \exists i \in [0, n-1] \text{ s.t. } (E \ge \min(nums1_i, nums2_i)) \land (E \le \max(nums1_i, nums2_i))$。 设 $d_{min} = \min_{i \in [0, n-1]} (\min(|nums1_i - E|, |nums2_i - E|))$。 算法计算的成本 $C$ 为： $C = \begin{cases} S + 1 & \text{如果 } P \text{ 为真} \ S + 1 + d_{min} & \text{如果 } P \text{ 为假} \end{cases}$ 我的代码是这个函数的一个直接且正确的实现。循环确保检查了所有的 $i$ 以确定存在条件 $P$，并找到了最小距离 $d_{min}$。最后的if-else块正确地应用了分段函数的两种情况。

时间和空间复杂度

时间复杂度: 该算法主要由一个从i = 0到nums1.size() - 1遍历数组的for循环主导。设 $n$ 是数组的大小。循环运行 $n$ 次。 在循环内部，所有操作都是常数时间的：

• 绝对值计算。
• 比较。
• 赋值。
• 算术运算。 因此，循环内部完成的工作是$O(1)$。总时间复杂度是 $n$ 乘以这个常数工作量，即 $O(n)$。

形式上，设 $T(n)$ 为运行时间。 $T(n) = \sum_{i=0}^{n-1} C$，其中 $C$ 是循环内部操作的常数成本。 $T(n) = n \cdot C = O(n)$。

空间复杂度: 该算法使用了少数几个变量（extra, step_cnt, nearest, nearest_d, flag, status）来存储中间值。使用的内存量是常数的，不依赖于输入数组的大小。因此，空间复杂度是$O(1)$（不包括输入数组本身的空间）。

，其中 $C’$ 是一个常数。这是$O(1)$。