DSA PA4 Report

DSA PA4 Report

PA4-1 Circuit解题报告

算法构思与实现要点

本题涉及大量 64 位长的 01 串自高相低的逐位比对问题，考虑用字典树（Trie）存储和处理。字典树在接受字符串的行为上类似一个自动机，同时能够通过节点记录字符串相关的更多信息，实现对字符串基于公共前缀的压缩存储以及查询、删除等功能。由于本题中字符集为 ${0,1}$，字典树为二叉树，树中每个节点维护一个 child 数组，记录两个孩子节点的位置，向左走（child[0]）代表着接受字符0，向右走（child[1]）代表接受字符1。本题中，为了查询目标 01 串的编号，还需要在节点中存储当前经过该节点的编号最小的串编号。

由于在存在多个答案时需要输出最小编号，故考虑先将所有01串读入一个二维 bool 数组中，然后在字典树中逆序插入01串，使小编号覆盖先前插入的大编号。

由于编号 $i$ 的串查询范围限定于 $[\max(0,i-k-1), i) \cup (i,\min(i+k+1,n-1)]$，随着 $i$ 的变化区间范围也单调变化，可以对维护的字典树中执行动态的插入、查询、删除操作。具体而言，在逆序插入到第 $i (0 \le i < n)$ 号 01 串后，检查 $i+k+1$ 是否 $<n$，如果是的话，说明第 $i+k+1$ 号查询范围的 01 串已全部插入字典树中，即刻进行查询，保存答案；然后检查第 $i+2k+2$ 号元素是否 $<n$，如果是的话，由于后续查询范围都不再包含该串，即刻从字典树中删除。完成全部插入后，从 $k$ 号串开始继续逆序执行查询、删除操作。这样，**在每次查询 $i$ 号 01 串时，字典树中恰好存储的是 $i$ 号串查询范围内的 01 串**（这时树中也包含它自身，但由于 $k > 0$ 且查询目标串是与自身异或值最大的编号最小的串，故仅在 $i=0$ 且第0、1号串完全相同时可能出现自身与自身组合的情况，在结束后进行一次特判即可）。

具体的字典树操作过程如下：

  1. 插入：从根节点开始自高向低逐位读入第 $i$ 号 01 串，遇 0 则转向左孩子，遇 1 则转向右孩子（孩子为空则创建节点），同时将沿途节点记录的编号都更新为 $i$。
  2. 查询：从根节点开始自高向低逐位读取第 $i$ 号 01 串，由于位高低次序保证，可以采用贪心策略，尽可能寻找与第 $i$ 号 01 串每一位相异的串，只要另一侧孩子节点存在即转向另一侧的节点，即：遇 0 则转向右孩子，遇 1 则转向右孩子；否则转向同一侧孩子节点，这样得到的串与 $i$ 号串异或值最大。
  3. 删除：从根节点开始自高向低逐位读取第 $i$ 号 01 串，沿着插入路径，如果经过节点上记录的最小编号 $\ge i$（实则至多 $=i$），则删去其父节点对其位置的记录，相当于删去了这个孩子。

完成过程中遇到的问题与解决过程

  1. 对于可能的边界情况需要进行特判：仅在 $i=0$ 且第0、1号串完全相同时可能出现第 0 号串自身与自身组合的情况，完成全部查询操作后检查答案数组，若 ans[0]==0 修改为 ans[0]=1 即可。
  2. 本题空间限制较紧，如果每个节点用指针存储两个孩子节点的位置，同时存储一个 int 类型的编号信息，由于结构体的字节对齐要求，每个节点需要占用 24B 空间，存储 $n \le 5 \times 10^5$ 个 64 位 01 串占用空间上界将达到 $64 \times 5 \times 10^5 \times 24$B = 768 MB，存在超出空间限制的可能，因此改用大数组统一存储字典树节点，通过 int 类型数组下标索引孩子节点位置，将每个节点占用空间缩减到 12B，避免了可能出现的MLE问题，同时避免了指针寻址，访问孩子的方式更加 cache-friendly，在时间上也有明显的常系数优化。

复杂度估算

  • 时间复杂度：共 $n$ 个 64 位 01 串，每个串至多需要执行插入、查询和删除操作各一次，每个操作访问的字典树高均为 64，故总时间复杂度为 $O(3 \times 64n)$，其中 $n \le 5 \times 10^5$，故总基本操作数次数大约为 $10^8$ 量级。

  • 空间复杂度：字典树中存储的节点数至多为 $64n$，故渐进空间复杂度为 $O(n)$。但本题在空间限制上存在卡常行为，需要仔细分析最坏情况下可能的空间开销：

    1. 字典树节点：改为数组存储后每个节点占用 12B 空间，总共空间开销不超过 $64 \times 5 \times 10^5 \times 12$B = 384 MB；
    2. 输入的 01 串：通过二维 bool 数组存储，总空间开销不超过 $64 \times 5 \times 10^5 \times 1$B = 32 MB；
    3. 答案：由于答案时逆序求得的，因此需要用一个 int 数组额外存储，总空间开销不超过 $5 \times 10^5 \times 4$B = 2 MB；
      综上，总空间开销上限约为 418 MB < 512 MB。

PA4-3 kth解题报告

算法构思与实现要点

要找出 $n^3$ 种组合中第 $k$ 小的组合，一个基本的想法是建立一个小顶堆，依次弹出堆顶最小元素，弹出 $k$ 次即可得到第 $k$ 小的元素。

首先面临的问题是如何建堆。直接将 $n^3$ 个元素建堆至少需要 $O(n^3)$ 时间，在给定数据范围内显然是不可接受的，且由于 $k \ll n^3$ 不必要地维护了大量无用信息。结合人工确定答案的经验，更明智的做法是首先通过预处理，“定二议一”，通过固定两个编号将第三个数组按编号排好序，确定出一个“偏序关系”：
$$ (a’[i’], b’[j’], c’[l’]) \ge (a’[i], b’[j], c’[k]) \quad
\forall i’ \ge i, j’ \ge j, k’ \ge k $$
再依次插入“第 $i (1 \le i < \le k)$ 小元素的可能取值”。具体而言，设 $a’,b’,c’$ 分别存储 $a, b, c$ 中元素从小到大排序后对应的下标（如 $a[a’[0]]$ 代表 $a$ 中最小值），那么和最小的组合只可能是 $(a’[0], b’[0], c’[0])$，和第二小的组合只可能是 $$(a’[1], b’[0], c’[0]), (a’[0], b’[1], c’[0]), (a’[0], b’[0], c’[1])$$ 三者之一。用归纳法可以证明：设和第 $r$ 小的组合是 $(a’[i], b’[j], c’[k])$，那么它将第 $r$ 个被弹出堆，同时将 $$(a’[i+1], b’[j], c’[k]), (a’[i], b’[j+1], c’[k]), (a’[i], b’[j], c’[k+1])$$ $(i+1, j+1, k+1 \le n)$压入堆中，和第 $r+1$ 小的组合只可能来自当前堆中的组合。

但是这样做有可能会重复压入相同元素。一种解决的办法是，规定各个方向压入的次序：只有当 $j = k = 1$ 时压入 $a’,b’,c’$ 方向相邻三个元素，否则当 $k = 1$ 时压入 $b’,c’$ 方向两个相邻元素，其他情况只压入 $c’$ 方向相邻元素。

为方便说明这样做的正确性，不妨考虑二维情形：假设本题只有两个数组，当 $j = 1$ 时压入 $a’,b’$ 方向相邻两个元素，否则只压入 $b’$ 方向一个元素。因此，当 $(a’[i],b’[j]), i < n, j > 1$ 出堆时，$(a’[i+1],b’[1])$ 一定曾经已经入过堆。若 $(a’[i+1],b’[j])$ 曾经入过堆，不必重复入堆；若 $(a’[i+1],b’[j])$ 未曾入过堆，则一定 $\exist 1\le t < j,(a’[i+1],b’[t])$ 仍在堆中。由偏序关系:$$(a’[i+1],b’[t]) < (a’[i+1],b’[j])$$$(a’[i+1],b’[t])$ 一定将先于 $(a’[i+1],b’[j])$ 出堆，故 $(a’[i+1],b’[j])$ 不可能是下一个出堆元素，因此当前不必压入堆中。同理可推广到三维情形，这样就可以有效避免重复入堆。

具体实现上，需要维护一个 $Heap$ 类，实现压入、弹出元素时的上滤、下滤操作，算法非常经典，不再赘述。唯一需要提到的一点是，在我的 $Heap$ 类中特别实现了一个 pushFromTop 方法，表示从顶部压入并下滤，同时覆盖堆顶元素，相当于完成一次弹出与压入的组合操作。当需要压入多个元素时，将最小者从堆顶压入（下滤），其他的从堆底压入（上滤），可在常系数上减少元素交换次数。

完成过程中遇到的问题与解决过程

  1. 注意不要误用连等！在C++中，表达式 a == b == c 与 a == b && b == c 完全不同！不妨假设其中三个变量都是 int 型，前者相当于 (a == b) == c，会先计算 a == b，返回 true 或者 false。由于 c 是 int 型，因此会发生隐式类型转换， true 或者 false 会被转换为 int 型的 1 或者 0，最后表达式就变成 1 == c 或者 0 == c。故本题中 if(j == k == 1) 的语义与 if(j == k) 无异，正确的写法应该是 if(j == 1 && k == 1)。
  2. 注意在下滤时要分类讨论清楚，碰到已经就位的情况要及时 break 退出。

复杂度估算

  • 时间复杂度：

    1. 对三个数组内部元素的预处理排序：$O(3n \log n)$
    2. 在堆中弹出 $k$ 个元素，至多压入 $3k$ 个元素，由于采用了 pushFromTop 方法，每次弹出压入动态过程至多包含3次上滤/下滤操作，堆中至多包含 $2k$ 个元素，总共经历 $k$ 次动态操作，故总时间复杂度上限为：$O(3k\log 2k)$
    3. 综上，渐进复杂度为 $O(n\log n + k\log k)$

  • 空间复杂度：

    1. 排序后维护 $a’,b’,c’$ 数组：$O(3n)$
    2. 堆中元素不超过 $2k$：$O(2k)$
    3. 综上，渐进复杂度为 $O(n+k)$