DSA PA1 Report

PA1-1 A*B Problem解题报告

算法构思与实现要点

模拟竖式乘法计算高精度乘法，首先用char数组读取输入数据，然后将输入数字按“10^9进制”（每9位十进制数为一组，这样两个数字相乘仍然不超过long long最大正整数范围，能最大程度减少循环次数，从常数上优化算法效率）逆序存入long long数组，按10^9进制模拟竖式乘法计算并将结果存入ans数组中，然后逆序输出（除最高位外中间位均右对齐补0）

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

• 一开始使用的是最朴素的十进制竖式乘法模拟，即数组中的每一位只存储0-9的数字，这样由于两个数字相乘的计算量与两个数字位数的积成正比，进行500次5000位 * 5000位（十进制）数的乘法大约要进行500 * 5000 * 5000 = 1.25 * 10^10次计算，超出可接受范围，最终在五成测中获得40分（TLE)
• 为了最大程度利用内置乘法减少循环次数，只要在long long数据范围内（约10^20以下）的乘法都可以直接计算，因此想到按组拆分原数据，按“ 10^9进制 ”进行存储和计算，这样总计算量大约降为500 * 5000/9 * 5000/9 = 2 * 10^8量级，为1s内可以接受的级别，并且由于以10的次方为基底，方便输出，也不用修改原程序的竖式乘法逻辑
• 在修改过程中遇到了一个输出格式问题，即输出的乘法结果除了最高那9位数字以外，其他每9位在输出时都要右对齐补0为一个9位数，这一bug是通过对拍程序检查输出结果找出来的

复杂度估算

设总共完成m次乘法计算，每次两个因子的十进制位数分别为n1和n2（量级相同，统称为n），则渐进时间复杂度为$O(m * n^2)$，考虑在常数意义下的优化，优化后的算法时间复杂度具体而言约为$O(m * \frac{n1}{9} * \frac{n2}{9})$；采用三个long long数组存储因子和答案完成模拟竖式计算，数组长度与因子的十进制位数成正比，渐进空间复杂度为$O(n)$，具体而言约为$O(\frac{n1}{9} + \frac{n2}{9} + \frac{n1+n2}{9})$

PA1-2 Graphics解题报告

算法构思与实现要点

首先用两个int数组存储x轴、y轴上的坐标点，并调用中的qsort函数进行排序，排序后将编号对应的坐标点两两连成线段恰能保证线段之间两两不相交，其中第i条线段的方程为 $\frac{x}{a[i]} + \frac{y}{b[i]} = 1 (x \ge 0, y \ge 0, 0 \le i < n)$。然后对m次查询进行m次二分查找，找到“恰好无法相交”的线段编号hi，hi也即能相交到的线段数（因为编号从0开始）。判断问询点(px, py)能否与第i条线段相交的准则是：将px代入线段方程得到一个纵坐标值，若py大于等于该值则问询点在线段上方，能够相交。

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

• 一开始遗漏了一种特殊情况，即问询点在所有线段（第0条线段）下方，与0条线段相交，后加入一条特判即得以解决
• 由于坐标范围很大（接近int上界），在用上述方法判断点是否在线段上方时因为调用两个大int相乘结果会溢出造成错判，吸取教训：数据范围过大达到int边界时一定要小心，尤其小心两数相乘，保险起见最好用long long

复杂度估算、

设x轴、y轴上分别有n个坐标点，则对坐标点快速排序需要的时间复杂度为$O(nlogn)$；总共问询m次，每次进行一次二分查找，总共需要的时间复杂度为$O(mlogn)$，综上，算法时间复杂度为$O((2n+m)logn)$。需要两个数组存储x轴、y轴坐标点，空间复杂度为$O(n)$。