《数据结构》课程 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)$。