这是DSA 2023 Spring PA 4的Circuit的解题报告，内容涉及Trie树。
A.所使用数据结构与算法的构思、原理和实现要点
所使用的数据结构：
二叉树（更准确地说，是Trie树） 列表
算法构思：
1 二叉树的每条边代表这一位输出0或1，每个点代表一些元件的集合（或者理解为一个指定的元件输出序列前缀），从父节点走向左孩子表示该元件在这一位的输出是0，走向右孩子代表这一位输出是1。
2 从前向后依次处理每个元件，当有新元件符合间隔要求而需要被考虑的时候，将它加入二叉树中。反之，当一个元件距离很远，将其从二叉树中删除。
3 二叉树中每个节点应该维护一个值用以表示有多少个元件拥有自己所表示的序列的前缀。
4 二叉树中可能同时存在两个相同的元件，所以叶子结点需要连接向一个列表，用以储存所有输出序列为自己所表示的序列的元件序号。
实现要点：
1 二叉树使用结构体数组实现，列表也使用数组实现。为了用数组实现列表，我们实现一个二维数组，第一行用于储存信息，第二行用于储存列表下一项在数组中的位置。
2 使用贪心算法，尽量寻找与当前元件不同输出的元件，以此确保异或值最大。也正是由于这一操作，我们不用在每次查询一个元件的最佳组合时删除当前元件自身。
3 列表保存头地址和尾地址，确保插入和删除均为O(1)操作。
B.完成过程中遇到的问题，排除问题的主要过程、使用的方法和技巧，以及参考资料
问题1：程序需要的空间太大，无法满足限制条件
二叉树的构建需要太多节点，如果按每个元件都会带来63个新节点计算的话，如果每个二叉树节点都要存储左右孩子、链表开头、元件数目的话，二叉树和列表就将消耗 $3.1510^744+510^524=5.08*10^8Byte$，已经接近空间上限。而且，在实际测试中，过大的空间开销也会拖慢程序运行。所以，最终选择将二叉树的内部节点和叶子结点分开用两个数组实现，这样，内部节点不需要保留用不到的列表地址，叶子结点不需要保存用不到的左右孩子，而且叶子结点数目可以大幅减少至n个。
问题2：九成测两个测试点Wrong Answer
经过检查，发现是如下代码出现bug：
1 | //如果当前链表有多于一个元素，则删去最早写入的元素（链表头端元素） |
在这里，我们先把链表当前位置的尾指针指向下一个位置的尾指针，又将指向当前链表位置的指针指向了当前位置尾指针的位置，相当于让指向当前链表位置的指针跳过了两个元素，多删除了一个。考虑到被删除元素在数组中的为知不会再使用，不需要调整被删除元素的尾指针，因此直接删掉上面两行代码的第一行即可。
参考资料
除了习题课PPT，没有参考其他资料。
C.时间和空间复杂度的估算
时间复杂度
二叉树每次查询、插入和删除，长度固定为64，复杂度为O(1)。对n个元件进行查询，复杂度为O(n)。
空间复杂度
程序代码中使用的是定长数组。从实际有效使用的空间角度分析，二叉树空间占用不超过O(n)，因为每个元件最多引入63个二叉树的新节点。而列表的空间占用，由于无论是否重复都会放入列表，所以为O(n)。综合来看，空间复杂度为O(n)。