✅ PAT 甲级题目讲解1002《AB for Polynomials》 摘要本文是 PAT 甲级 1002 题《AB for Polynomials》的详细题解介绍了多项式加法的实现方法使用数组以指数为下标、累加系数再统计非零项并按降幂输出。文章涵盖题目要求、样例分析、解题思路、完整代码、常见错误提醒及复杂度分析并提供思维拓展帮助读者掌握稀疏多项式合并的典型处理技巧。 题目简介本题要求实现两个一元多项式A(x)A(x)A(x)与B(x)B(x)B(x)的加法操作。每个多项式使用若干个指数-系数对表示最终输出它们之和结果中的零系数项应省略。 样例分析输入样例2 1 2.4 0 3.2 2 2 1.5 1 0.5表示两个多项式分别为A(x)2.4x13.2A(x) 2.4x^1 3.2A(x)2.4x13.2B(x)1.5x20.5x1B(x) 1.5x^2 0.5x^1B(x)1.5x20.5x1合并相同指数项后A(x)B(x)1.5x2(2.40.5)x13.21.5x22.9x13.2A(x)B(x) 1.5x^2 (2.40.5)x^1 3.2 1.5x^2 2.9x^1 3.2A(x)B(x)1.5x2(2.40.5)x13.21.5x22.9x13.2输出3 2 1.5 1 2.9 0 3.2 解题思路本题是典型的“稀疏多项式合并”问题需注意指数相同项的合并与零系数项的剔除。使用一个长度为 1005 的数组b[]以指数为下标、系数为值来存储合并后的多项式。需特别注意以下几点系数为 0 的项不能输出指数需从高到低排序输出格式需精确到小数点后一位且注意控制空格。 变量说明变量名类型含义kint当前读入的非零项个数nint当前项的指数adouble当前项的系数b[]double[]存储每个指数对应的系数maxnint当前出现的最大指数cint合并后非零项的数量✅ Step 1输入并合并多项式项封装一个f()函数用于处理每组多项式的输入读取k对指数-系数对每读入一项(n,a)(n, a)(n,a)就执行b[n] a;同时更新出现的最大指数maxnvoidf(){scanf(%d,k);while(k--){scanf(%d %lf,n,a);// 读取 k 对 指数-系数maxnmax(n,maxn);// maxn 记录最大指数项值b[n]a;// 指数为 n 的项系数加上 a}}调用两次f()函数分别读入A(x)A(x)A(x)与B(x)B(x)B(x)f();// 读 Af();// 读 B✅ Step 2统计非零项个数从x0x^0x0到xmaxnx^{maxn}xmaxn统计非零项项数c输出总项数cfor(inti0;imaxn;i){if(b[i])c;}printf(%d,c);✅ Step 3按降幂输出结果从xmaxnx^{maxn}xmaxn到x0x^0x0降序输出每一项的(指数 系数)注意格式控制先空格、浮点保留一位小数等。for(intimaxn;i0;i--){if(b[i]){printf( %d %.1lf,i,b[i]);}}✅ 完整代码#includebits/stdc.husingnamespacestd;intk,n,maxn,c;doublea,b[1005];voidf(){scanf(%d,k);while(k--){scanf(%d %lf,n,a);maxnmax(n,maxn);b[n]a;}}intmain(){f();f();for(inti0;imaxn;i){if(b[i])c;}printf(%d,c);for(intimaxn;i0;i--){if(b[i]){printf( %d %.1lf,i,b[i]);}}return0;} 常见错误提醒错误类型具体表现忽略合并同类项相同指数项未累加导致重复项浮点数精度丢失未保留一位小数或误差未处理忘记剔除零系数项输出了系数为 0 的项输出格式不规范多余空格、换行或小数位数错误✅ 总结归纳 核心方法总结使用数组下标作为指数直接累加系数排序输出 精度控制。 技术要点回顾多项式的稀疏表示浮点加法的误差控制格式化输出技巧保留小数、控制空格。 复杂度分析时间复杂度O(n)\mathcal{O}(n)O(n)空间复杂度O(1001)\mathcal{O}(1001)O(1001)其中nnn为两多项式项数之和最大指数不超过 1000。 思维拓展多项式乘法该如何实现能否用 map 优化若存在负指数或小数指数该如何表示和合并若输入项数10510^5105该如何减少空间消耗