《数据结构》课程 PA3 报告
内含以下题目的实验报告：
- CST2021F 3-1 Circuit
- CST2021F 3-3 kth
- CST2021F 3-5 Prefix
- CST2021F 3-7 Sort
这里不提供任何解题代码，仅将解题的白盒报告归档处理。
本博文仅做参考使用，任何可能影响您查重结果的行为请您后果自负！
| Problem | White Box (20%) | Black Box (80%) |
|---|---|---|
| CST2021F 3-1 Circuit (25%) | 100 | [100] -1 |
| CST2021F 3-3 kth (25%) | 100 | [100] -1 |
| CST2021F 3-5 Prefix (25%) | 100 | [100] -1 |
| CST2021F 3-7 Sort (25%) | 100 | [100] -1 |
CST2021F 3-1 Circuit
[关键词] Trie 树
方案设计
$\forall i \in [0, n)$，需要一种支持以下操作的数据结构：
(1) 持有 $[\max(i-k-1, 0), \min(i+k+1, n-1)]$ 中所有的元件的输出信息；
(2) 可以查询这些信息中满足与 $data[i]$ 异或值最大的 $data[j]$ 的 $j$，其中 $i \ne j$。
(3) 在考虑 $i$ 结束，转向考虑 $i+1$ 的时候，可以快速地删除 $data[i-k-1]$ 的信息，加入 $data[(i+1)+k+1]$ 的信息。
而字典树，恰恰就能满足我们上述的需求，下面对其进行详细介绍。
字典树：规则
字典树的结点分非叶结点和叶结点两种。事实上，我们可以用考虑有限转移自动机（DFA）的方式来考虑字典树。
非叶结点记录了所有终态经过它的串的个数，以及通过输入一个字符 $a\in\Sigma$，可以转移到的下一个非叶结点或叶结点的位置。
叶结点记录了所有以它为终态的串的个数，同时维护了一个列表来按次序记录所有以该叶结点为终态的串的 ID。
我们定义，一个结点输入一个字符 $a\in \Sigma$ 后对应的结点存在，当且仅当该结点是非叶结点，同时该非叶结点可以通过字符 $a$ 转移到位置 $t$，且结点 $t$ 接受的终态经过 $t$ 或是以 $t$ 为终态的串的个数非零。
字典树：初始化
从这小节的讨论开始，我们只讨论 $\Sigma=\{0, 1\}$ 的情况。
字典树默认只有一个根节点，接受空串 $\epsilon$，终态经过它的串的个数为 $0$，这里我们不将该根节点视为叶结点。
$\Sigma = \{0,1\}$ 的字典树的非叶结点只需记录其经过 $0$ 转移和 $1$ 转移后的到达结点，这里我们使用二叉树的记号，分别记作其左孩子和右孩子。
字典树：插入
考虑我们将插入 $64$ 位整数 $data[i]$。
我们从根节点出发，逐一考虑去接受该串的字符，遇 $0$ 则转向其左孩子，遇 $1$ 则转向其右孩子，若对应的孩子的位置不存在（注意这里与上述结点的存在不同，结点存在需要位置存在，且该位置的记录串数非零）则创建。同时我们将沿途所有的非叶结点的“终态经过它的串的个数”自增，终态叶结点的“以它为终态的串的个数”自增。最后，我们在终态叶结点的串列表中将该串的 ID $i$ 插入。在本题中由于我们考虑的窗口永远是从左向右滑动，我们可以保证插入的 ID $i$ 一定是在列表的末尾，故我们只需插入到列表末尾即可。
字典树：删除
考虑我们将删除 $64$ 位整数 $data[i]$，同时我们断言 $data[i]$ 在此前一定被插入到树中。
我们从根节点出发，逐一考虑去接受该串的字符，遇 $0$ 则转向其左孩子，遇 $1$ 则转向其右孩子。我们将沿途所有的非叶结点的“终态经过它的串的个数”自减，终态叶结点的“以它为终态的串的个数”自减。最后，我们在终态叶结点的串列表中将该串的 ID $i$ 移除。在本题中由于我们考虑的窗口永远是从左向右滑动，我们可以保证删除的 ID $i$ 一定是在列表的首位，故我们只需删除列表首位即可。
字典树：查询
考虑我们将查询 $j$，使得 $i \ne j$ 且 $data[j]$ 与 $64$ 位整数 $data[i]$ 的异或值最大，其中 $j \in [\max(i-k-1, 0), \min(i+k+1, n-1)]$。
由贪心策略，如果我们每步均朝向异或值最大的方向走，即遇 $0$ 走 $1$，遇 $1$ 走 $0$（如果可能的话，这种可能性由对应的结点存在蕴含），我们最终得到的异或值便一定是最大的。
也就是说，我们的查询过程可以概述如下：
从根节点出发，逐一去考虑接受该串的字符，遇 $0$ 若右孩子存在则转向右孩子，不然转向左孩子；遇 $1$ 若左孩子存在则转向左孩子，不然转向右孩子。这样不断进行下去势必会达到一个终态，而这个我们要做的便是输出这个终态叶结点的接受串 ID 列表中第一个 $id$（满足 $id \ne i$）。
过程记录
输入有毒。输入有毒。输入有毒。最初一版使用 getchar() 读取 $64$ 位字符串，结果满满的是 WA，一个点都不给过。初步推断可能是输入文件以 \r\n 结尾而程序只考虑了以 \n 结尾的情况。换用 scanf() 后便解决了问题，而这个问题竟然喜提 PA3 中 Debug 时间最久的问题。
解决过程大致是首先为了控制变量，排除算法实现过程的具体问题，做了以下两个操作：
(1) 撰写了对拍器 check.py（见附 1），但是本地的数据怎么测都是 AC。
(2) 撰写了 Trivial.cpp（见附 2），读入部分没变（事实上，最初我认为是后续字典树处理写出了问题，于是想写个最简单的版本交上去看下测试数据的规模），使用最平凡的 $O(nk)$ 的算法处理问题，最终发现还是爆零。目光转向读入部分，改用 scanf 后 Trivial 算法拿到了 40/50（自然会喜提 TLE），然后是将新的读入复制回 main.cpp，前后两次拿到了 50/50, 90/90, 完结撒花。
复杂度分析
从时间上来看，每个结点最多被插入一次，查询一次，删除一次，这些操作的时间复杂度均是正比于树高 $h=O(64)=O(1)$，而对于 $n$ 个结点，我们有时间复杂度是 $O(n)$。
字典树的每个结点可能对应 $64$ 位整数的位表示中的一个字符。也就是说，最多有 $O(64n)=O(n)$ 量级的结点个数。而这些结点有小部分是可以复用的。具体来说，根据鸽巢原理，我们设读入 $k$ 个字符后，才会出现 $2^k>n$，解得 $k\ge19$。也就是说，我们可以考虑一种极端的情况，树深度 $depth \le 19$ 时为满树，而树深度 $depth \ge 20$ 时为单链，这种情况下最多的结点个数为 $\sum_{i=0}^{19}2^i+(64-19)n\approx 2.410^7=24M$。
我们的叶结点共有 $O(n)$ 个，同时每个叶节点都需要维护 1 个列表，因此列表的个数也是 $O(n)$ 个，列表的元素的总个数也是 $O(n)$。综上，空间复杂度为 $O(n)$。
而这题还是有卡常的嫌疑的，也就是说虽然是 $O(n)$ 量级，但是空间复杂度还是可能有可能会超限，具体分析如下：（$n=5*10^5$）
- 非叶结点，24M * 12Byte = 288M.
- 列表条目，0.5M * 12Byte = 6M.
- 叶结点，0.5M * 20Byte = 10M.
- $64$ 位整数的数据，0.5M * 8Byte = 4M.
- 合计 308M < 512M.
附录
附 1: check.py
import io
import time
import datetime
import random
import subprocess
import numpy as np
IN = ''
OUT = ''
class Judger:
def generateInputData(self):
global IN, OUT
IN = ''
OUT = ''
n = 10
k = 2
IN = f'{n} {k}\n'
dataList = [random.randint(0, 2**64-1) for i in range(n)]
rawList = [bin(data)[2:].zfill(64) for data in dataList]
print(dataList)
print(rawList)
for raw in rawList:
IN += f'{raw}\n'
for index, data in enumerate(dataList):
left = index - k - 1
if left < 0:
left = 0
right = index + k + 1
if right > n-1:
right = n-1
currMaxIndex = -999
currMaxValue = -999
for i in range(left, right+1):
if (i == index):
continue
if (dataList[i] ^ data) > currMaxValue:
currMaxIndex = i
currMaxValue = (dataList[i] ^ data)
OUT += f'{currMaxIndex}\n'
return IN
def getAnswer(self):
global OUT
return OUT.strip()
def judge(self, name, judgeAns=True):
print('\n\nCompiling...')
try:
subprocess.check_output(['g++', '-O2', '-std=c++14', '-w', f'{name}', '-o', 'main'])
except subprocess.CalledProcessError as e:
return 'CE'
print('Generating testing data...')
data = self.generateInputData()
print('Running...')
try:
time1 = time.time()
cppout = subprocess.check_output(['./main'], input=bytes(data, 'utf-8'), timeout=2.0)
cppout = cppout.decode('utf-8').strip()
time2 = time.time()
except subprocess.TimeoutExpired:
f = open(f'check-{datetime.datetime.now().strftime("%Y-%m-%d-%H-%M-%S")}.log', 'w+', encoding='utf-8')
f.write(f"Time Limit Exceeded\n")
f.write("-------------IN--------------\n")
f.write(data + '\n')
f.close()
return f'Time Limit Exceeded (2.000s)'
except subprocess.CalledProcessError as e:
f = open(f'check-{datetime.datetime.now().strftime("%Y-%m-%d-%H-%M-%S")}.log', 'w+', encoding='utf-8')
f.write(f"Runtime Error (signal {e.returncode})\n")
f.write("-------------IN--------------\n")
f.write(data + '\n')
f.close()
return f'Runtime Error (Signal {e.returncode})'
if judgeAns:
# print(cppout)
# print("↑ cppout ↓ ans")
print('Generating testing answer...')
ans = self.getAnswer()
# print(ans)
print('Judging...')
try:
cppout_ = cppout.split('\n')
ans_ = ans.split('\n')
if (len(cppout_) != len(ans_)):
raise BaseException(-1)
for i in range(len(cppout_)):
if (cppout_[i].strip() != ans_[i].strip()):
raise BaseException(i)
except BaseException as e:
f = open(f'check-{datetime.datetime.now().strftime("%Y-%m-%d-%H-%M-%S")}.log', 'w+', encoding='utf-8')
f.write(f"Wrong Answer on line {e}\n")
f.write("-------------IN--------------\n")
f.write(data + '\n')
f.write("-------------CPPOUT--------------\n")
f.write(cppout + '\n')
f.write("-------------ANS--------------\n")
f.write(ans + '\n')
f.close()
return 'Wrong Answer'
return f'Accepted ({round(time2 - time1, 3)}s)'
else:
return f'Program exited successfully ({round(time2 - time1, 4)}s)'
j = Judger()
for i in range(1000):
print(j.judge('trivial.cpp', judgeAns=True))
附 2: Trivial.cpp
#define ull unsigned long long
#include <cstdio>
int n, k;
ull data[500001] = {0};
int main() {
scanf("%d %d\n", &n, &k);
for (int i = 1; i <= n; ++i) {
char c = getchar();
while (c == '0' || c == '1') {
data[i] <<= 1;
data[i] += c - '0';
c = getchar();
}
}
for(int i = 1; i <= n; ++i) {
int l = i-k-1;
if(l < 1) l = 1;
int r = i + k + 1;
if(r > n) r = n;
ull currMax = 0;
ull currMaxIndex = l != i ? l : (l + 1);
for(int T = l; T <= r; ++T) {
if(T == i) {continue;}
if ((data[T]^data[i])>currMax) {
currMax = data[T] ^ data[i];
currMaxIndex = T;
}
}
printf("%d", currMaxIndex-1);
if(i != n) puts("");
}
return 0;
}CST2021F 3-3 kth
[关键词] 堆，偏序关系，归并排序
方案设计
偏序关系
首先我们可以回忆出针对一维数组寻找第 $k$ 大元素问题的解决方案。我们可以将原数组直接建小顶堆后，第 $k$ 次 pop 出的元素即为所求，时间复杂度为 $O(n+k*\log n)$。而稍微再仔细考虑我们的建堆过程，实际上我们是将这一维数组中的所有元素之间建立起一种偏序关系。没错，偏序关系，这也是接下来我们讨论的重点。
二维情况
再来考虑针对两个数组的情况。首先我们可以固定某个 $X$ 元素，将 $Y$ 元素的顺序排序；然后固定某个 $Y$ 元素，将 $X$ 元素进行排序。这里排序的意思是说，找到一个序列 $(new_1, new_2, \cdots, new_n)$，使得 $X_{new_i} = sorted(X)[i]$。之后我们便可以记 $X[i]:=X_{new_i}=sorted(X)[i]$.
针对两个数组的情况，我们记 $(i,j)$ 表示值 $X[i]+Y[j]$。可以对于 $(i_1, j_1)$ 与 $(i_2, j_2)$，我们有：
- $(i_1,j_1) \le (i_2, j_2)$, if $i_1 \le i_2$ and $j_1 \le j_2$.
由于我们的内存有限，我们能放在堆中的元素是有限的。所以我们要想出一种组织这些元素的方式，使得每个元素能且仅能出现在小顶堆中一次，也就是说，我们要建立一种新的偏序关系 $M$，使得 $\forall (i,j)$, 集合 $\{(x,y)\ |\ (x,y) \le_M (i,j) \ \and\ (x,y)\ne(i,j) \}$ 有最大元 $(m,n)$，即当且仅当 $(m,n)$ 出堆，$(i,j)$ 才能入堆，且这种偏序关系满足如果 $(x,y) \le_M(i,j)$，那么 $(x,y) \le (i,j)$。
对于数组有两个维度的情况，我们可以构造偏序关系 $M$ 如下图：
对于某个顶点 $(i,j)$，可以验证从比它小的元素指向它的边的入度均为 $1$（根节点除外），此即保证了每个元素都能入堆（当在新的偏序关系下，比它小的元素的极大值出堆，即当与它直接相连但比它小的那个顶点出堆，注意这里的“小”均为在新的偏序关系下），且每个元素仅能入堆一次。
于是我们便可以首先将 $(1,1)$ 推入小顶堆中，然后每 pop 一次，将其出边对应的结点推入堆中。这样 pop $k$ 次后得到的 $(x,y)$ 即为所求。
三维情况
在三个数组的情况，我们采用与上述类似的记号，而建立的偏序关系如下图：
于是我们便可以首先将 $(1,1,1)$ 推入小顶堆中，然后每 pop 一次，将其出边对应的结点推入堆中。这样 pop $k$ 次后得到的 $(x,y,z)$ 即为所求。
过程记录
首先对原有的 X，Y，Z 数组进行归并排序，具体来说是找到上述的 $X$
编写
Index类模拟上述定义的索引 tuple。可以简单地通过重载运算符来实现两个Index之间的比较（调用交互库函数）。- 注意按照上述拓扑关系建立
Index之间的新偏序关系，以保证所有顶点能且仅能被推入堆中一次。
复杂度分析
从时间上来说，归并排序所需时间复杂度为 $O(n \log n)$。注意到上述所有结点最多有 3 条出边，即运行 $k$ 次上述操作后，可以保证堆中的结点数不超过 $3*k=O(k)$。对于这样的堆，运行 $k$ 次 pop，$O(3k)$ 次 insert，我们有时间复杂度为 $O(k \log k)$。于是总体时间复杂度为 $O(n \log n + k \log k)$。
对原数组进行排序的归并排序数组辅助空间为 $O(n)$，堆开辟的空间大小为 $O(3k)=O(k)$。总空间复杂度为 $O(n+k)$。
CST2021F 3-5 Prefix
[关键词] KMP next[] 表，动态规划
方案设计
关键概念定义
这里我们采用一种与题目和课堂讲义上不同的字符串及 next[] 表表示方式，具体介绍如下：
- 对于长度为 $n$ 的串 $S$，记之为 $S[1…n]$. (Index starts from 1)
- 记 $next[j]$ 表示 $S[1…j]$ 中最大自匹配的真前缀和真后缀的串长，也就是说，与讲义中偏重 Pattern String 下一次移动到的位置不同，我们更加侧重的是这个长度值。举个例子：
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| raw[i] | * | a | a | b | a | a | b |
| next[i] | -1 | 0 | 1 | 0 | 1 | 2 | 3 |
可以证明，这种 next[] 表与讲义上的 next[] 表只偏差了一个 offset。
next[] 表的构建
根据我们的定义，$next[j]$ 代表 $S[1…j]$ 中最大自匹配的真前缀和真后缀的串长，而这个真前缀便是 $S[1…next[j]]$。
于是，在我们采用递推的方式计算 $next[j+1]$ 时，我们要寻找的是 $S[1…j+1]$ 中最大自匹配的真前缀和真后缀的串长。
我们已知 $S[1…t]$ 与 $S[j-t+1… j]$ 是匹配的，这里 $t \in \{next[j], next[next[j]], next[next[next[j]]] \cdots\} =: T_j$。
于是，我们便可以逐个考虑序列 $T_j$ 中的元素：
- 如果 $S[j+1]$ 与 $S[t+1]$ 相等，我们便找到了 $S[1…j+1]$ 的一个最大的自匹配的真前缀与真后缀，此即 $next[j+1] \leftarrow t+1$.
- 不然，我们转而考虑这个序列的下一个元素。
由于这个序列最后必然收敛于通配符 *，算法必定终止。
动态规划求前缀出现次数
考虑串 aabaabaab，定义 $dp[j]$ 表示 $S[1…j]$ 的所有真前缀与真后缀相匹配的次数。可得下表：
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| raw[i] | * | a | a | b | a | a | b | a | a | b |
| next[i] | -1 | 0 | 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| dp[i] | - | 0 | 1 | 0 | 1 | 2 | 1 | 2 | 3 | 2 |
归纳可证明：
最后我们的答案还需要考虑整个子串自匹配的情况，即 $S[1…j]$ 在 $S[1…n]$ 中出现过一次，$\forall j \in [1, n]$.
于是答案便是 $n + \sum_{i=1}^ndp[i]$.
过程记录
- 通过引入通配符
*这个哨兵结点，可以有效地进行递推。 - 需要用
long long来存储答案数值。 - 同时记录 $raw, next, dp$ 会导致内存溢出，因为 $(1+4+8)*20M = 260M > 256M.$
- 首先想到的解决方案是，由于答案的大小不会超过 $(20M)^2=4e14$，而 $\log_2(4*10^{14})=2+\frac {14} {\lg2} \approx 49$，使用 $56$ 个 bit 便可以将其储存。
- 于是我们可以撰写自己的
int56类，在 get 与 set 对应整数的时候将long long通过位运算拆成char,short,int三部分（7 Byte）。 - 经过此种优化之后，内存用量为 $240M$，便有了通过的可能。
- 于是我们可以撰写自己的
但是转而一想，数据结构并不是汇编程序设计。- 事实上我们按照上述解题思路不难得出，我们是先算出了 $next$ 数组中的所有值，然后根据 $next$ 数组的值去递推 $dp$ 数组。
- 事实上，我们可以考虑只建立一个 $next$ 数组，为
long long类型，首先在其中算出所有 $next_j$，然后根据这个 $next_j$ 计算 $dp_i$，实行就地覆盖的方法，并不会影响答案的结果。
- 首先想到的解决方案是，由于答案的大小不会超过 $(20M)^2=4e14$，而 $\log_2(4*10^{14})=2+\frac {14} {\lg2} \approx 49$，使用 $56$ 个 bit 便可以将其储存。
复杂度分析
KMP 的 next[] 表构建过程时间复杂度为 $O(n)$，之后根据 $next$ 递推 $dp$ 与累加求和的复杂度均为 $O(n)$。于是时间复杂度为 $O(n)$。
空间上，使用 $raw$ 与 $next$ 数组均为 $O(n)$ 大小，最大内存使用量为 $20M*9=180M<256M$。
CST2021F 3-7 Sort
[关键词] 归并排序， 四路归并
方案设计
首先由题目测试数据给出的 $n$ 和 $k$ 的大小关系我们可以果断摒弃掉最坏情况为 $O(n^2)$ 的冒泡排序，选择排序等等算法。这些算法即使在一次能比较的数的个数上进行了优化，这也只是常数级别的，并不能撼动其数量级的地位。
目光自然转向了复杂度为 $O(n \log n)$ 的快速排序和归并排序上。我们要做的，便是利用比较器一次可以比较三个数的性质，对这些复杂度已经达到理论下界的算法进行常数级别的优化。
这里由于归并排序的稳定性，所以首选的是归并排序。首先我们自然可以想到的是，模仿二路归并的具体实现，如果比较器一次可以比较三个数，那么我们可以尝试实现三路归并，这样需要求解的递推方程为 $Cmp(n) = 3*Cmp(\frac n 3) + n$，这是基于每经过一次比较，我们就可以确定三路中的最小元素，并将其从三路中取出，放置于数组的对应位置。
但是如果我们代入 $n=3^k$ 对该方程求解，我们得出 $a_k=(k+1)3^k$，其中 $a_k=Cmp(3^k)$，此即 $Cmp(n) \sim n\log_3n$。代入 $n=10^6$ 我们有 $Cmp(n) \approx 7.6*10^7$。不能满足我们对 $limit$ 的要求。
于是想法转移到能否更加 exploit 比较器返回的结果中包含的信息。具体来说，在三路归并中，每次比较都能返回 $a<b<c$，我们只运用到了 $a<b$, $a<c$ 这两个部分，并没有利用到 $c$ 是三者的最大值这么一个条件。而一旦 $c$ 是最大值，由于有 $b<c$，可以保证在下次的比较过程中，$c$ 一定不是三者中的最小值。这竟然退化成了 $b,c,d$ 比较，实际上我们用比较器只比较了 $b, d$ 的二路归并的情况。
于是再进一步，我们考虑可以使用四路归并，便可以尽力 exploit 比较器的返回信息。具体来说，和上述想法相似，对于待合并数组 $a,b,c,d$，一旦我们在 $a,b,c$ 中比较得到 $a<b<c$，在下一次比较选择最小值时，我们便可以忽略掉 $c$，只比较 $next(a), b,d$，其正确性由 $b<c$，即 $c$ 一定不是最小值保证。
这样需要求解的递推方程为 $Cmp(n) = 4Cmp(\frac n 4) + n$，此即 $Cmp(n) \sim n\log_4n$。代入 $n=10^6$ 我们有 $Cmp(n) \approx 9.97*10^6<limit_n$。
过程记录
四路归并的具体实现过程中，递归过程与二路归并类似，而重点在于四路合并的过程。具体来说，我们可以先在 $a,b,c,d$ 四个数组中选取前三个数组 $a,b,c$ 做一次比较，将三者中的最大值的数组信息记录在一个全局变量 nextBypass 中。
然后我们便可以进入循环，每次比较除了该全局变量 nextBypass 记录的数组的剩下三个数组的首元素的相对大小信息，然后将三者中的最大值所在的数组信息更新给全局变量 nextBypass，而将最小值写入最终的合并后数组中，直到四路中某个数组耗竭，退化成上述平凡的三路归并的情况，进而退化成更加平凡的二路归并的情况，进而退化成更加更加平凡的数组拷贝的情况。
复杂度分析
四路归并中，时间复杂度方程与 $Cmp(n) = 4*Cmp(\frac n 4) + n$ 同构，即 $T(n) = O(n \log_4 n)$。而我们在上文也证明了比较次数 $Cmp(n) = O(n \log_4 n)$。
在空间上，主要开辟的是 $a,b,c,d$ 四个数组的辅助空间，空间复杂度为 $O(n)$。