noip2009普及组复赛解题报告

【NOIP2009普及组复赛解题报告】 本次解题报告主要涉及两道题目，分别是多项式输出和分数线划定。 **第一题：多项式输出** 这是一道要求根据输入的多项式系数，按照特定格式输出多项式的题目。算法分析如下： 1. **时间复杂度**：O(n)，其中n表示多项式的最高次数。 2. **空间复杂度**：O(n)，用于存储非零系数及其对应的次数。 3. **解题思路**： - 遍历输入的系数，只存储非零项到数组a和b中，a存放系数，b存放对应次数。 - 输出时，考虑特殊情况： - 系数绝对值为1，不需要输出。 - 指数为1或0，应分别输出"x"或不输出。 - 首项前的加号不必输出。 - 使用辅助函数处理x^n部分，根据指数生成相应的字符串。 - 对于每项的符号，如果不是首项，需判断正负并输出相应符号。 **参考程序**： 提供的参考程序使用了Pascal语言，其主要逻辑是读入系数，存储非零项，然后按照处理规则输出多项式。 **第二题：分数线划定** 这道题目要求根据给定的分数和编号，找出前[m*150%]个（考虑重分情况）分数，输出实际数目、最低分数以及排序后的分数和编号。 1. **时间复杂度**：O(Nlog2N)，使用了排序算法。 2. **空间复杂度**：O(N)，存储输入的分数和编号。 3. **解题策略**： - 关键在于选择合适的排序算法。由于数据规模不大（n≤5000），可以选择O(Nlog2N)的排序算法，如快速排序或堆排序。 - 在处理过程中，注意双关键字排序，即同时考虑分数和编号。 - 对于快速排序，由于不稳定，需要在比较条件上进行调整。 - 为了避免重分带来的问题，可以使用“分数*10000+编号”作为排序键。 **参考程序**： 提供了基于快速排序的程序框架，但具体实现并未给出。在实际编程时，需要补充快速排序的递归部分，并在比较函数中考虑分数和编号的双重标准。 总结，这两道题考察了基础的数据处理能力，包括输入输出、数组操作、排序算法以及特殊情况的处理。在编程竞赛中，理解题目需求、选择合适的数据结构和算法是解决问题的关键。