这是DSA 2023 Spring PA 3的Histroy的解题报告，内容是使用散列，比较简单。
A.所使用数据结构与算法的构思、原理和实现要点
所使用的数据结构：
散列：存储的数据是所有的学生的上一次查询次数
算法构思：
1 读取数据，用异或处理得到真实id
2 利用散列函数和冲突处理策略寻址
3 更新散列中储存的信息
实现要点：
1 使用除余法作为散列函数
2 使用线性试探作为冲突处理策略
3 为了取得更好效果，散列表的 table_size 设置为 1000003 。
4 使用结构体数组作为散列。
B.完成过程中遇到的问题，排除问题的主要过程、使用的方法和技巧，以及参考资料
问题：第一次尝试时，所有的插入数据均被认为是未曾出现过的
经过观察源代码，发现是由于判断散列当前位置是由被占用的过程中出现了问题。为了简化，直接在散列所储存的结构体中加入一个标记是否被占用的 bool 变量。
参考资料
未参考各种资料。
C.时间和空间复杂度的估算
时间复杂度
插入操作和查询操作类似，每次操作，不冲突时，时间复杂度为O(1)，冲突时，最坏情况为O(n)。
考虑到总共需要进行n次插入和查询操作，总体复杂度最优为O(n)，最坏为O(n^2)。
从正常情况考虑的话，设装填因子为x，则线性试探的平均成功长度为0.5*(1+1/(1-x))。本题中最多有1000000个输入，而我设置的散列表大小为2000003，所以装填因子不会大于0.5，即平均成功长度不会大于1.5。基于这一点，可以认为n次操作的总体复杂度为O(n)。
空间复杂度
由于使用的是定长结构体数组，所以开辟的空间是常数值。
实际使用的空间大小与输入的提交记录个数成线性关系，O(n)。