《数据结构》课程 PA2 报告

内含以下题目的实验报告：

• CST2021F 2-1 Build
• CST2021F 2-2 Not Found
• CST2021F 2-4-2 Kidd
• CST2021F 2-6 Hacker

这里不提供任何解题代码，仅将解题的白盒报告归档处理。

本博文仅做参考使用，任何可能影响您查重结果的行为请您后果自负！

Problem	White Box (20%)	Black Box (80%)
CST2021F 2-1 Build (25%)	100	[100] -1
CST2021F 2-2 Not Found (25%)	95	[100] -1
CST2021F 2-4-2 Kidd (25%)	95	[100] -1
CST2021F 2-6 Hacker (25%)	100	[100] -2

CST2021F 2-1 NotFound

​ [关键词] 父亲-长子-兄弟法的多叉树表示，List

方案设计

结点

每个结点需要维护以下信息。

• parent，指向父亲的指针
• firstChild，指向长子的指针
• nextSibling，指向下一个兄弟的指针
• prevSibling，指向前一个兄弟的指针
• height，子树高度
• size，子树规模
• suffixMaxHeight，以自己为基点，自己及自己之后的兄弟的高度的最大值
• childLength，孩子个数
• childPushed，在建树时用到的临时变量

其中 suffixMaxHeight 的维护是基于复杂度分析的考量。每次更新时我们需保证复杂度不大于 $O(cost)$，$cost$ 中包含了结点的 $Rank$、也就是说，为了避免遍历所有孩子结点，我们可以考虑维护后续高度的最大值，然后只更新长子到本结点这些兄弟的高度最大值即可。父亲的高度自然是长子的 suffixMaxHeight + 1。这样就保证了单步更新高度复杂度在 $O(Rank)$，进而整体更新高度 $O(cost)$​ 范围内。

建树

我们在遍历初始树的时候按照以下原则，效力从上到下递减：

• 如果一个结点的 childPushed 为 false，那么将其该字段设为 true，并将其压入栈中，将其所有孩子按照长子到末子的顺序压入栈中。
• 如果一个结点是叶节点，那么直接将其预处理。
  • $height \leftarrow 0$​
  • $size \leftarrow 1$
  • $suffixMaxHeight \leftarrow \max(suffixMaxHeight_{nextSibling?}, height)$​​
  • $parent?.height \leftarrow parent?.height+1 $
• 不然我们得出该结点一定有长子，且其所有孩子一定先于其被预处理。
  • $height \leftarrow firstChild.suffixMaxHeight +1$
  • $size \leftarrow size + 1$​
  • $suffixMaxHeight \leftarrow \max(suffixMaxHeight_{nextSibling?}, height)$
  • $parent?.height \leftarrow parent?.height+1 $
• 其中 $?$ 表示对其不存在的情况做特判。

删除子树

分待删除子树是不是长子两种情况考虑。

• 改变子树局部的拓扑结构
• 沿“祖父”链更新子树规模
• 沿“结点$\rightarrow$长子$\rightarrow$父亲$\rightarrow\cdots$”链更新 height 与 suffixMaxHeight

插入子树

分待插入子树是不是长子两种情况考虑。

• 改变子树局部的拓扑结构
• 沿“祖父”链更新子树规模
• 沿“结点$\rightarrow$长子$\rightarrow$父亲$\rightarrow\cdots$”链更新 height 与 suffixMaxHeight

查询

根据我们维护的 size 和 height，找到对应节点输出相应数据即可。

过程记录

目的位置的节点表示为移除源子树后的节点表示。

题没读完就下手，对拍写的都是错的，痛苦 Debug 一天，然后不及 5min 读一遍题有效。

具体来说，提交记录交了 5 页，assert 出某个测试数据要在某个我认为的“叶节点”的第 1 个位置插入元素。猜测拓扑结构的查询或是更新出了问题，但小数据可以 AC，感觉大部分移动都是没问题的。于是感觉有种特殊情况处理的不对。大不解，重新读题…

事实上理解题意之后也直接可以手写一组小数据 Hack 掉自己的程序。

本题唯一有思想价值的是 suffixMaxHeight 的维护。既然不能在更新子树时遍历所有孩子，而复杂度要求我们可以在 $Rank$ 内完成子树的维护，于是我们就想到这样一种类似于区间最值的维护手段，每次更新只更新 $[0, Rank]$​ 的数据即可。

复杂度分析

在建树时每个结点至多被压入栈中两次，预处理可以视为 $O(1)$ 时间，因而建树的时间复杂度为 $O(n)$。

按照上面对 suffixMaxHeight 维护的分析，所有单步操作 $i$ 的复杂度被 $O(cost_i)$ 所控制，因而整体 $m$ 次操作的复杂度被 $O(cost)$ 所控制。

总体来看时间复杂度为 $O(n+cost)$。

空间复杂度方面，只有结点列表和预处理栈大规模使用了空间，复杂度为 $O(n)$。

CST2021F 2-2 NotFound

归档时注：该方法极有可能在优化不足的情况下被卡常，网络学堂已有人提交对应测例，本人并未对其进行测试。

​ [关键词] Bitmap, BitMask

方案设计

存储数据

考虑使用类似于 Bitmap 的结构，来逐位进行存储数据。

一个 unsigned char 为 8 个 Bit，将长度为 $2^{24}$​ 长的 0/1 串存储需要 $2^{24}/8=2^{21}$​ 个，内存占用 $2$ MB。

答案长度

我们考虑答案长度的上界 $M$，即假设至多需要 $k$​​ 的长度才能得出答案。

那么字符串中所有长度为 $k$ 的连续字串共有 $n-k+1$ 个。

而 $k$ 的长度的所有可能情况有 $2^k$ 种。

于是我们令 $n-k+1<2^k$，即 $2^k+k>n+1$ 时，即可充分地保证答案存在，于是我们得出 $k \ge log_2 n$ 即可。

事实上，我们证明了答案的最大长度不超过 $log_2 n$​，因此我们不妨取 $M=24$​.

于是我们可以考虑枚举答案，最多不超过 $\sum_{k=1}^{24} 2^{k}$ 种可能情况。

判断答案

对输入字符串进行枚举一次，得出所有不满足答案要求的定长子串的时间为 $O(n)$​。而我们知道，针对不同的答案长度 $k\in[1, M]$​，封顶估计我们只需要枚举字符串 $Mn = 24n$​​​​ 次，便可以得到所有子串的情况。而我们只需要反选出所有可能的答案序列中，最早的一个即可。

而想要实现反选的效果，我们用 Ans 数组（unsigned char, $2^{21}$​）来记录某种情况是否已经出现。比如在枚举答案长度为 3，输入子串为 101 时，便将 Ans 数组的第 5 个 Bit 置为 1，表示该种情况存在。最终我们只需要输出第一个为 0 的 Bit 的 index 的二进制表示即可。

同时，一旦我们检测到某个答案长度下的输入数据的子串数目与可能的最多子串数目相等，便可以剪枝优化。

案例分析

具体来说，我们考虑下面一个例子。

对样例数据 $10100011$，我们考虑：

[AnsLen = 1]

输入数据的一个小 Window	Ans 数组	输入数据在本长度下的子串数目
1	01	1
0	11	2

[AnsLen = 2]

输入数据的一个小 Window	Ans 数组	输入数据在本长度下的子串数目
10	0010	1
01	0110	2
10	0110	2
00	1110	3
00	1110	3
01	1110	3
11	1111	4

[AnsLen = 3]

输入数据的一个小 Window	Ans 数组	输入数据在本长度下的子串数目
101	00000100	1
010	00100100	2
100	00101100	3
000	10101100	4
001	11101100	5
011	11111100	6

我们最终判断得到 $6 \ne 2^{3} = 8$​，于是在此时寻找第一个为 0 的元素 $6$ 并输出其在长度为 3 意义下的二进制表示 $110$，即为答案。

过程记录

我们使用“对拍”验证程序的运行时间，具体来说我们生成长度为 $2^{24}$ 的随机测试数据，然后让程序多次实验取最坏情况。

经测试，在随机数据上程序运行的最坏时间为 $0.57s$​​​​。

事实上打开了 O2 优化开关之后运行的平均最坏时间为 $0.2s$。

在报告的最后会附上对拍代码。

复杂度分析

在空间上，使用了两个大小为 $2^{21}$ 的 unsigned char 数组，不超过 $4$ M。

在时间上，复杂度主要为对输入子串做连续子串截取与最终的反向寻找答案，二者最坏情况为 $O(n)$，都最多进行 $M$ 次，故最终复杂度为 $O(Mn)=O(n\log n)$​。

附：Judger 代码

# Judger by c7w
import io
import time
import datetime
import random
import subprocess
import numpy as np

class Judger:
    def generateInputData(self):
        IN = ''
        for i in range(2**24):
            IN += f'{random.randint(0, 1)}'
        IN += '\n'
        return IN

    def getAnswer(self):
        OUT = ''
        return OUT.strip()
    
    def judge(self, name, judgeAns=True):
        print('\n\nCompiling...')
        try:
            subprocess.check_output(['g++', 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: # Do not judge answer
            return f'Program exited ({round(time2 - time1, 3)}s)'
        

j = Judger()
for i in range(10):
    print(j.judge('main.cpp', False))

CST2021F 2-4-2 Kidd

​ [关键词] Segment Tree

方案设计

建树

首先读入数据，将所有操作预存储。

将所有 $[i, j]$​ 区间考虑为 $(i-1, j]$​ 的形式，并且将所有的 $(p_i, p_j]$​ 区间合并端点后，排序去重得到分点集合 $\{sep_0, sep_1, sep_2, \cdots, sep_{pos}\}$​​。

这样，我们便可以将 $(sep_{i-1}, sep_{i}]$​​​​​ 中所有的点在接下来的考虑中等而视之，我们不妨将其翻转次数和记作 $a_{i+1}$​。同时我们计算 $(sep_{i-1}, sep_{i}]$​​​​ 中所含有点的个数，来作为最终更新翻转次数和的时候该区间对应的权重 $weight$​。

我们维护两个数组 $sum$ 与 $lazy$​ 表示对应的区间的翻转总次数和以及没有下放的翻转次数。

图为一颗普通的线段树的样子，其中绿色标记为其在数组中对应的存储下标。

然后我们就可以用这种数据结构去维护翻转次数和以及懒惰标记了，更新和查询操作如下。

更新

首先，我们要把待更新区间通过在有序分点集合中二分查找，找到其对应的最左区间 $a_l$ 和最右区间 $a_r$。

现在问题转化成我们要更新 $[a_l, a_r]$​ 中的所有元素。通过分治的方法我们可以将待更新区间分割成如图所示的若干个极大区间 $[a_{i_0}, a_{i_1}], \cdots, [a_{i_k}, a_{i_{k+1}}]$​，然后对其做一次“更新”操作，其中“更新”操作定义如下：

• 将自身和自身的所有祖先的 $sum$ 加上自己的权值，表示对应区间翻转次数增加这个权值。
• 将自身的“懒惰”标记 $lazy$ 增加 1，表示有一次翻转并没有通知自己的子节点。

查询

首先，我们要把待查询区间通过在有序分点集合中二分查找，找到其对应的最左区间 $a_l$ 和最右区间 $a_r$​。

现在问题转化成我们要查找 $[a_l, a_r]$​ 中的所有元素。通过分治的方法我们可以将待查找区间分割成如图所示的若干个极大区间 $[a_{i_0}, a_{i_1}], \cdots, [a_{i_k}, a_{i_{k+1}}]$​，然后对其做一次“查找”操作，其中“查找”操作定义如下：

• 在“分割”成极大子区间的过程中，如果一个含有懒惰标记的区间 $a_i$​​ 被分割，那么将该懒惰标记释放，同时其两个子区间 $a_j, a_k$​​ 要更新其 $sum$​​ 值和 $lazy$ 值：
  • $sum_j \leftarrow sum_j + weight_j*lazy_i$​
  • $sum_k \leftarrow sum_k + weight_k*lazy_i$​
  • $lazy_j \leftarrow lazy_j + lazy_i$
  • $lazy_k \leftarrow lazy_k + lazy_i$
  • 事实上，这是对之前更新时并未更新子区间的翻转次数和的“延时效应”的激活。
• 返回各个极大子区间的 $sum$ 值之和。

过程记录

理清思路是很重要的。

在首次划分区间的时候，并没有考虑 $(0, sep_0]$ 和 $(sep_{pos-1}, n]$ 这两个区段，导致算法运行时出现错误。

经过考虑不妨补充上这两个区间，即使 $sep_0 = 0$ 或是 $sep_{pos-1} = n$​，将其作为哨兵结点即可，在有序分点集合的二分查找中也不会命中它们。

复杂度分析

设分点总数为 $M$​​，可知 $M \le 2m$​​​，即 $M = O(m)$。

建树时排序 $O(Mlog M)$​，去重 $O(M)$​。在求权重时调用了递归方程对每个区间都求了权重，$T(M) = 2T(\frac M 2) +O(1)$，解递归方程复杂度 $O(M)$​。

更新时，首先在有序分点集合进行二分查找，复杂度 $O(logM)$​。因为有了懒惰标记，所以更新 $sum$​ 值的节点的个数被树高控制，即更新时复杂度为 $O(logM)$​。于是单次更新的复杂度为 $O((logM)^2)$​。

而在查询时，首先在有序分点集合进行二分查找，复杂度 $O(logM)$。因为极大区间存储了其对应子区间的 $sum$ 值总和，所以我们不需要遍历每一个子节点，与查询相关的极大子区间个数也被树高控制。于是单次查询的复杂度为 $O((logM)^2)$​。

由此我们可以得出，本算法的时间复杂度为 $O(MlogMlogM)$​​，即 $O(m\log m\log m)$.

而在空间上，我们使用的分点集合大小为 $M$​​​​，线段树对应的每个 $sum$​​​, $lazy$​​​, $weight$​​​ 的元素个数为 $O(m)$，于是我们得出空间复杂度为 $O(m)$​​​.

CST2021F 2-6 Hacker

​ [关键词] Hash, CRC32, Bitmask

方案设计

密码表示

首先我们建立密码可能存在的字符与整数的对应关系。

• ‘0’ ~ ‘9’ 映射至 0 ~ 9
• ‘t’, ‘s’, ‘i’, ‘n’, ‘g’, ‘h’, ‘u’, ‘a’ 映射至 10 ~ 17

用字符数组来存储不方便我们进行管理，由于每个密码长度不超过八位，我们做以下规定：

• 使用 long long ($64$ Bit) 来表示一个密码
• 密码的后 $4$ 个 Bit 表示密码长度.
• 密码的后 $[5k+4, 5k+9)$​ 个 Bit 表示倒数第 $k$ 个字符。

比如，密码 222 可以表示为 $0b0000200002000020011$

我们可以通过方便的移位操作和与操作来取出对应位数的字符。

将密码组织成密码结点的形式，存储其 salted(CRC32) 值，当前密码以及下一个同样 key 的密码结点的地址。

特别的，如果一个 CRC32 值已冲突，我们将密码记为 -1，即 $11111 \cdots 1111$。​

散列表

我们的取模值 M 取为 5999993.

我们的 HashTable 取长度为 M，待插入其中的元素 key 为 $salted(CRC32) \mod M$​​，值为对应的密码结点地址。

初始化

首先我们需要把 $\bigcup_{i=1}^{5} \Sigma^i$​​ 的所有字符串加入 HashTable 中。

根据 CRC32 函数的流拼接性质，我们使用队列来实现类似广度优先搜索的操作。

具体来说，首先向散列表插入 $\Sigma$ 中的所有元素，并将其入队。如果队列中还有剩余元素，那么首先向散列表插入将其与 $\Sigma$ 中所有元素拼接的结果，如果这些结果长度小于 5，那么继续将其入队。

散列表的动态操作

查询

首先将对应的 CRC32 值加盐，称为 salted(CRC32)。

查询 salted(CRC32) % M 单元，返回第一个 CRC32 值为 salted(CRC32) 的密码结点。

如果没查询到返回 nullptr。

插入

首先将 CRC32 值加盐，称之为 salted(CRC32)。

对散列表查询 CRC32 % M 单元，如果返回 nullptr 直接插入到该单元。

如果发现了一个 salted(CRC32)，那么直接将其 pass 设置为 -1.

历史记录维护

历史记录使用一维长度为 8 的滚动数组维护，需要存储其累积至今的 CRC32 值和 pass 值。

根据 CRC32 的流性质在有新的成功记录时直接拼接即可。

过程记录

《当你看代码逻辑三小时而不知出什么问题.jpeg》

• 初版代码忘了在历史记录插入 HashTable 时加盐（样例都跑不过 本地解决）
• 第一次九成测内存空间没算对。密码结点最多数目为 $2M$（Init）+ $3M$​（历史记录插入）

复杂度分析

首先我们分析 HashTable 的查询与插入过程。

查询 HashTable，由于 HashTable 的长度大于实际最终可能的密码结点总数，因此分摊而言查询复杂度为 $O(1)$。

插入 HashTable 包含了一个查询过程和插入过程。因此时间也是 $O(1)$。

初始处理 1 ~ 5 位的初始字符串集合需要处理 $18 + 18^2 + 18^3 + 18^4 + 18^5 = 210^6$ 的数据，因此需要 $O(T)$​ 的时间，这里 $T=210^6$。

而后续处理的过程中，对于每个 CRC32 值，我们均需查询，如果成功还需维护历史记录，但是这些操作均在 $O(1)$ 时间内能够完成，因此整体来看时间复杂度为 $O(n)$。

于是整体的时间复杂度为 $O(T+n)$，其中 $T=2*10^6$，为初始遍历序列的势。

空间复杂度而言，我们每个密码结点需要 24 Byte（考虑到对齐要求），$245M=120M$​。而 HashTable 只需要储存密码结点的地址，$86M=48M$。遍历初始序列的队列大小为 $0.1M$，可以忽略。这样我们就整体在 $O(n)$​ 的空间复杂度内，且常数符合题目要求的情况下，完成了题目。