DSA PA2 REPORT
2-1 Risk Report
算法构思
本题的核心是如何构造一个类似于“队列”的数据结构，数据遵循先进先出的原则，且又能在O(1)时间内找到最大值。针对本题，我发现从$i−m_i$到$i-1$并不是每一个数字都有意义，实际上，只需要存储这样一个子序列就可以：该子序列B满足子列的每一项都严格大于所有原数组中项数大于这一项的元素，而每当 i 加一，只需要根据$m_i$删掉B的前几项，并从子序列的最后开始向前找到大于A[i-1]的项并删掉其后面的所有元素，这样就可以得到新的满足要求的B。
在搜索满足最大确诊病例在[0,p),[p,q)问题上，我采取了维护前缀和的方法，即les_num[i]表示最大确诊病例数小于 i 的总天数
时间和空间复杂度的估算
时间复杂度：注意到维护B序列的两个指针lo和hi一定最多只会扫过一个一个元素一次，所以维护B序列的时间复杂度为$O(n)$，此外维护前缀和数组的时间复杂度为$O(m) \, m=2*10^{6}$，查询时间复杂度为$O(T)$。因此总复杂度为$O(m+n+T)$
空间复杂度：程序开了三个长为n的数组，分别存储每日病例数，B数组每一项对应的病例数和B数组元素在原数组的下标。此外还开了两个长为m的数组存储每日前$i-m_i$日最大病例数和前缀和。总空间复杂度为$O(n+m)$
CST 2-2 Report
算法构思
本题的实现思路主要参考教材中中缀表达式的算法。大体思想为：从左向右依次扫描一个每个字符，如果读到的是操作数则加入操作数栈，如果是操作符则需要比较和操作符栈栈顶的优先级关系，如果栈顶优先级更高则计算栈中两个操作数（本题中除括号外全部都是双目运算符），如果当前操作符优先级更高则入栈，如果相当则去掉栈顶操作符，并读取下一个位置的字符（对应去括号和\0匹配）。
为了完成本题我构造了两个类，Stack和Poly，前者用数组模拟了一个简单的栈结构，后者建立了一个多项式类实现其各项系数的存储以及加减乘次方运算。
具体实现时本题和教材也有一些不同：
- 本题中操作数是一位位读入，且含有x，因此我设置了
tmp_num变量来记录多位数，并且考虑x的情况。只有当读入下一个字符时才能知道之前的操作数读入是否结束，此时才将此前的操作数转化成Poly对象后入栈，这也是和教材不太一样的地方。 - 乘号省略。根据题目描述，乘号省略包括“)(，n(，x(，nx，)x”（n表示数字）这5种情况，所以每次读入字符时会判断一下这个字符和其前一个字符是否满足乘号省略的条件，如果满足则相当于先要让乘法和栈顶操作符比较，运算或入栈后再次读取当前字符（我使用一个
mul变量来记录“读入当前字符时是否已经考虑乘号被省略”，从而确定是补乘号还是真正读取当前字符） - 取模运算，每次运算后都要对1000000007取模，对于负数x，我采用$(x+1000000007)\mod1000000007$的方法
一些算法优化：
- 在读入字符串时，考虑到\^1这个运算本身对运算结果没有影响，为了避免不必要的次方运算，省略了所有\^1
- 每当构造一个多项式类时，都会用一个
_degree变量来记录这个多项式类实例的最高位幂次，这样在乘法运算时不需要循环64*64次而只需要循环_degree1*_degree2次
时间和空间复杂度的估算
时间复杂度：程序时间复杂度主要来自三部分：字符串读入和出入栈计算。字符串读入显然是$O(n)$的，下面针对出入栈计算的时间复杂度进行分析。
每当扫描到一个字符，程序会判断此时运算数入栈（这里的运算数实际上是这个字符之前的字符组成的，比如123*x当扫描到*时123入栈）、运算符入栈或继续扫描，这个判断是线性的。计算时程序开了运算数和运算符两个栈，字符串中每个字符至多入其中一个栈一次并出栈一次（考虑到有些字符会整体作为一个数字入运算数栈，实际上出入栈的是运算数和运算符，其总和是小于字符串长度的）。此外，考虑到乘号省略情况，补全乘号后的字符串总长度也一定不会超过2n，最坏情况下也是线性的。运算数和运算符出栈时进行计算，每次计算的复杂的为常数次，因此总复杂度可以视作为 $O(n)$
综上所述，算法的时间复杂度为$O(n)$
空间复杂度：每个栈均需开一个长为1000010的数组，共开两个栈，运算符栈每个元素的大小为char类型大小，运算数栈每个元素为一个Poly类，每个Poly类实例占空间大小主要为长为65的int数组，因此两个栈空间复杂度都可以视为$O(n)$。此外程序还开了一个长为1000010的字符串来存储中缀表达式。因此总空间复杂度为 $O(n)$
LAB1 Zuma Report
01
错误类型
Runtime Error
错误原因
第19行
1 | |
未考虑到如果left本身变为0的时候left-1小于0的情况，即某种操作使从最首字符开始到操作位置之间的字符都被消掉，即会触发该错误
测例构造
相应测例：
1 | |
标准答案：
1 | |
构造思路：只需要构造某种操作使从首字符开始到操作位置之间的字符都被消掉的情况即可。上例中，当执行第一次消除后，程序运行到第19行时left=0此时会调用函数play(- 1)，而执行到第十行a.at(rank);此时rank=-1会导致函数访问数组错误，导致RE。
02
错误类型
Runtime Error
错误原因
未考虑到字符串被消除为空串后a.at(0)会越界访问
测例构造
相应测例：
1 | |
标准答案：
1 | |
构造思路：只需要构造某种操作使字符完全被消除，得到空串即可。此时完全消除字符串后变量next=0，函数调用play(0)，在下一个实例中，第十行调用at(0)时会导致数组越界访问
03
错误类型
Time Limit Exceeded
错误原因
该算法中用到的erase和insert方法的时间复杂度均是$O(n)$，最坏情况下，整体复杂度为$O(mn)$，效率过低会导致超时问题
测例构造
相应测例：
1 | |
标准答案：
1 | |
构造思路：使n和m均达到数据大小上限，并且每一次操作都有一定的复杂度（比如让每次操作都消除一些字符串）便会导致超时。
04
错误类型
Wrong Answer
错误原因
代码第12行
1 | |
操作时由于left未加1导致每次删除的字符串左侧会多删除一个，因此导致错误结果
测例构造
相应测例：
1 | |
标准答案：
1 | |
构造思路：构造一个待删除串左侧有不应该被删除的字符即可，上例中A就会被错误删除，消除时left=0，right=3，则erase(left, size)会删除字符串ABB，导致WA。
05
错误类型
Wrong Answer
错误原因
代码第27行
1 | |
输入字符串时用的cin而非getline，无法读入空字符串，不满足输入要求
测例构造
相应测例：
1 | |
标准答案：
1 | |
构造思路：构造一个空串即可制造错误，cin>>a无法读入。
06
错误类型
Wrong Answer
错误原因
当某一块输入大于$2^{12}$时，程序没有进行重组块操作，溢出的数据可能覆盖后面的块
测例构造
相应测例：
1 | |
标准答案：
1 | |
构造思路：构造一个使某一块长度大于$2^{12}$的操作即可使块数据溢出，上例中，会不断向位置1处添加字符且不会发生消除，在添加$2^{11}$个后，p[0]中元素已满，此时再在第0块中添加一个字符且不可消去时，p[0]溢出覆盖后面的内存，导致错误结果
07
错误类型
Wrong Answer
错误原因
第96行
1 | |
应改为while循环，否则会导致当某次消除需要跳过一个已经为空的块儿时无法跳过（if仅使l.first减了一次）
测例构造
相应测例：
1 | |
标准答案：
1 | |
构造思路：构造一个消除操作恰好要越过一个空块儿的测例即可，算法无法越过空快向前读取重复的字符，比如上例中，在最后一个D输入前，字符串会消除为“CD(第一块)（第二块为空）DE（第三块），此时在2处插入D，此时执行第96行时，程序无法从第三块跨过第二块看到第一块中的D，从而无法将D连消，导致产生CDDDE这样的错误结果
08
错误类型
Wrong Answer
错误原因
第92行处未进行while(1)操作，会导致无法连续消除
测例构造
相应测例：
1 | |
标准答案：
1 | |
构造思路：构造一个会发生连续消除的样例即可
09
错误类型
Runtime Error
错误原因
第130行处未判定l.first和r.first是否相等，可能出现两个相等即删除的字符串但没有跨越块儿的情况，这时候plen可能会记录错误的块长度大小数据，从而在p2a函数中memcpy函数移动数组时产生访问越界的问题
测例构造
相应测例：
1 | |
标准答案：
1 | |
构造思路：构造一个消除只发生在一个块内，且消除字符串的前后都有需要被保留的字符串即可，这样就会导致plen记录了错误的长度大小（负值），本例中，l.second=1,r.seconde=5,由于l.first与r.first相等，因此第135行计算出的len为-3，而赋到size_t类型的plen[0]中时会被转换成大整数18446744073709551613这样一个很大很大的数，远远大于p[i]的大小（$2^{12}$），导致在函数p2a中执行 memcpy时，将一个取了大于p[i]大小的数组内容，这就产生了了数组越界。
10
错误类型
Wrong Answer
错误原因
第147行
1 | |
i从l.first开始，并将其长度置为0，实际上第i块长度并不一定达到零，这就会导致最后在p2a组装回去中各块出现长度不对应的情况，在a长度计算正确的情况下，会导致组装错误
测例构造
相应测例：
1 | |
标准答案：
1 | |
构造思路：构造一个消除会跨越块发生，且消除字符的前后都有剩余字符的测例即可。本例中，数组总长计算没有错，但plen[0]会被赋成0，所以导致p2a中第一块部分并没有被组装回原数组a中，只有p[1]中剩余的“C”会被复制到a[0]开始的内存中，而后面的部分实际上是a数组原来的剩余，最终导致输出C（来自p[1]）AABBAABB……（原数组剩余）的结果，产生错误答案