DSA PA2 Report

DSA PA2 Report

PA2-1 Risk解题报告

算法构思与实现要点

  1. 首先，将每天感染人数和向前查询天数（$m_i$）读入num和m数组中，并维护一个Queap类的实例q（能够执行push，pop_to_size [弹出元素直至主队列元素个数为指定size] 和 get_max [返回当前队列中最大元素] 操作）。
  2. 接着，逐日求出当日前$m_i$天的最大病例数，具体而言：由于$i-m_i$单调非减，到第$i$天时q中至多只需要维护前$m_i$天的数据，因此若此时q.size() > m[i]，则先调用q.pop_to_size(m[i])将q的大小进行缩减，此时暴露在q队首所指的也恰好就是待查询（至多）$m_i$长度后缀中最大元素的位置，此时只需对q调用get_max并将数据存入数组（record[i] = q.get_max()），然后将第$i$天病例数num[i]加入q即可。
  3. 最后，调用qsort对record数组中记录的数据由小到大排序，并调用二分查找分别找出record中（严格）小于p和小于q的最大元素的位置，由此求出低中风险天数即可。
  • 注：Queap类实现要点：
    • 内部维护两个数组queue和max_record（仅就本题数据范围考虑分配足够空间，因此并未额外实现扩容等操作），分别记录主队列中存放的数据和队列后缀中最大元素位置（数组下标）。另有两组数分别记录queue和max_record的首尾位置，通过这组指针的移动模拟对队列增删等操作
    • push()函数：在主队列queue尾部加入数据，然后从后往前将新数据与max_record记录的后缀最大元素比较，如果新元素大于等于记录元素就将max_record的尾指针不断前移，直到不满足条件时将max_record的尾部记录新元素位置
    • pop_to_size(int size)函数：将queue的头指针直接移到尾指针减size的位置，代表让前面元素一次性出队，然后从头部开始逐一检查max_record中记录得到最大元素位置是否已经出队，若所记录的元素已经出队则让max_record的头元素也出队即可
    • get_max()函数：直接返回max_record头元素所指向的queue中的元素（queue[max_record[head]]）即可

完成过程中遇到的问题与解决过程

  1. 直接调用课上所讲的二分查找函数返回的是不大于$p/q$的最大元素位置，而此处要求查找的是严格小于$p/q$的最大元素位置，为此只需要改为查找不大于$p-1/q-1$的最大元素位置即可；由于数组坐标从0开始，最后计算数量时还需要在查找出来的坐标值基础上+1
  2. 开始没有注意$m_i$和$p,q$数据范围已经超出int最大正整数范围，导致在九成测中有两个测例没有通过，将对应部分均改为long long即可

复杂度估算

设统计天数为$n$，每次处理一天需要进行一次push、一次get_max和至多一次pop_to_size操作，由于push操作中每个元素的下标最多从max_record的队尾进入一次、出去一次，总操作数$\le 2n$，pop_to_size操作中每个元素下标最多从队首出去一次，总操作数$\le n$，整体总操作数$\le 3n$，故处理单日数据的分摊复杂度为$O(1)$，全部处理完的时间复杂度约为$O(n)$。对$n$个元素的record数组调用qsort排序,时间复杂度为$O(n \log n)$。设共有$T$次查询，每次查询调用两次二分查找，总时间复杂度为$O(T·2 \log n)$，故整个算法时间复杂度约为$O(n+(n+2T)\log n)$。使用三个数组分别存储每日病例数、查询天数、查询天数中的最大数，且Queap中也要分配相应大小的空间存储数据，空间复杂度约为$O(n)$。

PA2-2 Polynomial解题报告

算法构思与实现要点

实现一个Polynomial类，用一个数组存储多项式各次项系数，一个整数high标记最高位次数，然后重载+=、-=、*=、^=，即可像处理整数一样处理多项式，使用中缀表达式求值的方法即可求出结果多项式。

  • 具体而言，先实现一个Stack类并维护一个Stack<char>类的符号栈和一个Stack<Polynomial*>类的多项式栈，每当在表达式串中遇到一个整数（不在^之后）或字符x时，都会new出一个Polynomial类的指针压入栈中；每当遇到一个^符号时，会同时读入下一个整数（因为最高只可能是4次方，且次幂位置无其他符号），取出栈顶多项式完成相应运算后压入栈中；每当遇到+、-、*符号时，按照约定优先级判断是将符号压入符号栈中还是取出栈顶多项式和符号执行相应运算。另外，还需要特判一下两种省略*的情况，相应将*压入栈中（严格来说，此处应该先判断*与栈顶符号优先级，再判定是将*压入栈中还是执行栈顶运算；但由于*优先级比其他两个符号都更高，因此直接将省略*可能带来的唯一影响就是乘法右结合而非左结合，但根据乘法结合律不会影响运算结果，因此此处可以直接将省略的*压入栈中）。
  • 注：Polynomial类实现要点：
    • +=、-=实现较为简单，对应系数相加减，按需求更改high即可。
    • 为了使整体实现更加简洁优雅，*=、^=共用了一个multiply(long long* a, const long long* p_a, int& high, int p_high)函数，其中a和p_a是两个存储多项式系数的数组，high和p_high分别记录两个多项式的最高次数（也就对应数组的边界），multiply可以在不额外分配空间的情况下在a的空间上原地实现a和p_a的多项式相乘，结果放在a中，由于是从结果的高次方系数位向低次方系数位计算，因此不会发生数据覆盖，以此省去了用new重新分配空间储存结果的时间和空间开销，具体实现可参见代码。
    • 由于^=后次幂最多为四次方，因此分为了四种情况单独判断处理，相应调用multiply函数解决，3次方和4次方都是调用两次multiply即可计算出结果。

完成过程中遇到的问题与解决过程

  1. 开始没有特判“若结果为0，则直接输出0”的情况，此时high会被减到负数，输出为空，特判一下即可。
  2. 在计算3次方时开始没有注意经过第一次2次方后high已经变成原来的2倍了，修改即可。
  3. 当当前读入的符号比栈顶符号优先级高的时候，不应当把当前符号压入符号栈或继续读取下一字符，因为这个s可能会引起前面一系列运算符的运算（比如当前符号恰为右括号），必须等这一系列运算都算完了，碰到下一个case’<’的情况s才能++。
  4. 当完成一次多项式二元运算后应当把多余的Polynomial指针立刻delete掉，否则会引起内存泄漏导致MLE，这警示之后要时刻注意及时delete掉new分配出的已经无用的空间，避免内存泄漏。
  5. 困扰我最久的一个错误是TOJ上两个点报出的Runtime Error (trap 253 SIGABRT)错误，引起相应错误的测例在本地无论如何都找不出来，但可以调试出来是Stack类实现中的一个问题。无奈之下，某一天晚上我随手改了Stack类的构造函数，将 
    1
    Stack() try: _elem(new T[capacity]) {}
    改为 
    1
    2
    3
    Stack() {
        _elem = new T[capacity];
    }
    立刻就得以通过。这一奇怪的现象引起了我的兴趣，我进一步上StackOverflow上查阅了相关资料（由于这是解决问题后的拓展查询而非参考资料，没有写入Honor Code中），据说是在初始化列表里用new分配空间有可能会失败报错。于是我进一步探索发现，这一问题除了用上述写入构造函数体的办法解决之外，用try catch捕获一下new分配空间时报出的std::bad_alloc异常也可通过测试，如下： 
    1
    2
    Stack() try: _elem(new T[capacity]) {}
    catch(char* str) {}

复杂度估算

中缀表达式求值为一趟线性扫描算法，中间每个符号最多入栈一次出栈一次，每个多项式最多入栈两次出栈两次（二元运算符计算的结果会导致第二次进栈，但此时一定有一个参与二元运算的多项式不会再进栈；将次方上的幂指数也看做一个多项式），因此整体运算次数与输入字符串长度$n$成正比，为$O(n)$，每次运算至多进行2次乘法，由于整个过程中最高次数不超过$m$，每次运算时间复杂度最高不超过$O(2(m/2)^2)$。空间开销主要在于栈中存储中间运算结果多项式和符号，多项式最高次数不超过$m$，因此空间复杂度为$O(mn)$。